Chapter 10: Search Trees

10.1Search trees

Nobody looks up “Smith” in a phone book by starting at page one. You open it in the middle, see which half the name is in, and discard the other, which works only because the book is sorted. On a computer this is binary search: about log₂ n comparisons among n sorted elements.

The weakness of a sorted array is updating: adding an entry shifts everything after it, n moves in the worst case. A linked list inserts and deletes cheaply but cannot jump to its middle, so a search steps through it one element at a time. Search trees sit in between. Being linked, they update by changing a few links; being ordered, they let each search step eliminate part of the candidates.

10.1.1What is a search tree?

First, the vocabulary. A tree consists of nodes joined by edges. The topmost node is the root; nodes without children are leaves. The depth of a node is the number of edges from the root down to it, so the root has depth 0, and the height h of the tree is the depth of its deepest node. A single node has height 0; the empty tree, by convention, −1.

Each node of a search tree holds an element with a key, a comparable value that identifies it: a student ID, a dictionary word, a surname. The rest of the element (name, address, GPA) is stored alongside. To keep examples simple, our keys are mostly integers and nodes hold nothing else.

That last sentence is the whole chapter in brief. Search, insertion and deletion each follow one path down from the root, at most as long as the height, so they cost O(h): fast while the tree stays short, slow when it grows tall.

How tall can an n-node tree be? At worst every node has one child, the tree is a chain, and the height is n − 1. At best every level is full. Depth d holds at most 2^d nodes, so a binary tree of height h has at most 1 + 2 + 4 + … + 2^h = 2^h+1 − 1 nodes, and n ≤ 2^h+1 − 1 gives h ≥ log₂(n + 1) − 1: about log₂ n.

This gap is why the rest of the chapter exists. A plain BST promises nothing about height. AVL and red-black trees repair themselves locally after each update and guarantee h = O(log n). A splay tree meets that bound on average over long sequences, and a B-tree packs many keys per node, making the tree short and wide.

10.1.2Basic operations

A search tree offers what any sorted collection does. Table 10.1 lists the operations and our method names.

The order supports further queries: the minimum and maximum key; the successor of a key (the smallest larger key) and its predecessor (the largest smaller key); and all keys within a range. Each follows a single path from the root, so everything except traversal takes O(h); traversal visits every node once, in O(n).

A hash table also searches and inserts in constant average time; ordered queries are what set a search tree apart. Because a hash table scatters its keys, questions like “the smallest key above 50” or “the keys from 20 to 45, in order” force it to scan everything. A search tree answers them in O(h) or O(h + s), where s is the number of keys returned.

10.1.3Kinds of search trees

We cover four kinds of binary search tree and two multiway trees. The binary kinds share one ordering rule and differ in how, and how tightly, they control height. Figure 10.2 shows a small example of each.

• Binary search tree (BST): each key is greater than every key in its left subtree and smaller than every key in its right subtree. No balance guarantee; the shape depends on insertion order.
• AVL tree: at every node the subtree heights differ by at most 1 (the balance factor); rotations restore the condition when it breaks.
• Red-black tree: nodes are red or black, and color rules bound the height by 2 log₂(n + 1).
• Splay tree: rotations move each accessed node to the root. One operation can be costly, but the amortized cost is O(log n).

In multiway trees (B-trees and B+ trees) a node holds several keys and more than two children. Designed mainly for data on disk, they are the subject of Section 10.7.

10.2Binary search trees

In a binary tree each node has at most two children, left and right. A binary search tree adds an ordering rule that makes it behave like a “linked” sorted array.

10.2.1The BST property

“All” matters: the condition relates a node to every descendant, not just its children. In Figure 10.3, the left tree is a valid BST; in the right one, 7 has been added as the right child of 4. That pair is fine, but 7 lies in the left subtree of 6 while being larger than 6, so the tree is not a BST.

So a node's key splits its subtree in two, smaller keys left and larger right, like the middle element of a sorted array. As binary search halves its range, a BST search knows at each node which side to take and discards the other.

Can a key appear twice? Not under this definition, with its strict inequalities. In practice you either reject duplicates, as our code does, or consistently send equal keys to one side, say the right. Search, insertion and deletion must follow the same rule, or an inserted key may never be found again.

10.2.2Node structure

A BST node has three fields: the data (the key) and references to its left and right children (Figure 10.4). A missing child is null, so a leaf has two null references. Compared with a linked-list node, there are two child references instead of one “next.”

The slides write the node in two forms. The first holds only an int key:

class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

The constructor stores the data and sets both children to null, which Java does anyway; the assignments just show intent. The successor, range query and validation code use this class, with the short field names left and right.

The second form is a generic class. The key need not be an integer; any comparable type will do:

class BinaryTreeNode<E extends Comparable<E>> {
    E data;                    // element
    BinaryTreeNode<E> leftChild; // left child
    BinaryTreeNode<E> rightChild; // right child

    BinaryTreeNode(E data) {
        this.data = data;
        // children start out null
    }
}

The bound E extends Comparable<E> means two E objects can be compared with compareTo. Integer, String and LocalDate implement Comparable, so any of them can be a key. a.compareTo(b) is negative if a < b, 0 if equal, and positive if a > b; search, insertion and deletion look only at this sign. Here the fields are leftChild and rightChild.

Each node carries two references besides its data, so n nodes take O(n) memory. Balanced trees add a constant per node, a height for AVL or a one-bit color for red-black, and total memory stays O(n).

10.2.3Minimum and maximum keys

The BST property tells us where the extremes are. A node with a left child cannot be the minimum, since something smaller is on its left. So the minimum is found by going left from the root until a node has no left child, and the maximum by going right (Figure 10.5).

The slides give both methods together:

BinaryTreeNode<E> minValue(
        BinaryTreeNode<E> node) {
    while (node.leftChild != null)
        node = node.leftChild; // go left
    return node;  // minimum
}
BinaryTreeNode<E> maxValue(
        BinaryTreeNode<E> node) {
    while (node.rightChild != null)
        node = node.rightChild; // go right
    return node;  // maximum
}

minValue starts at the given node and, while it has a left child, moves node there; when the left child is null, it returns the current node. maxValue does the same on the right. Both assume a nonempty tree: if node starts as null, node.leftChild throws a NullPointerException.

No keys are compared; the methods just follow links, one level per iteration, so they take at most h iterations, O(h) time, and O(1) extra memory.

Taking any node rather than the root is deliberate: deletion calls minValue on the right subtree of a two-child node to find its replacement. The same method serves for the whole tree or any subtree.

10.2.4Code trace: minValue and maxValue

We trace the tree of Figure 10.5, built by inserting 6, 2, 8, 1, 4, 3: root 6 with children 2 and 8; 2 with children 1 and 4; 4 with left child 3. Table 10.2 shows node and the condition in each iteration.

Note that the deepest node, 3, is not the minimum: it is left of 4, which is right of 2, so 3 > 2. The minimum is in the leftmost node, not the deepest. Figure 10.6 shows three moments of minValue and the result of maxValue.

10.2.5Inorder traversal

A traversal visits every node in a fixed order. Binary trees have three classic recursive orders, preorder, inorder and postorder, named for when the root is visited relative to its subtrees. Inorder visits the left subtree, then the root, then the right subtree.

