Balanced Search Trees and Ordered Queries

A changing set of keys often needs more than “is 26 present?” It may need the largest key below 26, or every key between 25 and 60. A balanced search tree keeps both key order and short search paths, making it useful for dynamic ordered sets. For data that rarely changes, start with binary search. The data structures map and search algorithms map connect these choices to the workload.

Search order applies to entire subtrees

The binary search tree definition in Open Data Structures requires keys from a total order: every key in a node's left subtree is smaller than its key, and every key in its right subtree is larger. Here the tree has set semantics: inserting an existing key adds no node. A tree used as a map can instead update the value associated with that key.

Checking only parent and child is insufficient. With root 40 and left child 20, the right child of 20 may be 30, but cannot be 50. Although 50 exceeds 20, it still belongs to the left subtree of 40. An inorder traversal—left subtree, node, right subtree—produces increasing keys.

A min-heap requires only that a parent's key be no greater than its children's keys. Root 10 with left child 70 and right child 20 satisfies heap order. It provides no search-tree partition between left and right, so one comparison cannot select a single search direction. A heap suits repeated minimum extraction; a search tree supports key lookup and ordered queries.

Follow one path, then report keys in order

Insert 40, 20, 60, 10, 30, 50, 70, 55 in that order:

L and R denote left and right children. Searching for 55 visits 40, 60, 50, 55: 4 nodes. Reaching an empty child without equality means the key is absent. Inserting 25 visits 40, 20, 30, then attaches the new node as the empty left child of 30.

Ordered queries retain a candidate while descending:

Query	How the candidate changes	Result after inserting 25
Strict predecessor: largest key below x	Save the current key when it is below x, then go right; otherwise go left	predecessor(26) = 25
Lower bound: smallest key at least x	Save the current key when it is at least x, then go left; otherwise go right	lower_bound(26) = 30
Half-open range $[lo, hi)$	Traverse inorder, skipping subtrees that cannot contain a result	$[25,60)$ reports 25, 30, 40, 50, 55

Predecessor and lower bound can return an answer even when the target key is absent. They return None when no key qualifies. Strict predecessor excludes equality; lower bound includes it. The corresponding array boundary is explained in binary search's lower bound.

For a range query, retain the inorder traversal stack or parent links so the next key can be reached without starting over. The recursive implementation below uses the call stack and prunes by the endpoints. With $k$ reported keys and tree height $h$, a single lookup takes $O(h+1)$, reporting a range takes $O(h+1+k)$, and the auxiliary stack uses $O(h+1)$ space. In a balanced tree, the range cost is $O(\log(n+1)+k)$; writing the results alone costs $O(k)$. Searching again from the root for each result adds repeated lookup work.

Sorted insertion can create a chain

In Open Data Structures' height convention, height counts edges from the root to the deepest real node. A single-node tree has height 0. Insert 1, 2, 3, 4, 5, 6, 7 in order and each new key goes right, creating a chain of height 6. Finding 7 visits 7 nodes. In general, $n$ increasing keys yield height $n-1$ and a linear-time search at the end. Building the tree visits $0+1+\cdots+(n-1)=n(n-1)/2$ existing nodes in total.

Correct search order does not guarantee logarithmic height. A balancing algorithm needs an additional invariant that constrains the shape, and must restore it after each update.

Rotations change links while preserving order

Open Data Structures describes rotations and their pointer operations in Section 7.2. A right rotation promotes the left child to the local root and makes the old root its right child. Diagram 1 is before the rotation; diagram 2 is after it:

The middle subtree 30 must move from the right of 20 to the left of 40. Its keys lie between 20 and 40, so either attachment preserves search order. The inorder sequence remains 10, 20, 30, 40, 60. The same argument applies to whole subtrees: keys on the left are below 20, middle keys lie between 20 and 40, and keys on the right exceed 40. A left rotation reverses these changes.

A rotation changes a constant number of links and costs $O(1)$. The caller must attach the returned local root to its parent, or replace the tree's root. Implementations with parent pointers, subtree sizes, or similar fields must update those fields too. Rotation preserves search order; the balancing invariant determines which rotations are needed.

Red-black colours constrain height

Red-black trees guarantee worst-case $O(\log n)$ search, insertion, and deletion for nonempty trees. The red-black invariants in Section 9.2 provide a way to check the structure:

