An interval tree is a data structure that indexes intervals so a query can find those that intersect a given window. A risk system can use one to check whether a proposed exposure window overlaps an existing position’s window as positions open and close.
What the tree stores
In the augmented balanced binary search tree version, each node holds one interval , ordered by start . A record ID can break ties between equal starts. Each node also stores max end, the largest end among its own interval and all its descendants. Recompute that value from the node’s own end and its children’s cached maxima. A rotation changes which intervals lie below the rotated nodes, so update the lower node before the new local root. MIT OpenCourseWare on interval-tree augmentation
Use nonempty, half-open intervals, with the start included and the end excluded. A stored interval overlaps query exactly when
A subtree with max end at or before can be skipped because every interval in it ends too soon. A node whose start is at or after is too late, as is its entire right subtree. Its left subtree can still contain an earlier start.
Trace the query
Four fictional exposure windows are measured in minutes from the start of a session. The root stores and has max end 12 because its right child stores . The root overlaps the query. Its left subtree has max end 4, so the search skips outright. On the right, starts at the query’s excluded end. That node misses, but its left child overlaps. The complete result is and .
![Query [4, 9) overlaps [3, 8) and [8, 10). The tree prunes [1, 4) because its maximum end is 4. It skips [9, 12) because that node starts at 9, but checks its left child 8, 10).
The timeline shows where the two matches overlap the query. The tree rules out the left branch by its maximum end and skips the right child’s own interval by its start.
Finding one match and reporting every match
Find any overlap. Test the current node and stop on a hit. Otherwise go left if the left subtree’s max end is strictly greater than . If it is, some left interval ends after . That interval either overlaps or starts at or after , in which case every right interval also starts too late. If the left child is absent or its max end is at most , go right. Reaching a missing child means there is no match. On the same tree, a one-match search for goes from the root to , then left to .
One search takes time for tree height . With a red-black tree and correctly maintained maxima, finding one overlap, inserting a record and deleting a record by its key each take worst-case time for stored intervals, using space. MIT OpenCourseWare on the search and its correctness
Report all overlaps. A depth-first traversal can use both pruning rules and visit both children when they might contain results. The traversal runs in time in the worst case, and emitting matches takes time. The one-path bound applies to finding a single match. For a different query, “which windows contain time ?”, a static centered interval tree groups intervals that contain each split point in endpoint-sorted lists. It can report all intervals containing in time by scanning only the relevant end of each list along a single path. Mount’s lecture on interval trees and point stabbing
The SelfMadeQuant lesson shows how to maintain the cached values through rotations and works through a closed-interval search for one match. The preview is public and the full lesson requires membership. Augmenting Data Structures
Sources
- Erik D. Demaine and Charles E. Leiserson (2005). Augmenting Data Structures, MIT OpenCourseWare, lecture 11.
- David M. Mount. Computational Geometry, lecture 24, “Interval Trees,” pp. 116–119.