void inorder(BinaryTreeNode<E> d) {
    if (d == null) return;
    inorder(d.leftChild);  // left
    System.out.print(d.data + " ");
    inorder(d.rightChild);  // right
}

On an empty subtree (d == null) the method returns at once: the base case. Otherwise its three lines traverse the left subtree, print the node's data, and traverse the right subtree.

In a BST this order prints the keys in increasing order. Take any node: its whole left subtree, all smaller keys, is printed before it, and its right subtree, all larger keys, after it. Every node thus comes after all smaller keys and before all larger ones, which is exactly sorted output.

The converse holds too: a binary tree whose inorder traversal is strictly increasing is a BST. So one way to check a tree is to traverse it inorder and test that the output increases.

Each node is printed once and makes two recursive calls, O(n) calls in all (n nodes produce n + 1 empty calls), so the time is O(n). The stack holds at most h + 2 frames, counting the empty call: O(h) memory.

10.2.6Code trace: inorder

inorder(root) on the same tree produces the events of Table 10.3. “Pending” lists, bottom to top, the nodes on the call stack waiting for their left subtrees.

The output 1 2 3 4 6 8 is sorted. 6 is called first but printed fifth, since its four smaller keys are all in its left subtree; 8 is called last and printed last. Figure 10.7 shows four moments.

10.3BST operations

All BST operations share one skeleton: start at the root, compare, go left if smaller and right if larger. They differ in where they stop and what follows. Search stops at an equal key or an empty link; insertion hangs a new node on the empty link; deletion removes the found node in one of three ways, depending on its children.

10.3.1Search

Search follows three rules:

1. Start at the root. If the node's key equals the target, the search succeeds.
2. If the target is smaller, repeat in the left subtree; if larger, in the right subtree.
3. If you reach a null link, the key is not in the tree.

The third rule follows from the BST property: a key in the tree must lie in the subtree chosen at each step, since the other subtree's keys are all smaller or all larger. If that subtree is empty, the key is nowhere.

The slides give a recursive search on the generic node class:

boolean search(BinaryTreeNode<E> root, E data) {
    if (root == null)
        return false;            // absent
    int k = data.compareTo(root.data);
    if (k == 0)
        return true;             // found
    else if (k < 0)
        return search(root.leftChild, data);
    else
        return search(root.rightChild, data);
}

The first if is the base case: an empty subtree has no keys, so the answer is false. Otherwise the target is compared once with the node's data, the result is kept in k, and the method returns true for k == 0 or recurses left for k < 0 and right for k > 0, passing the result up unchanged.

Comparing once and saving the result is clearer and cheaper: compareTo may be costly for a String or a complex object, and two ifs would call it twice.

Each call descends one level with constant work. A successful search examines one node more than the found node's depth; an unsuccessful one at most h + 1. Both are O(h), using O(h) stack. Since the recursive call comes last, a while loop assigning root = root.leftChild or root = root.rightChild does the same in O(1) extra memory.

10.3.2Code trace: search

We trace a successful search(root, 5) and an unsuccessful search(root, 10) on the tree of Figure 10.8, 6(4(2, 5), 8(7, 9)). Each call opens a new stack frame.

The successful search compared three nodes, one more than the depth of 5. The unsuccessful one also examined three (6, 8, 9) before its fourth call hit an empty link. With height 2, no search can exceed h + 1 = 3 comparisons, and both reached that bound; an unsorted array of the same seven keys would need seven for a miss.

10.3.3Insertion

A new key goes where a search for it ends: at a null link. Every node on the way sent the search to the correct side, so that link is the only place the key fits without breaking the BST property. The new node becomes a leaf there.

BinaryTreeNode<E> insert(
        BinaryTreeNode<E> root, E data) {
    if (root == null)
        return new BinaryTreeNode<>(data);
    int k = data.compareTo(root.data);
    if (k < 0)
        root.leftChild = insert(root.leftChild, data);
    else if (k > 0)
        root.rightChild = insert(root.rightChild, data);
    // k == 0: key already present, not inserted
    return root;
}
// usage: root = insert(root, 5);

The key feature is the return value: insert returns the root of its subtree after the insertion. For an empty subtree it creates and returns the new node, now that subtree's root. Otherwise the root stays the same: the method updates a child link with the recursive result and returns its own root.

The line root.leftChild = insert(root.leftChild, data) looks redundant, since the child is already there. Only the assignment at the bottom does real work: in the new node's parent, root.rightChild is still null, and the assignment links in the returned node. Elsewhere each link is rewritten with its own value. These “redundant” assignments save the code from tracking the parent.

The caller follows the same pattern, root = insert(root, 5);. For an empty tree, the first insertion creates the root, and only this assignment stores it.

An equal key (k == 0) skips both ifs, so the method returns root unchanged and no duplicate is inserted. Insertion costs the same as search, O(h) time and O(h) stack. The new node is always a leaf and existing nodes never move, which is also why a plain BST's shape depends entirely on insertion order.

10.3.4Code trace: insert

We insert 5 into the tree of Figure 10.10 with root = insert(root, 5). Table 10.5 shows the descent and the return, with the value each frame assigns to its child link.

The result is 6(2(1, 4(3, 5)), 8), with inorder 1 2 3 4 5 6 8. Three frames opened and closed, and only the right link of 4 really changed. Figure 10.11 shows the new node being created and linked.

10.3.5Successor, predecessor, ceiling and floor

Each element of a sorted list has a “next” and a “previous” neighbor; in a BST they are the successor and the predecessor.

For x in the tree there are two cases (Figure 10.12):

1. With a right subtree, the successor is its minimum: right once, then left all the way. The keys just above x are in that subtree, and the smallest of them is the successor.
2. Without a right subtree, it is the nearest ancestor that the root-to-x path passes on its left. The path to 5 is 6 → 4 → 5: it turns left at 6, so 5 < 6, and right at 4, so 4 < 5 cannot qualify. The successor is 6.

The code merges both cases into one loop down from the root that keeps the “best candidate so far”:

TreeNode successor(TreeNode root, int x) {
    TreeNode candidate = null; // smallest key greater than x
    while (root != null) {
        if (x < root.data) {
            candidate = root;     // root is a candidate
            root = root.left;  // anything smaller is on the left
        } else
            root = root.right;  // keys greater than x are on the right
    }
    return candidate;
}

At each node, if x < root.data, the node is larger than x and a candidate; a better one, larger than x but smaller than this node, can only be on its left, so we record it and go left. If x ≥ root.data, the node and its left subtree are all at most x and cannot qualify, so we go right. The loop ends at an empty link and returns the last candidate, or null if there was none, meaning no key exceeds x.

Both cases come out automatically. With a right subtree, the loop passes x, goes right once, then left while collecting candidates, ending at that subtree's minimum. Without one, the loop ends right after x, and the last candidate is the nearest ancestor passed on its left. The code does not even need x to be in the tree.

The successor has three relatives, listed in Table 10.6; Java's TreeMap and TreeSet provide all four.

The predecessor mirrors the successor: if x > root.data, record the node and go right; otherwise go left. Ceiling differs from successor only on equality: for x in the tree, the ceiling is x itself, the successor the next key. Floor is likewise predecessor with equality allowed. Since 3 is absent from the example tree, ceiling(3) = 4 and floor(3) = 2. All four follow one path, in O(h).

