Binary search trees and balancing

Binary search in a sorted array finds a key in O(log n) steps, but keeping the array sorted makes every insertion and deletion cost O(n), because elements must shift to make room. A hash table, lesson 10, makes insertion and lookup fast but forgets the order of the keys entirely. The binary search tree combines the strengths: it keeps keys in sorted order, so it can answer range and nearest-key questions, while inserting, deleting and searching in time proportional to the tree's height. When the tree is kept balanced, that height is O(log n), and every operation is logarithmic. Balanced search trees are behind the ordered map types of most languages, such as std::map in C++ and TreeMap in Java, and their close relatives, B-trees, are behind nearly every database index and file system.

Northway's server needs exactly what a search tree offers. Analysts ask questions such as which vehicles passed node 0203 between 07:30 and 08:15, and what was the first record after 17:00. A hash table keyed by timestamp can answer whether a particular timestamp exists, but not which timestamps fall in a range. A sorted array could answer range queries, but each node sends hundreds of new records every few minutes, out of order when uploads are retried, and inserting them into a large sorted array is slow. Jonah's task is to understand the search tree well enough to choose the right library structure and to explain its behavior in the design review.

The search tree property

A binary search tree, or BST, is a binary tree in which each node holds a key, and for every node, all keys in its left subtree are smaller than its key and all keys in its right subtree are larger. Duplicates are either forbidden or sent consistently to one side. This single rule, applied at every node, has two consequences. An inorder traversal visits the keys in sorted order, as lesson 7 promised. And a search can discard a whole subtree at every step: compare the target with the root's key; if equal, stop; if smaller, the target can only be in the left subtree; if larger, only in the right. Each comparison moves one level down, so a search costs at most height + 1 comparisons.

# A simple (unbalanced) binary search tree keyed by timestamp in seconds of day
class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(root, key):
    if root is None:
        return Node(key)
    cur = root
    while True:
        if key < cur.key:
            if cur.left is None: cur.left = Node(key); return root
            cur = cur.left
        elif key > cur.key:
            if cur.right is None: cur.right = Node(key); return root
            cur = cur.right
        else:
            return root                   # duplicate: ignore

def search(root, key):
    steps, cur = 0, root
    while cur is not None:
        steps += 1
        if key == cur.key: return True, steps
        cur = cur.left if key < cur.key else cur.right
    return False, steps

def range_query(n, lo, hi, out):          # inorder, skipping subtrees outside [lo, hi]
    if n is None: return out
    if lo < n.key: range_query(n.left, lo, hi, out)
    if lo <= n.key <= hi: out.append(n.key)
    if n.key < hi: range_query(n.right, lo, hi, out)
    return out

root = None
for t in (27000, 25200, 29700, 24300, 26100, 28800, 30600, 27450):
    root = insert(root, t)
print("search 26100:", search(root, 26100))
print("search 26200:", search(root, 26200))
print("between 26000 and 28000:", range_query(root, 26000, 28000, []))

search 26100: (True, 3)
search 26200: (False, 3)
between 26000 and 28000: [26100, 27000, 27450]

The range query is the operation that justifies the tree. It is an inorder traversal that refuses to enter a subtree when every key there must be outside the range: if the current key is already below the low end, nothing in its left subtree can qualify. Its cost is O(h + k), where h is the height and k is the number of keys reported. For a balanced tree that is O(log n + k), which is as good as possible, since the answer itself has k items. Finding the smallest key greater than or equal to a given value, the successor query that answers first record after 17:00, works the same way: walk down, remembering the last node where you went left.

Insertion and deletion

Inserting a key follows the same path as an unsuccessful search and attaches a new leaf where the search fell off the tree, so it also costs O(h). Deleting is the one operation that needs care, because removing an internal node would leave its children without a parent. There are three cases. A leaf is simply removed. A node with one child is replaced by that child, which keeps the search property because the whole subtree lay on the correct side of the node's parent. A node with two children is handled by finding its inorder successor, the smallest key in its right subtree, which is the leftmost node there and has no left child; copy the successor's key into the node, then delete the successor, which falls into one of the two easy cases.

The problem: unbalanced trees

Every BST operation costs O(h), and lesson 7 showed that h can be anywhere from about log₂ n to n − 1. Which shape a plain BST gets depends entirely on the order in which keys arrive. Random order gives a tree whose expected height is about 2.99·log₂ n, comfortably logarithmic. But sorted order, the most natural order for timestamps, gives the worst shape possible: each new key is larger than all the others, so it becomes the right child of the previous one, and the tree degenerates into a linked list leaning to the right. A search then costs O(n), and the tree has the costs of a list with the overhead of a tree.

Balanced search trees and rotations

A self-balancing search tree performs a little extra work during insertions and deletions to keep its height O(log n) whatever order the keys arrive in. The basic tool is the rotation, a local rearrangement of three nodes and their subtrees that changes the tree's shape while preserving the search property. In a right rotation at node y with left child x, x moves up to take y's place, y becomes x's right child, and x's former right subtree, whose keys lie between x and y, becomes y's left subtree. A left rotation is the mirror image. A rotation changes only a constant number of pointers, so it costs O(1), and it shortens the side that was too tall by one level.

