Interval Tree
A BST of intervals augmented with subtree maximum endpoints for overlap queries.
Decision · step 2 of 5Interval, 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.
What you will see
Intervals drawn as bars on nodes; the search prunes subtrees whose max endpoint is too small.
Cost
| insert | O(log n) |
|---|---|
| overlap query | O(log n) |
| all overlaps | O(k log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.