10.3.6Code trace: successor

successor(root, 5) and successor(root, 6) illustrate the two cases. Each row of Table 10.7 is one loop iteration.

In the first call the candidate, found at the root, never changes: 5 has no right subtree, so its successor is the ancestor 6. In the second it becomes 8, then 7, the minimum of the right subtree of 6. Each call examines three nodes. Figure 10.13 shows four moments.

10.3.7Deletion: three cases

Deletion is the most delicate BST operation. A search finds the node in O(h), which is then removed, according to its number of children, without breaking the BST property. The examples use the tree of Figure 10.14.

1. Leaf. Set the parent's link to null. Deleting 70 nulls the right link of 60.
2. One child. Link the parent directly to the only child. Deleting 45 points 40 at 42; deleting 60 points 50 at 70.
3. Two children. The parent has one link to offer but the node has two children, so it cannot be removed directly. Instead, replace the node's value with that of its inorder successor (minimum of the right subtree) or predecessor (maximum of the left subtree), then delete that node from its own position. Example: deleting 40.

The one-child case clearly preserves the BST property. 45 and all its descendants lie in the right subtree of 40 and exceed 40, so linking 42 to the right of 40 changes nothing; 42 also stays in the left subtree of 50, below 50. The subtree simply moves up a level, its order intact.

Why the successor? The replacement must exceed everything in the left subtree and be smaller than everything in the right. The keys adjacent in inorder, predecessor and successor, both qualify. The successor of 40 is 42: as the minimum of the right subtree it is below the other keys there, and being above 40 it exceeds the whole left subtree. Putting 42 in place of 40 keeps the BST property.

Deleting the successor from its old position is always easy. It was found by going left in the right subtree until there was no left child, so it is a leaf or has only a right child: Case 1 or Case 2. The recursion never meets a two-child node again.

10.3.8The deletion code

With the same “return the subtree's new root” pattern as insertion, one recursive method handles all three cases:

BinaryTreeNode<E> delete(
        BinaryTreeNode<E> root, E data) {
    if (root == null) return null;   // absent
    int k = data.compareTo(root.data);
    if (k < 0)
        root.leftChild = delete(root.leftChild, data);
    else if (k > 0)
        root.rightChild = delete(root.rightChild, data);
    else if (root.leftChild == null)
        return root.rightChild;  // leaf/right child
    else if (root.rightChild == null)
        return root.leftChild;  // left child only
    else {                    // two children
        root.data = minValue(root.rightChild).data;
        root.rightChild = delete(root.rightChild, root.data);
    }
    return root;
}

The first half is a search. If the key is absent (root == null), it returns null, leaving the tree unchanged. For k < 0 or k > 0 it recurses into the corresponding subtree and assigns the result to the child link.

At k == 0 the node is found, and three branches handle the cases:

• If root.leftChild == null, return root.rightChild. This covers two cases: for a leaf it returns null, emptying the parent's link; for a node with only a right child it returns that child, which the parent then links to directly.
• If root.rightChild == null (left child only), return the left child.
• With two children, minValue(root.rightChild) finds the successor, whose value is copied into the node; delete(root.rightChild, root.data) then removes the successor, since root.data now holds its value.

The node is detached when the returned value is assigned to the parent's link: in the leaf and one-child cases the method returns the node's replacement, and the reference to the deleted node disappears, leaving it for the garbage collector. Calls are written root = delete(root, 40);, since a deleted root can only be replaced through this assignment.

The descent costs O(h). In the two-child case minValue and the second delete continue below the node, together within O(h). Deletion takes O(h).

10.3.9Code trace: three deletions

All three start from the tree of Figure 10.14; Table 10.8 shows the comparisons and returned links.

The inorder sequences of the results are 30 40 42 45 50 60, 30 40 42 50 60 70 and 30 42 45 50 60 70: the deleted key is gone, the rest in order. The root never changed; root = delete(…) in main wrote back 50 each time.

The third trace runs one deletion inside another; Table 10.9 shows it step by step.

The node object holding 40 never left the tree; only its value became 42. What was detached is the leaf holding the old 42. Figure 10.17 shows three moments and the result.

10.3.10Analysis of BST operations

Every operation so far costs time proportional to the depth of the deepest node it reaches, at worst the height: O(h). So the real question is how tall a BST with n keys gets.

That depends on insertion order. Inserting 4, 2, 6, 1, 3, 5, 7 gives a perfect tree of height 2. Inserting 1, 2, …, 7 puts each key right of the previous one, producing a chain of height 6. Such a degenerate tree is just a linked list that wastes memory.

The middle row is encouraging. With random insertion order, the average depth is about 2 ln n ≈ 1.39 log₂ n, some 28 comparisons for a million keys, only about 40% above the best case. The expected height is larger, about 4.31 ln n ≈ 2.99 log₂ n, around 60 for a million keys; the table's height column shows this, its last column the average depth. The analysis matches quicksort's: each key, on becoming a root, splits the rest into two random groups.

Real data, however, is seldom random. Records from a file may be sorted already, student IDs grow with enrollment, timestamps only increase. Such input drives a plain BST to its worst case, with every operation O(n), and inserting n sorted keys costs 1 + 2 + … + (n − 1) = n(n − 1)/2 = O(n²) comparisons: half a trillion for a million keys.

10.3.11Range queries

A range query reports, in order, every key in [lo, hi]: “keys between 5 and 10,” or “students with a GPA from 2.5 to 3.0.” Traversing the whole tree inorder works but takes O(n) however few keys qualify. The BST property lets us do far better by never entering a subtree that cannot hold a key in range, a technique called pruning.

void range(TreeNode k, int lo, int hi) {
    if (k == null) return;
    if (lo < k.data)           // candidates on the left
        range(k.left, lo, hi);
    if (lo <= k.data && k.data <= hi)
        System.out.print(k.data + " ");
    if (k.data < hi)           // candidates on the right
        range(k.right, lo, hi);
}

This is inorder traversal pruned by two tests. All left-subtree keys are below k.data, so if k.data ≤ lo none can be in range and the left subtree is skipped; likewise, if k.data ≥ hi, the right subtree is skipped. The middle if prints the node when it is in range, and the left–node–right order keeps the output sorted.

Table 10.11 traces range(root, 5, 10) on 8(4(2, 6(5, 7)), 12(10, 14)).

The output 5 6 7 8 10 is sorted. The visited nodes are 8, 4, 6, 5, 7, 12, 10; 2 and 14 were never visited, because 4 was already below the lower bound and 12 above the upper. Figure 10.19 shows the start and end of the trace.

For the cost, split the visited nodes into the s nodes in range, all printed, and the others, which lie on the two paths toward the ends of the range, each of at most h + 1 nodes. The total is O(h + s): in a balanced tree of a million keys, a 10-key range takes a few dozen node visits.

10.3.12Is a tree a BST?

To check whether a binary tree is a BST, remember that the property applies to whole subtrees: each node must agree with all its ancestors, not just its parent. Going left adds an upper bound, going right a lower bound, and every node must lie within all the bounds on its path from the root.

boolean isBST(TreeNode k, long min, long max) {
    if (k == null) return true;
    if (k.data <= min || k.data >= max)
        return false;          // out of range
    return isBST(k.left, min, k.data)
        && isBST(k.right, k.data, max);
}
// first call: isBST(root, Long.MIN_VALUE,
//                   Long.MAX_VALUE)