• Each real node is red or black, the root is black, and empty children are treated as black NIL nodes.
• A red node has black children: two red nodes cannot be adjacent.
• Every path from any node to a descendant NIL contains the same number of black nodes.

For counting in the example, let $b$ be the number of real black nodes on a root-to-NIL path, including the root and excluding NIL. No adjacent red nodes means a longest path can at most alternate black and red. Equal black counts require corresponding depth on every branch. Recursive counting gives at least $2^b-1$ real nodes, while a root-to-deepest-node path contains at most $2b$ real nodes. A convenient height bound is therefore:

$$h \le 2\log_2(n+1), \qquad n\ge 1.$$

This is an upper bound, not a requirement that left and right subtrees have equal sizes. The book's implementation also maintains a left-leaning condition: if a left child is black, the right child must be black. The three conditions above are the general red-black constraints checked here.

Insertion first adds a red leaf in search order, preserving each path's black count, then repairs any red-red edge and makes the root black. Inserting the first key into an empty tree also requires colouring the new root black; this increases every path's black count by 1. For example, start with black root 30 and its red left child 20, then insert red 10. The edge 20—10 violates the invariant. Rotate right at 30, colour 20 black and 30 red, and the result is black root 20 with red children 10 and 30. Every path has 1 real black node, and height falls from 2 to 1. The code below executes and checks this particular repair case.

Deleting a node with two children

Ordinary search-tree deletion has three cases. Detach a leaf; replace a node that has one child with that child; for a node with two children, replace its key with the minimum key in its right subtree, its strict successor, then remove the successor's original node.

In the earlier tree, after inserting 25, delete 40. The smallest key in the right subtree is 50, so the root's key becomes 50. The original 50 has no left child but has right child 55. Removing it must change the left child of 60 to 55. The final inorder sequence is 10, 20, 25, 30, 50, 55, 60, 70: only 40 is gone. For key-value records, replace the value along with the key; copying only the key would associate it with the wrong record.

A red-black tree must also restore its colour constraints. Physically removing a black node leaves some paths one black node short. Repair uses the replacement child's and sibling's colours to recolour and rotate, propagating the deficit toward the root when necessary. The relevant colour is that of the successor node actually removed, not just the node containing the originally requested key. Restoring search order and restoring red-black balance are separate steps of deletion.

Runnable queries and deletion

This program implements the structural operations of an ordinary binary search tree with integer keys. Duplicate insertion adds no node, and deleting an absent key leaves the set unchanged. The colour field is used by the repair example that follows; insert and delete here perform no red-black balancing. Recursive operations need enough call-stack depth for the whole path; a long chain that exceeds Python's recursion limit raises RecursionError.

from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: 'Node | None' = None
    right: 'Node | None' = None
    red: bool = False


def insert(t, x):
    if t is None:
        return Node(x)
    if x < t.key:
        t.left = insert(t.left, x)
    elif x > t.key:
        t.right = insert(t.right, x)
    return t


def search(t, x):
    path = []
    while t is not None:
        path.append(t.key)
        if x == t.key:
            return True, path
        t = t.left if x < t.key else t.right
    return False, path


def predecessor(t, x):
    best = None
    while t is not None:
        if t.key < x:
            best, t = t.key, t.right
        else:
            t = t.left
    return best


def lower_bound(t, x):
    best = None
    while t is not None:
        if t.key >= x:
            best, t = t.key, t.left
        else:
            t = t.right
    return best


def between(t, lo, hi):
    if t is None:
        return
    if lo < t.key:
        yield from between(t.left, lo, hi)
    if lo <= t.key < hi:
        yield t.key
    if t.key < hi:
        yield from between(t.right, lo, hi)


def delete(t, x):
    if t is None:
        return None
    if x < t.key:
        t.left = delete(t.left, x)
    elif x > t.key:
        t.right = delete(t.right, x)
    else:
        if t.left is None:
            return t.right
        if t.right is None:
            return t.left
        successor = t.right
        while successor.left is not None:
            successor = successor.left
        t.key = successor.key
        t.right = delete(t.right, successor.key)
    return t


def height(t):
    return -1 if t is None else 1 + max(height(t.left), height(t.right))


root = None
for x in [40, 20, 60, 10, 30, 50, 70, 55]:
    root = insert(root, x)
