AlgoScope

Interval Tree

A BST of intervals augmented with subtree maximum endpoints for overlap queries.

Data structures, data structure, advanced
At 15-20: No overlap, left max reaches the query: go left.5-20 | 2010-30 | 3012-15 | 1515-20 | 4017-19 | 4030-40 | 40node
At 15-20: No overlap, left max reaches the query: go left.5-20 | 2010-30 | 3012-15 | 1515-20 | 4017-19 | 4030-40 | 40node

Interval, kd and Range Trees: Interval tree: the max endpoint prunes a subtree

Decision, step 2 of 5

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)

Taught by the same lesson

Interval, kd and Range Trees covers these too, in the same run.