Interval Tree
A BST of intervals augmented with subtree maximum endpoints for overlap queries.
Interval, kd and Range Trees: Interval tree: the max endpoint prunes a subtree
At 15-20. No overlap. The left subtree's max is 30, at least 6, so some interval on the left may reach the query: go left.
Cost
- Insert
- O(log n)
- Overlap query
- O(log n)
- All overlaps
- O(k log n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.