Each node receives an allowed interval (min, max). The root's is unbounded, with Long.MIN_VALUE and Long.MAX_VALUE standing in for ±∞; since keys are ints, these long values never equal a key. A node outside its interval yields false; otherwise its value becomes the upper bound for its left child and the lower bound for its right, and the two results are joined with &&.

Table 10.12 checks the faulty tree on the right, 6(2(1, 4(3, 7)), 8).

The interval for 7 is (4, 6): the lower bound because 7 is right of 4, the upper bound because 7 is in the left subtree of 6, a bound carried two levels down from the root. A parent–child check would accept this tree, since 4 < 7. The correct check visits each node once: O(n) time, O(h) stack.

10.3.13Application: student records

Real applications store whole records in nodes. In the slides' example the key is the student ID and the node holds the entire student object:

public class Student {
    int id;     // key
    String fullName;

    public Student(int id,
                   String fullName) {
        this.id = id;
        this.fullName = fullName;
    }
}

public class StudentNode {
    Student st;           // data
    StudentNode leftChild;
    StudentNode rightChild;

    public StudentNode(Student st) {
        this.st = st;
        // children start out null
    }
}

Student holds the data and StudentNode the tree structure, so the same student object can also live in another structure, a list for example. Insertion and search mirror the integer versions:

StudentNode insert(StudentNode root, Student st) {
    if (root == null) return new StudentNode(st);
    if (st.id < root.st.id)
        root.leftChild = insert(root.leftChild, st);   // continue left
    else if (st.id > root.st.id)
        root.rightChild = insert(root.rightChild, st);   // continue right
    return root;                                   // duplicate ID not inserted
}

Student search(StudentNode root, int id) {
    if (root == null) return null;                // no record
    if (id == root.st.id) return root.st; // found
    if (id < root.st.id)
        return search(root.leftChild, id);         // continue left
    return search(root.rightChild, id);             // continue right
}

With an int key, comparisons use <, > and == directly rather than compareTo. And search returns the student object, with the name and other fields, or null, instead of a boolean.

Java's TreeMap<Integer, Student> does this job out of the box. It maps keys to values using a red-black tree internally: put, get and remove take O(log n), and higherKey, floorKey and subMap answer successor, floor and range queries. Unlike a hand-written BST, it never degenerates, even on sorted input.

10.4Balance and AVL trees

BST operations take O(h), and h can reach n − 1. Is there a cheap way to keep the height O(log n) no matter what? Yes; Adelson-Velsky and Landis showed the first in 1962.

10.4.1Why balance matters

A plain BST's shape follows the insertion order: 1, 2, 3, 4 gives a chain of height 3, yet the same keys fit in trees of height 2, such as 2(1, 3(—, 4)) and 3(1(—, 2), 4) (Figure 10.21). All three trees have inorder 1 2 3 4; they hold the same sorted set in different shapes.

“Local” is the key word. Rebuilding an unbalanced tree from its inorder sequence would work but costs O(n) per update, destroying the tree's advantage. Balanced trees touch only a few nodes on the updated path, which has length O(log n), with constant work per node, so updates stay O(log n).

10.4.2A balancing example

A larger example shows local repair at work. The tree on the left of Figure 10.22 holds 11 keys; its branches 9 → 14 → 12 and 76 → 54 → 72 → 67 have grown long, giving height 4. Rearranging those two subtrees fits the keys into height 3, with 12 and 72 as new subtree roots.

Rearranging leaves the inorder sequence, 9 12 14 17 19 23 50 54 67 72 76, unchanged; only parent–child relations change. In the left subtree of 17, the median of 9, 14, 12 became the root with 9 and 14 as children. On the right, 54, 72, 67 and 76 were rearranged and the middle key, 72, moved up. The rest of the tree was untouched.

AVL and red-black trees make such repairs automatically. An update can disturb only its own path, and the repair runs along that path from the bottom up.

10.4.3AVL trees and the balance factor

The AVL tree, named after the Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis and published in 1962, was the first self-balancing binary search tree. Its idea is simple: at every node, the two subtree heights differ by at most 1.

A positive balance factor means “left-heavy,” a negative one “right-heavy.” A leaf has bf = −1 − (−1) = 0; a node with only a left child, bf = 0 − (−1) = 1. This is why an empty subtree must count as −1: with 0, a leaf and a one-child node would look alike.

The right-hand tree has two unbalanced nodes. We fix the lowest, the one nearest the new node, here 20. That shortens its subtree by one, and 30 rebalances by itself.

Each AVL node stores its height, and balance factors are computed from the children's heights. Insertion and deletion proceed as in a plain BST; then, as the recursion unwinds, each node on the path updates its height and checks its balance factor, and a node with |bf| = 2 is fixed by rotation.

10.4.4Why is AVL height O(log n)?

The AVL condition is local, so to see that it bounds the height, ask the reverse: how few nodes, N(h), can an AVL tree of height h have? In such a sparsest tree one subtree of the root has height h − 1, the other the least allowed, h − 2, and both are sparsest trees themselves. Hence:

N(0) = 1,   N(1) = 2,   N(h) = 1 + N(h − 1) + N(h − 2)

These numbers grow like Fibonacci numbers; in fact N(h) = F(h + 3) − 1 (with F(1) = F(2) = 1), so N(h) grows exponentially. A simple bound: since N(h − 1) > N(h − 2), N(h) = 1 + N(h − 1) + N(h − 2) > 2 · N(h − 2), so the count at least doubles every two levels, and N(h) > 2^h/2.

So an AVL tree is at worst about 44% taller than a perfectly balanced one; with a million keys its height never exceeds 28, compared with a million-long chain for a plain BST.

10.4.5Rotations

The basic repair tool is the rotation, which reverses the parent–child relation between a node and one of its children: the child moves up, the old parent down. To preserve the BST property, one subtree changes owner.

In a right rotation, y is the parent and x its left child, with subtrees T1 and T2; T3 is the right subtree of y. The inorder sequence is T1, x, T2, y, T3. Afterward x is on top with right child y; T1 and T3 keep their places, and T2, whose keys lie between x and y, becomes the left subtree of y. The sequence is unchanged.

The three links: the left link of y now points to T2, the right link of x to y, and the parent's link to x instead of y. Three assignments suffice for any tree size. T1 rises a level, T3 drops one, T2 stays put, so if T1 is the heavy side of a left-heavy node, a right rotation evens things out.

10.4.6Single rotations: LL and RR

Let z be the lowest unbalanced node after an insertion. There are four cases, named for the first two steps from z toward the new node (L for left, R for right). In LL the new node went into the left subtree of the left child of z; RR is the mirror image. Here z and its child lean the same way, and one rotation suffices.

LL shows up as bf(z) = 2 (left-heavy) with the left child at 1 or 0; the fix is a right rotation at z. RR shows up as bf(z) = −2 with the right child at −1 or 0; the fix is a left rotation at z.

After an insertion, a single rotation returns the subtree to its pre-insertion height. In Figure 10.26, the subtree of 30 had height 1, the insertion of 10 made it 2, and the rotation restored 1. Ancestors never see a change, so one repair per insertion suffices.

10.4.7Double rotations: LR and RL

