Interval Trees

2 min read•1 page

An Interval Tree is a centered 1D search structure that stores a set of intervals. Each node in the tree is associated with a pivot point. The intervals are partitioned based on whether they lie entirely to the left, entirely to the right, or contain the pivot.

Interval representation:

1. Pivot Selection: Typically the median value of all interval endpoints. 2. Center Set: Intervals containing the pivot are stored directly at the node. 3. Sorted Arrays: The center set is stored in two sorted lists (by low and high coordinate) to enable rapid overlap querying.

python

1class IntervalNode:
2    def __init__(self, pivot):
3        self.pivot = pivot        # Midpoint coordinate
4        self.left = None           # Subtree for intervals to the left
5        self.right = None          # Subtree for intervals to the right
6        # Stored intervals containing the pivot
7        self.by_low = []           # Sorted by start coordinate
8        self.by_high = []          # Sorted by end coordinate

2 min read•1 page

To build the tree, we choose a splitting pivot coordinate (usually the median of all start and end points) and partition the list of intervals.

Partition Rules:

1. Left Subtree: All intervals completely to the left of the pivot ($end < pivot$). 2. Right Subtree: All intervals completely to the right of the pivot ($start > pivot$). 3. Center Node: All intervals containing/overlapping the pivot ($start \le pivot \le end$).

python

1def build_interval_tree(intervals):
2    if not intervals:
3        return None
4
5    # 1. Find pivot (e.g., median of endpoints)
6    endpoints = []
7    for start, end in intervals:
8        endpoints.extend([start, end])
9    pivot = sorted(endpoints)[len(endpoints) // 2]
10
11    # 2. Partition intervals
12    left, right, center = [], [], []
13    for start, end in intervals:
14        if end < pivot:
15            left.append((start, end))
16        elif start > pivot:
17            right.append((start, end))
18        else:
19            center.append((start, end))
20
21    # 3. Recursively construct subtrees
22    node = IntervalNode(pivot)
23    node.by_low = sorted(center, key=lambda x: x[0])
24    node.by_high = sorted(center, key=lambda x: x[1])
25    node.left = build_interval_tree(left)
26    node.right = build_interval_tree(right)
27    return node

Active Pivot Coordinate X

0.00

2 min read•1 page

Querying an Interval Tree with a coordinate point $x$ finds all intervals containing $x$. We recursively traverse down, pruning entire subtrees.

Query Algorithm:

1. Pivot Comparison: Compare query $x$ to node pivot. 2. Pruning subtrees: If $x < pivot$, we only need to search the left subtree (plus the center set). If $x > pivot$, we only need to search the right subtree (plus the center set). 3. Early Stopping: By traversing the sorted center arrays, we stop checking as soon as an interval is guaranteed not to overlap.

python

1def query_interval_tree(node, x, results):
2    if not node:
3        return
4
5    # Compare query coordinate with node pivot
6    if x < node.pivot:
7        # Traverse center sorted by start (left endpoint)
8        for inv in node.by_low:
9            if inv[0] > x:
10                break  # Stop: remaining starts are larger than x
11            results.append(inv)
12        # Search left subtree
13        query_interval_tree(node.left, x, results)
14    else:
15        # Traverse center sorted by end (right endpoint) in reverse
16        for inv in reversed(node.by_high):
17            if inv[1] < x:
18                break  # Stop: remaining ends are smaller than x
19            results.append(inv)
20        # Search right subtree
21        query_interval_tree(node.right, x, results)

Query Coordinate X

-0.50

Show Query Line