print('search 55:', search(root, 55))
root = insert(root, 25)
print('predecessor 26:', predecessor(root, 26))
print('lower_bound 26:', lower_bound(root, 26))
print('range [25, 60):', list(between(root, 25, 60)))
root = delete(root, 40)
print('after delete 40:', list(between(root, 0, 100)))
print('replacement:', root.key, root.right.left.key)
chain = None
for x in range(1, 8):
    chain = insert(chain, x)
print('sorted insertion:', height(chain), len(search(chain, 7)[1]))

Output:

search 55: (True, [40, 60, 50, 55])
predecessor 26: 25
lower_bound 26: 30
range [25, 60): [25, 30, 40, 50, 55]
after delete 40: [10, 20, 25, 30, 50, 55, 60, 70]
replacement: 50 55
sorted insertion: 6 7

Append the following code to the same Python file. check_rb checks search order across each entire subtree, red-red edges, and equal black counts. It returns the black-node count starting at the current node, excluding NIL; the caller checks the black root separately.

def rotate_right(t):
    pivot = t.left
    assert pivot is not None
    t.left = pivot.right
    pivot.right = t
    return pivot


def check_rb(t, lo=float('-inf'), hi=float('inf')):
    if t is None:
        return 0
    assert lo < t.key < hi
    if t.red:
        assert t.left is None or not t.left.red
        assert t.right is None or not t.right.red
    left = check_rb(t.left, lo, t.key)
    right = check_rb(t.right, t.key, hi)
    assert left == right
    return left + int(not t.red)


rb = Node(30, Node(20, Node(10, red=True), red=True))
before = list(between(rb, 0, 100))
try:
    check_rb(rb)
except AssertionError:
    print('before: invariant fails')
rb = rotate_right(rb)
rb.red = False
rb.right.red = True
assert not rb.red
black_count = check_rb(rb)
assert list(between(rb, 0, 100)) == before
print('after:', rb.key, rb.left.key, rb.right.key)
print('order:', before)
print('height / black count:', height(rb), black_count)

Output from the appended portion:

before: invariant fails
after: 20 10 30
order: [10, 20, 30]
height / black count: 1 1

Choosing a tree, sorted array, or hash table

The Python bisect documentation distinguishes logarithmic insertion-point search from linear-time list insertion. The analysis of chained hashing separates expected lookup and deletion costs from amortized resizing costs. In the table, $n$ is the number of keys, $k$ the number of range results, and $B$ the number of hash-table buckets. Comparing, hashing, and moving one element are treated as constant-cost operations, and range endpoints satisfy $lo\le hi$. The resize amortization assumes geometric growth over an update sequence starting from an empty table.

Operation or property	Red-black search tree	Sorted array	Chained hash table
Exact lookup	Worst-case $O(\log(n+1))$	Worst-case $O(\log(n+1))$	Expected $O(1)$, worst-case $O(n)$
Insert or delete	Worst-case $O(\log(n+1))$	Worst-case $O(n)$; shifts a suffix	Expected $O(1)$ excluding resizing; resizing adds amortized $O(1)$
Predecessor or lower bound	Worst-case $O(\log(n+1))$	Worst-case $O(\log(n+1))$	$O(B+n)$ scan of buckets and keys without an ordered index
Report a range in order	$O(\log(n+1)+k)$	$O(\log(n+1)+k)$	$O(B+n)$ scan, plus sorting the results
Storage	Nodes, links, and colours; pointer traversal	Compact contiguous slots; good traversal locality	Buckets and spare capacity; no key order

Expected hash-table bounds require suitable hashing and controlled load. A single resize may still cost $O(n)$. A scan visits every bucket, including empty ones; it reduces to $O(n)$ when bucket capacity stays proportional to the current number of keys. A table that grows without shrinking can retain far more buckets than keys after many deletions. Tree bounds count comparisons and link operations; expensive string comparisons need their own accounting. For array shifts and locality, see arrays and dynamic arrays.

For frequent exact lookup alone, a hash table usually fits. A sorted array supports boundaries and ranges directly when data is sorted in batches and rarely updated. When updates continue alongside predecessor, lower-bound, or ordered range queries, a balanced search tree supports them in one representation.

My reading · Opened notes are remembered in this browser.