In the other two cases the new node ends a “zigzag.” In LR it went into the right subtree of the left child of z: z leans left, its child right, and the three nodes form a triangle. A single right rotation at z merely flips the triangle, leaving the tree unbalanced.

The fix takes two rotations: left at the child, straightening the triangle into the LL case, then right at z. The median of the three keys ends on top with the smaller on its left and the larger on its right. RL is the mirror image.

10.4.8The AVL code

An AVL node holds a key, a height and two child references. The slides first give three helpers and the right rotation:

int h(AvlNode d) {
    return d == null ? -1 : d.height;
}
int bf(AvlNode d) {
    return h(d.left) - h(d.right);
}
void update(AvlNode d) {
    d.height = 1 +
        Math.max(h(d.left), h(d.right));
}
AvlNode rotateRight(AvlNode y) {
    AvlNode x = y.left;
    y.left = x.right;  // T2 → y.left
    x.right = y;       // y → x.right
    update(y);         // lower node first
    update(x);
    return x;          // new root
}

h returns −1 for an empty subtree, sparing other methods a null check; bf is the difference of the children's heights; update recomputes a node's height from its children's, which must already be correct, so heights are always updated bottom-up.

rotateRight(y) codes Figure 10.25: x is the rising left child, y.left = x.right moves T2, and x.right = y reverses the relation. y is updated before x, since y is now the child and the height of x depends on it. The method returns the new subtree root x, which the caller assigns to the parent's link, the third link.

The slides abbreviate the left rotation as the “left ↔ right mirror”; in full:

AvlNode rotateLeft(AvlNode x) {
    AvlNode y = x.right;
    x.right = y.left;  // T2 → x.right
    y.left = x;        // x → y.left
    update(x);         // lower node first
    update(y);
    return y;          // new root
}

rebalance combines the four cases:

AvlNode rebalance(AvlNode d) {
    update(d);
    if (bf(d) > 1) {       // left-heavy
        if (bf(d.left) < 0)  // LR
            d.left = rotateLeft(d.left);
        return rotateRight(d); // LL
    }
    if (bf(d) < -1) {      // right-heavy
        if (bf(d.right) > 0)  // RL
            d.right = rotateRight(d.right);
        return rotateLeft(d); // RR
    }
    return d;
}
// rotateLeft: mirror of left ↔ right
// insert/delete as in a BST; on return:
//   return rebalance(root);

rebalance(d) updates the height of d. If the node is left-heavy (bf > 1) and its left child leans right, the case is LR: rotate left at the child, storing the result in d.left. In both cases, then rotate right at d. The right-heavy case mirrors this; a balanced node is returned as is.

Insertion changes only the last line of the BST version:

AvlNode insert(AvlNode d, int k) {
    if (d == null) return new AvlNode(k);
    if (k < d.key)
        d.left = insert(d.left, k);
    else if (k > d.key)
        d.right = insert(d.right, k);
    else return d;          // no duplicates
    return rebalance(d);
}

return rebalance(d) replaces return d, so as the recursion unwinds, every node from the new leaf to the root updates its height and is fixed on the spot if unbalanced. Deletion likewise adds rebalance to the returns of BST deletion.

The descent covers O(log n) levels with constant work per rebalance and rotation, so insertion and deletion take O(log n). Insertion needs at most one repair (a single or double rotation). In deletion a repair may shorten the subtree and push the imbalance up, so there may be a rotation at every level, O(log n) in all.

10.4.9Code trace: rotateRight and rotateLeft

First an LL case: inserting 5 into 40(20(10, 30), 50). 5 goes down 40 → 20 → 10 and lands left of 10. On the way back rebalance(10) and rebalance(20) find bf 1 and do nothing; rebalance(40) finds bf = 2 with left child 20 at 1, so it calls rotateRight(40).

The result is 20(10(5, —), 40(30, 50)), with balance factors 0 at 20 and 40, 1 at 10, 0 at the leaves. The inorder sequence 5 10 20 30 40 50 is unchanged. 40 dropped from height 3 to 1, and the new subtree root 20 has height 2, as the subtree did before the insertion.

The mirror-image RR case: inserting 60 into 20(10, 40(30, 50)). rebalance(20) finds bf = −2 with right child 40 at −1 and calls rotateLeft(20): y = x.right is 40, x.right = y.left points 20 at 30, y.left = x makes 20 the left child of 40, and the updates give 20 height 1 + max(0, 0) = 1 (was 3) and 40 height 1 + max(1, 1) = 2. The result is 40(20(10, 30), 50(—, 60)).

10.4.10Code trace: rebalance

Now a double rotation in code, the LR case: inserting 25 into 50(20(10, 30), 60). 25 goes down 50 → 20 → 30 and lands left of 30, and rebalance runs at each node on the way back.

The result is 30(20(10, 25), 50(—, 60)), back to the pre-insertion height 2, with balance factors 0, 0, −1 at 30, 20, 50. Assigning the first rotation's result to d.left is essential: only then does 50 point to the new subtree root 30.

10.4.11An AVL insertion example

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree, input on which a plain BST would build (except for the last key) a right-leaning chain. Table 10.17 shows each step.

Can 30 and 20 both be unbalanced when 50 arrives? No. rebalance(40) runs first, then rebalance(30), which fixes 30 and restores its subtree's old height of 1. By the time rebalance(20) runs, its height stays 2 and bf(20) = −1: fixing the lowest unbalanced ancestor leaves everything above untouched.

The last key, 25, lands left of 30. bf(30) = 1 and bf(40) = 1 are fine, but bf(20) = h(10) − h(40) = 0 − 2 = −2 with the right child 40 leaning left: RL. Rotating right at 40 (30 moves up) and then left at 20 brings 30 to the root and moves 25 right of 20. Six insertions give height 2; a plain BST would have height 4.

10.5Red-black trees

An AVL tree keeps a tight balance, and pays for it: after a deletion the imbalance can climb to the root, with a rotation at every level. A red-black tree accepts looser balance in exchange for very few rotations, doing most repairs by recoloring. Guibas and Sedgewick defined it in today's color terms in 1978; Java's TreeMap and TreeSet and C++'s std::map use it.

10.5.1The rules

Rule 3 just means that in code null children count as black, so rules 4 and 5 still make sense where a child is missing. When counting black nodes we count the root but not the NIL leaves.

Check the rules on Figure 10.32. The red 8 and 17 have black children (1, 11 and 15, 25), and the red leaves 6, 22, 27 have NIL children, so rule 4 holds. For rule 5: 13 → 8 → 1 → NIL has blacks 13 and 1; 13 → 8 → 1 → 6 → NIL the same, since 6 is red; 13 → 17 → 25 → 27 → NIL has 13 and 25. Two on every path.

10.5.2How the rules guarantee balance

The height bound comes from two rules acting together. Let b be the root's black height. Every root-to-NIL path has exactly b black nodes, so the shortest, all black, has b nodes. The longest also has b blacks, with reds in between, but rule 4 allows at most one red after each black, so it has at most 2b nodes.

Search, insertion and deletion thus take O(log n). Fix-up uses at most 2 rotations after an insertion and 3 after a deletion; the rest is recoloring. The height bound is looser than AVL's (about 1.44 log₂ n), so the tree can be somewhat taller, but updates are cheaper and each node needs only one extra bit.