The AVL tree, invented by Georgy Adelson-Velsky and Evgenii Landis in 1962, was the first self-balancing search tree. Each node records its height, and the tree maintains the rule that the heights of every node's two subtrees differ by at most one. After an insertion or deletion, the heights along the path back to the root are updated, and any node that violates the rule is fixed by one rotation or by two rotations in sequence, a double rotation, depending on whether the tall grandchild is on the outside or the inside. The rule guarantees that an AVL tree's height is less than about 1.44·log₂ n, so every operation is O(log n) in the worst case.

The red-black tree, which appeared in the 1970s in work by Rudolf Bayer and by Leonidas Guibas and Robert Sedgewick, relaxes the balance rule to make updates cheaper. Each node is marked red or black, the root and the null leaves are black, a red node never has a red child, and every path from a node down to a leaf passes the same number of black nodes. These rules allow the longest path to be at most twice the shortest, so the height is at most 2·log₂(n + 1). Insertions and deletions fix any violation by changing node colors and with at most two or three rotations. AVL trees are a little shorter and so slightly faster to search; red-black trees rebalance less often, which makes them a common choice for general-purpose libraries. The C++ standard library's map, Java's TreeMap and the Linux kernel's scheduler and memory manager all use red-black trees.

# Height of a plain BST versus an AVL tree for keys arriving in sorted order
import math

def plain_height(keys):
    # a plain BST fed strictly increasing keys degenerates into a chain
    return len(keys) - 1

class AVL:
    __slots__ = ("k", "l", "r", "h")
    def __init__(self, k): self.k, self.l, self.r, self.h = k, None, None, 0

def h(n): return n.h if n else -1
def fix(n): n.h = 1 + max(h(n.l), h(n.r)); return n
def rot_right(y):
    x = y.l; y.l = x.r; x.r = y; fix(y); return fix(x)
def rot_left(x):
    y = x.r; x.r = y.l; y.l = x; fix(x); return fix(y)

def insert(n, k):
    if n is None: return AVL(k)
    if k < n.k: n.l = insert(n.l, k)
    else: n.r = insert(n.r, k)
    fix(n)
    bal = h(n.l) - h(n.r)
    if bal > 1:
        if k > n.l.k: n.l = rot_left(n.l)      # inside case: double rotation
        return rot_right(n)
    if bal < -1:
        if k < n.r.k: n.r = rot_right(n.r)
        return rot_left(n)
    return n

for n in (100, 1000, 40000):
    root = None
    for k in range(n):
        root = insert(root, k)
    print(f"n = {n:>6,}: plain BST height {plain_height(range(n)):>6,}, "
          f"AVL height {root.h:>2}, log2 n = {math.log2(n):.1f}")

n =    100: plain BST height     99, AVL height  6, log2 n = 6.6
n =  1,000: plain BST height    999, AVL height  9, log2 n = 10.0
n = 40,000: plain BST height 39,999, AVL height 15, log2 n = 15.3

Inserting 40,000 sorted keys gives an AVL tree of height 15, the minimum possible for that many nodes, while a plain BST would have height 39,999. The AVL code is short because recursion carries the path back up to the root, where heights are updated and rotations applied on the way out; the recursion depth is only the tree's height, so it is perfectly safe here. Real implementations are iterative and handle deletion as well, but the principle is the same.

B-trees: search trees for storage

On disk or flash, reading one node costs far more than comparing keys, because storage is read in blocks of 4 KB or more. A binary tree of a billion keys needs about 30 node reads per search, each potentially a separate block read. A B-tree instead stores hundreds of keys in each node, sized to fill one block, with one more child pointer than keys. Its height is then only three or four levels for a billion keys, and the top levels usually stay in memory. B-trees, and the B+ tree variant that keeps all records in the leaves linked for fast range scans, are the index structure of relational databases and of file systems such as NTFS, ext4's directory indexes and Apple's APFS. Northway's server stores vehicle records in a database whose timestamp index is a B+ tree, which is why Jonah's range queries return in milliseconds over a year of data.

-- The server's records table: the primary key and the index are both B+ trees
CREATE TABLE vehicle_rec (
    node_id    INTEGER  NOT NULL,
    ts         BIGINT   NOT NULL,   -- milliseconds since the epoch
    lane       SMALLINT NOT NULL,
    speed_dkmh SMALLINT NOT NULL,
    vclass     SMALLINT NOT NULL,
    PRIMARY KEY (node_id, ts)
);

-- Range query answered by walking the B+ tree: O(log n + k)
SELECT ts, lane, speed_dkmh, vclass
FROM vehicle_rec
WHERE node_id = 203
  AND ts BETWEEN 1793516400000 AND 1793519100000
ORDER BY ts;