Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Balanced interval indexes: rotate height and maximum metadata together

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An interval search tree can be balanced with AVL rotations while storing the maximum interval end under each node. Ordering by the pair (start, end) lets distinct windows share a start. After insertion, each ancestor recomputes its height and maximum end; any required single or double rotation then refreshes both metadata fields in child-first order. An overlap lookup can skip a left subtree whose maximum end is not greater than the query's low endpoint. The implementation supports insertion and finding one overlap, using half-open intervals. Deletion and enumerating every overlap require additional methods.

Operational case

A maintenance calendar inserts [47, 61), [19, 26), [52, 58), [83, 91), and [31, 42). It finds an overlap for [25, 32) and none for [62, 80). The stored root height remains three and its maximum end is 91 after the five inserts. Those values are derived from children, not guessed from insertion order. A plain augmented BST could become a chain under sorted starts; AVL height repair keeps this index logarithmic while endpoint metadata supports pruning. Equal complete interval pairs are ignored here rather than counted as separate bookings.

Working Python program

python
class WindowNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.height = 1
        self.max_end = end


def height(node):
    return node.height if node else 0


def refresh(node):
    node.height = 1 + max(height(node.left), height(node.right))
    node.max_end = max(node.end, node.left.max_end if node.left else node.end, node.right.max_end if node.right else node.end)


def rotate_left(old_root):
    new_root = old_root.right
    old_root.right = new_root.left
    new_root.left = old_root
    refresh(old_root)
    refresh(new_root)
    return new_root


def rotate_right(old_root):
    new_root = old_root.left
    old_root.left = new_root.right
    new_root.right = old_root
    refresh(old_root)
    refresh(new_root)
    return new_root


def add_window(node, start, end):
    if start >= end:
        raise ValueError("empty or reversed window")
    if node is None:
        return WindowNode(start, end)
    key = start, end
    current_key = node.start, node.end
    if key < current_key:
        node.left = add_window(node.left, start, end)
    elif key > current_key:
        node.right = add_window(node.right, start, end)
    else:
        return node
    refresh(node)
    difference = height(node.left) - height(node.right)
    if difference > 1:
        if key > (node.left.start, node.left.end):
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if difference < -1:
        if key < (node.right.start, node.right.end):
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def first_overlap(node, low, high):
    if low >= high:
        raise ValueError("empty or reversed query")
    while node:
        if node.start < high and low < node.end:
            return node.start, node.end
        if node.left and node.left.max_end > low:
            node = node.left
        else:
            node = node.right
    return None


window_root = None
for start, end in ((47, 61), (19, 26), (52, 58), (83, 91), (31, 42)):
    window_root = add_window(window_root, start, end)
print(first_overlap(window_root, 25, 32))
print(first_overlap(window_root, 62, 80))
print(window_root.height, window_root.max_end)

Output

Output
(19, 26)
None
3 91

Time, space, and tradeoff

Insertion and one-overlap lookup take O(log n) time because AVL height is logarithmic and each visited node performs O(1) metadata work. Insertion uses O(log n) recursion stack space, and the tree uses O(n) nodes. The search returns any overlapping interval, not necessarily the earliest or shortest one. A query that must enumerate k overlaps needs output-sensitive traversal and at least O(k) result work. Concurrent readers must not inspect partly rotated nodes without synchronization or an immutable snapshot; this Python program has no such protocol.

Common Mistakes

  • Do not update height while leaving max-end metadata stale after a rotation.
  • Do not call touching half-open endpoints an overlap.
  • Do not claim this insertion-only index handles removal of a booking.

Connected lessons

Apply this mutation in the index mutation project, then check the mutation quiz.

AVL interval deletion: repair balance and maximum endpoints extends this operation.

Buddy blocks: split powers of two and reunite partners extends the storage ownership comparison.

Disjoint interval unions: maintain covered maintenance time adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details