10.5.3Insertion and the fix-up cases

Insertion has two phases. First the new node is attached as a leaf by BST insertion and colored red: a black node would add a black to its paths and break rule 5, whereas a red one changes no black height. Only rule 4 can break, if the parent is red too. The second phase repairs that.

The fix-up involves four nodes (Figure 10.34): the new node x, its parent p, grandparent g and uncle u, the parent's sibling. A red parent cannot be the root, so g exists, and it is black, or two reds would already have been adjacent. The uncle's color decides what happens.

With a black parent nothing needs fixing. At the end the root is always colored black, and a NIL uncle counts as black.

Recoloring preserves rule 5: g goes from black to red and p, u from red to black, and every path down from g passes through exactly one of p, u, so it still has one black here. But a red g may now have a red parent, breaking rule 4 higher up, so the loop continues from g. The problem climbs two levels per step and at worst ends at the root, which is then colored black.

Recoloring is no use when the uncle is black: making g red would remove a black from the uncle's paths. Rotate instead. In the line case (x and p are children on the same side), rotate at g; p rises and turns black, g drops and turns red. In the triangle case, first rotate at p to get a line, just like AVL single and double rotations. The subtree root is then black and the loop ends.

10.5.4The fix-up code

A red-black node has, besides the key and children, a color and a parent reference that lets the fix-up climb. The slides' fix-up code:

void fixUp(Node x) {       // x: new, red
    while (x != root && isRed(x.parent)) {
        Node p = x.parent, g = p.parent;
        Node u = (p == g.left) ? g.right : g.left;
        if (isRed(u)) {           // red uncle
            p.color = u.color = BLACK;
            g.color = RED;
            x = g;                // problem moves to g
        } else {                  // black uncle
            if (isTriangle(x, p, g)) { // zigzag
                rotate(p, x);     // make it a line
                Node t = x; x = p; p = t;
            }
            rotate(g, p);         // line
            p.color = BLACK; g.color = RED;
        }
    }
    root.color = BLACK;
}

The helpers and the rest of the insertion are given as comments:

// Insert: add as a leaf as in a BST,
// link the parent, color it red:
//   x = bstInsert(key);
//   x.color = RED; fixUp(x);

// NIL (null) counts as black
boolean isRed(Node n) {
    return n != null
        && n.color == RED;
}
// is x–p–g a zigzag (triangle)?
boolean isTriangle(Node x, Node p,
                   Node g) {
    return (p == g.left)
        != (x == p.left);
}
// rotate(a, b): b is a child of a;
// moves b up into a's place (right
// rotation if b is on the left, left
// if on the right; parent links too)

isRed(n) treats null as black, so NIL uncles need no special case. isTriangle(x, p, g) compares “is p a left child?” with “is x a left child?”; different answers mean a zigzag. rotate(a, b) lifts b, a child of a, into the place of a (right rotation if b is on the left, left if on the right), updating parent links. The traces cite lines of fixUp: 2 is the loop test, 5 the uncle check, 10 the triangle check, 14 the rotation at g, and 18 the coloring of the root.

Node t = x; x = p; p = t; swaps roles after the triangle rotation, which moved x up and p down, so that rotate(g, p) rotates the upper node.

BST insertion is O(log n), and the loop climbs at least two levels per iteration, so it runs at most O(log n) times. Rotations happen only in the last iteration, since the black-uncle branch ends the loop, and number at most two.

10.5.5Code trace: 10, 20, 30, 15

Insert 10, 20, 30, 15 into an empty red-black tree. A letter after a key gives its color, R (red) or B (black): R, B.

For 30 the uncle is NIL, hence black, and 10 → 20 → 30 is a line, so isTriangle is false and line 14 rotates left at the grandparent, as in the AVL RR fix. After recoloring, the subtree root 20 is black and the loop ends.

For 15, the uncle 30 is red, so recoloring suffices. The grandparent 20 turns red and the loop moves to it, but 20 is the root, so the loop stops and line 18 makes it black again. The tree's black height rose from 1 to 2.

10.5.6Code trace: 12 and 5

Next insert 12, then 5, into 20B(10B(—, 15R), 30B): 12 shows the triangle case, 5 recoloring that moves the problem up.

For 12, 15 is the right child of 10 and 12 the left child of 15: a zigzag. Rotating right at 15 makes the line 10 → 12 → 15, though two reds remain adjacent; after the role swap, rotating left at 10 lifts 12 to the subtree root, black, with 10 red. This is the AVL RL fix.

For 5, the uncle 15 is red. Recoloring turns 12 red, and the loop stops at 12 because its parent 20 is black. Every path now has 2 black nodes: 20 and 10 on 20 → 12 → 10 → 5 → NIL, 20 and 30 on 20 → 30 → NIL.

10.5.7Deletion in balanced trees

Deletion in both AVL and red-black trees begins with plain BST deletion; a two-child node is replaced by its successor or predecessor, so the node actually removed is always a leaf or has one child. Its removal may break the AVL height condition or the red-black black-height rule.

• AVL repair: Update heights from the removed node up to the root, rotating (LL, RR, LR or RL) at every node with |bf| = 2. Unlike insertion, a rotation can leave the subtree shorter than before and unbalance an ancestor, so several ancestors may need repair.
• Red-black repair: Deleting a red node changes no black counts. Removing a black node leaves its paths one black short, which recoloring and rotations fix according to the colors of the sibling and its children. Textbooks call this the “double black” fix-up; the deficit can climb to the root, but there are at most three rotations.

Neither insertion nor deletion disturbs the BST order. Balancing changes only the tree's shape and the auxiliary data (height or color), so an inorder traversal always gives the same sorted list.

10.5.8AVL or red-black?

Both perform every operation in O(log n); the right choice depends on the workload. Table 10.22 summarizes the differences.

In practice the difference is often small. A dictionary built once and queried millions of times gains a few comparisons per search from AVL's shorter tree; a general-purpose library class with frequent updates benefits from red-black's cheaper ones, which is why the Java and C++ standard libraries use red-black trees.

10.6Splay trees

AVL and red-black trees store balance information in each node and use it to repair the tree after each operation. A splay tree stores none and does not even try to stay balanced; instead, each access moves the accessed node to the root. Proposed by Sleator and Tarjan in 1985, it is also called a self-adjusting BST.

10.6.1A self-adjusting tree

A splay tree has no height guarantee and can even become a chain, whose bottom node costs O(n) to reach. But that access also roughly halves the depth of the nodes on its path. Sleator and Tarjan showed that any m operations from an empty tree take O(m log n) in total, an amortized cost of O(log n) per operation: the bound covers the whole sequence, with cheap operations paying for expensive ones.

The structure has three notable properties:

• Locality: Frequently accessed keys stay near the root, so the tree acts like a cache and can beat balanced trees when accesses concentrate on a few keys.
• Simplicity: No extra fields; one splay routine serves all operations, applied to the node found, the node inserted, or the node about to be deleted.
• Drawback: Even a search modifies the tree, a problem when several threads read it, and no single operation has a time guarantee, which real-time systems may not accept.

10.6.2Zig, zig-zig and zig-zag

Splaying repeats three kinds of step until the accessed node x is the root; which step applies depends on its parent p and grandparent g.

