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

2 min read•1 page

Adding intervals dynamically requires checking their placement relative to each node's pivot. If an interval lies entirely left or right, we recurse down. If it intersects the pivot, we append it to the node's sorted center set.

InsertInterval(node, interval):

1. Pivot Left: If $end < pivot$, recurse left. 2. Pivot Right: If $start > pivot$, recurse right. 3. Sorted Insertion: If it overlaps, insert into the center set and re-sort lists by start/end points.

python

1def insert_interval(node, interval) -> IntervalNode:
2    if node is None:
3        # Create leaf with interval as initial pivot
4        return IntervalNode((interval[0] + interval[1]) / 2.0)
5
6    start, end = interval
7    if end < node.pivot:
8        # Add to left subtree
9        node.left = insert_interval(node.left, interval)
10    elif start > node.pivot:
11        # Add to right subtree
12        node.right = insert_interval(node.right, interval)
13    else:
14        # Overlaps pivot: add to center lists and sort
15        node.by_low.append(interval)
16        node.by_low.sort(key=lambda x: x[0])
17        node.by_high.append(interval)
18        node.by_high.sort(key=lambda x: x[1])
19
20    return node

Active Segments Count

1.00