• Zig: p is the root. One rotation at p makes x the root; this can only be the last step.
• Zig-zig: x and p are children on the same side. Rotate at the grandparent first, then the parent.
• Zig-zag: they are on opposite sides. Rotate at the parent, then the grandparent, as in an AVL double rotation.

The zig-zig order differs from AVL and matters. Rotating at the grandparent first “folds” the path, shortening the upper chain too; single rotations from the parent also bring x to the root but can leave the chain long. The amortized bound relies on the grandparent-first order.

The slides' code puts the three steps in one loop:

void splay(Node x) {
    while (x != root) {
        Node p = x.parent, g = p.parent;
        if (g == null)                // zig
            rotate(p, x);
        else if (sameSide(x, p, g)) {  // zig-zig
            rotate(g, p);   // grandparent first
            rotate(p, x);
        } else {                      // zig-zag
            rotate(p, x);   // parent first
            rotate(g, x);
        }
    }
}

rotate(a, b) is the single rotation from the red-black code, lifting b, a child of a, into the place of a. sameSide(x, p, g) checks whether x hangs on the same side of p as p of g. The zig-zag branch ends with rotate(g, x) because after the first rotation x has replaced p as the child of g.

10.6.3Code trace: splay(50) and splay(10)

Start from 80(40(20(10, 30), 60(50, 70)), 90) and access 50, then 10.

After splay(50) the tree is 50(40(20(10, 30), —), 80(60(—, 70), 90)): 50 rose from depth 3 to the root, the old root 80 dropped a level taking 90 from depth 1 to 2, and 40, 20, 60, 70 kept their depths.

After splay(10) it is 10(—, 50(20(—, 40(30, —)), 80(60(—, 70), 90))). 10 is the root, and 50, accessed just before, is still at depth 1. Because zig-zig rotated at 40 first, 40 moved below 20 and took 30 as its left child.

One splay costs time proportional to the accessed node's depth, up to O(n), but the constant reshaping keeps the average over long sequences at O(log n).

10.7Multiway search trees

So far every tree has been binary, which suits main memory, where following a link takes nanoseconds. On disk, reading a block is thousands of times slower than reading memory, hundreds of thousands on old spinning disks. A binary tree indexing a billion records has height at least 30; with one disk read per node, a search costs 30 accesses. Multiway trees cut this to a few.

10.7.1The B-tree

A node's keys act as boundaries between its children. The root [20, 40] in Figure 10.39 sends keys below 20 left, keys between 20 and 40 to the middle, and larger keys right: the BST property generalized. A BST resembles a B-tree of order 2, but the B-tree's strength is the rule that all leaves share one depth, which keeps it perfectly balanced.

Why? Each node fills one disk block, which holds hundreds of keys. With order 200, a tree of height 3 holds 200⁴, over a billion keys, and a search reads four blocks, fewer from disk since the root usually stays in memory. Being wide and shallow, B-trees, introduced by Bayer and McCreight in 1972, underlie database and file-system indexes.

A B-tree of order 4 is a 2-3-4 tree, whose nodes have 2, 3 or 4 children, and it is equivalent to a red-black tree: merging each black node with its red children yields a 2-3-4 tree, and “equal black height” becomes “all leaves at the same depth.”

10.7.2Search and insertion in a B-tree

Search generalizes BST search. At each node the keys are compared with the target; if it is not found, the search descends to the child for its interval. One node, one disk block, is read per level, so the cost is O(log_m n) reads; binary search within a node takes O(log m) comparisons, O(log n) in total.

Insertion always starts at a leaf: follow the search path and put the key in sorted position. If the leaf then reaches m keys, it splits: the median moves up to the parent and the remaining keys form two nodes. The parent, gaining a key and a child, may split in turn, and so on up to the root, whose split creates a new root and adds a level.

The four-key leaf [25, 30, 33, 35] has no single median. The slides pick the right middle key, 33, leaving two keys on the left and one on the right; the left one would also do, as long as the choice is consistent. Odd orders avoid the issue: with m = 3 an overflowing node has three keys and one median.

Splitting means a B-tree grows from the bottom up. A BST grows downward as leaves are added, but a B-tree gains height only when its root splits, pushing all leaves down at once, so they always stay at the same depth.

Deletion reverses insertion. A node that falls below minimum occupancy borrows a key from a sibling or merges with it; a merge takes a key from the parent, and the shortage may propagate upward. If the root loses its last key, it is removed and the height drops by one.

10.7.3Insertion and splitting, step by step

Insert 10, 20, 30, 40, 50, 60, 70 into an empty B-tree of order m = 3, where a node holds at most 2 keys and 3 children and splits on reaching 3 keys.

The 7 keys occupy 3 levels; every internal node has 2 children and all leaves share a depth. The height grew only at the two root splits. Sorted input that would turn a plain BST into a chain yields a perfectly balanced B-tree.

10.7.4The B+ tree

The B+ tree, the variant most used in databases, differs from the B-tree in three ways:

• Data in the leaves: All keys and records live in the leaves; internal nodes hold only routing keys, copies of leaf keys.
• Linked leaves: The leaves form a left-to-right linked list, so range queries like “20 to 50” walk along it.
• Wider internal nodes: Without records, more keys fit in a block, so the order rises and the tree gets shallower.

Every search ends at a leaf, where the records are; there is no B-tree-style early exit at an internal node. In return, every search descends the same number of levels, so its cost is predictable. Most relational database systems use B+ trees for table indexes.

10.7.5Range queries in a B+ tree

Find the keys from 10 to 45 in the tree of Figure 10.42.

1. At the root, 10 < 20, so the leaf holding the lower bound is the leftmost child. This descent is a search, O(log n) levels.
2. Leaf [5, 10]: skip 5, take 10, then follow the link to the next leaf without going back up.
3. Leaf [20, 25, 30]: take all three and follow the link.
4. Third leaf [40, 50, 60]: take 40; stop at 50 > 45.

The result 10 20 25 30 40 is sorted. The cost is one descent plus the leaves read: O(log n + k) for k results. In a B-tree, with keys spread over internal nodes too, the query would climb up and down repeatedly; the leaf chain avoids that.

10.8Common mistakes

Most bugs in search tree code are of a few types. Those noted throughout the chapter are collected here as a checklist for reviewing tree code.

Two misconceptions lie behind these mistakes. One is seeing the tree only locally, a node with its parent and children, when the BST property, the AVL condition and the black-height rule all constrain whole subtrees. The other is forgetting Java's reference semantics: tree methods return a subtree's new root, and nothing changes until the caller stores it in a link or variable.

10.9Summary

• A search tree keeps elements ordered by key; search, insertion and deletion follow one path from the root in O(h), where h ranges from about log₂ n to n − 1.
• The BST property: all keys in a node's left subtree are smaller and all in its right subtree larger, for whole subtrees. Inorder traversal gives sorted output in O(n). The minimum is leftmost, the maximum rightmost.
• Insertion descends as in a search and attaches a leaf at the empty link reached. Methods return the subtree's new root: root = insert(root, x).
• The successor of x is the smallest larger key, the predecessor the largest smaller one; ceiling and floor also accept equality. All take O(h).
• Deletion has three cases: remove a leaf; bypass a one-child node; replace a two-child node's value with its successor's (or predecessor's) and delete that node, which, having no left child, is an easy case.
• A range query with pruning takes O(h + s). BST validation carries an allowed interval down from the root and takes O(n).
• A plain BST's shape follows insertion order (sorted input gives a chain; random order, average depth about 1.39 log₂ n). Balanced trees guarantee h = O(log n) by small local changes.
• An AVL tree has bf = h(left) − h(right) ∈ {−1, 0, 1} at every node. The sparsest AVL tree grows like the Fibonacci numbers, so h < 1.44 log₂(n + 2). LL and RR need one rotation, LR and RL two; a rotation is O(1) and preserves the inorder sequence.
• A red-black tree has a black root, no adjacent reds, and equal black counts on all paths, so the longest path is at most twice the shortest and h ≤ 2 log₂(n + 1). Insertion fix-up depends on the uncle: red means recolor, black means at most two rotations.
• A splay tree moves each accessed node to the root by zig, zig-zig and zig-zag steps: O(n) worst case per operation, O(log n) amortized.
• A B-tree node holds at most m − 1 keys and m children, and all leaves share a depth. Overflowing nodes split, sending the median up, so the tree grows from the bottom. A B+ tree keeps data only in linked leaves; range queries take O(log n + k).

10.10Key terms

Each term links to the course glossary with its Turkish equivalent.

• search tree
• binary search tree (BST)
• key
• root
• leaf
• subtree
• depth
• height
• inorder
• traversal
• successor
• predecessor
• ancestor
• sibling
• perfect binary tree
• balance factor
• AVL tree
• rotation
• red-black tree
• splay tree
• zig, zig-zig, zig-zag
• amortized analysis
• B-tree
• B+ tree
• degree

10.11Test Yourself

1. Insert 35, 18, 52, 10, 25, 44, 60, 22, 48 into an empty BST. What is its height and its inorder traversal? How many nodes does search(root, 48) compare?

   Answer

   The tree is 35(18(10, 25(22, —)), 52(44(—, 48), 60)). The deepest nodes, 22 and 48, are at depth 3, so the height is 3. Inorder: 10 18 22 25 35 44 48 52 60. Searching for 48 compares 35 (right), 52 (left), 44 (right) and 48: 4 nodes, the depth of 48 plus one.

2. Delete 18 and then 35 from the same tree, using the inorder successor for two-child nodes. What is the tree after each deletion?

   Answer

   The successor of 18 is 22 (right to 25, then left); 22 is copied into the node of 18 and the old leaf deleted: 35(22(10, 25), 52(44(—, 48), 60)). The successor of 35, left from 52, is 44; it is copied to the root and the old 44, having one child, is bypassed: 44(22(10, 25), 52(48, 60)).

3. In the tree of question 1, what are successor(25), predecessor(44), ceiling(45) and floor(21)?

   Answer

   successor(25) = 35 and predecessor(44) = 35: 25 has no right subtree and 44 no left subtree, and in both cases the nearest qualifying ancestor is the root. ceiling(45) = 48 and floor(21) = 18; 45 and 21 are not in the tree.

4. In the tree of question 1, what does range(root, 20, 46) print? Which nodes are never visited?

   Answer

   22 25 35 44, visiting 35, 18, 25, 22, 52, 44, 48. At 18, 20 < 18 is false, pruning 10; at 52, 52 < 46 is false, pruning 60. 48 is visited (right of 44, since 44 < 46) but is out of range. 10 and 60 are never visited.

5. Insert 30, 20, 10, 40, 50, 35 into an empty AVL tree. Which insertions trigger which case, and what is the final tree?

   Answer

   10: bf(30) = 2, bf(20) = 1 → LL; right at 30 gives 20(10, 30). 40: balanced. 50: bf(30) = −2, bf(40) = −1 → RR; left at 30 gives 20(10, 40(30, 50)). 35 lands right of 30: bf(20) = −2, bf(40) = 1 → RL; right at 40, then left at 20. Final tree 30(20(10, —), 40(35, 50)), height 2.

6. Insert 30, 20, 10, 25, 27 into an empty red-black tree. Which case applies at each insertion needing a fix-up? Give the final tree with colors.

   Answer

   10: red parent 20, NIL uncle, a line → right at 30; 20B(10R, 30R). 25: red parent 30, red uncle 10 → recolor (10, 30 black, 20 red), and the root 20 turns black again. 27: red parent 25, NIL uncle, a triangle (27 right, 25 left child) → left at 25, right at 30; 27 black, 30 red. Final tree 20B(10B, 27B(25R, 30R)), 2 blacks on every path.

7. Given the splay tree 50(30(20(10, —), 40), 70), which step does splay(40) use, and what is the result?

   Answer

   The path is 50 → 30 → 40 (p = 30, g = 50); 40 is a right child, 30 a left child: zig-zag. Rotating left at 30 and right at 50 gives 40(30(20(10, —), —), 50(—, 70)) in one step.

8. Insert 5, 15, 25, 35, 45 into an empty B-tree of order 3. Which insertions cause splits, and what is the final tree?

   Answer

   25 overflows [5, 15, 25], and 15 moves up into a new root: [15]{[5] [25]}. 35 joins the right leaf: [25, 35]. 45 overflows [25, 35, 45]; 35 moves up to the root, which has room: [15, 35]{[5] [25] [45]}. Two splits, one at the root; height 1.

9. In a red-black tree whose root has black height 3, how many nodes can the shortest and longest root-to-NIL paths contain? What is the minimum number of nodes in such a tree?

   Answer

   Every path has 3 black nodes. The shortest is all black: 3 nodes. On the longest, a red can follow each black: at most 6 (black, red, black, red, black, red, as the root is black). The minimum is 2³ − 1 = 7 nodes: the all-black perfect tree of height 2.

10. In the B+ tree of Figure 10.42, which keys lie between 22 and 55, and how many leaves are read?

    Answer

    At the root, 20 ≤ 22 < 40 leads to the middle leaf [20, 25, 30]: skip 20, take 25 and 30. The link leads to [40, 50, 60]: take 40 and 50, stop at 60 > 55. Result 25 30 40 50; 2 leaves read, with no return to the root.

10.12Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 11: covers binary search trees, AVL, splay, (2, 4) and red-black trees in the same order, with Java code close to that of these notes.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 3.2 and 3.3: presents BSTs and left-leaning red-black trees by relating them to 2-3 trees; the easiest way to see why red-black trees work.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 12, 13 and 18: BSTs, red-black trees (with all cases, including deletion) and B-trees, with proofs.
• D. D. Sleator and R. E. Tarjan, “Self-Adjusting Binary Search Trees” (1985): the paper that introduced splay trees, proving the amortized O(log n) bound with a potential function.

10.13References

1. G. M. Adelson-Velsky, E. M. Landis, “An algorithm for the organization of information”, Soviet Mathematics Doklady, 3, 1259–1263, 1962.
2. R. Bayer, E. M. McCreight, “Organization and maintenance of large ordered indexes”, Acta Informatica, 1(3), 173–189, 1972.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
4. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
5. L. J. Guibas, R. Sedgewick, “A dichromatic framework for balanced trees”, 19th Annual Symposium on Foundations of Computer Science, 8–21, 1978.
6. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
7. D. D. Sleator, R. E. Tarjan, “Self-adjusting binary search trees”, Journal of the ACM, 32(3), 652–686, 1985.

Related pages: Chapter 10 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.