26.06Intermediate / Advanced5 topics15 min1 interactive animation

Tree implementations

Practical details of implementing balanced trees: sentinel nodes, parent pointers, rotations with parents, augmenting nodes with height and size, and comparator correctness.

Learning goals

Use a sentinel to remove null checks and speed up search
Traverse with parent pointers and no stack
Write a rotation that maintains parent pointers
Augment a node with a size to answer rank queries
Avoid comparator mistakes that silently corrupt a tree

Prerequisites

AVL treesRed-black trees

The algorithms are short; the bugs are in the details. These patterns remove whole classes of them.

26.06.1

Sentinel nodes

A **sentinel node** is a dummy object that stands in for 'no node'. One shared black NIL replaces every null child in a red-black tree, so code like x.parent.left.color never throws, and the fix-up can even set the parent of NIL temporarily. A second use is the classic **search sentinel**: store the key being searched in the sentinel, and the loop no longer needs a null check, because the walk always ends at a node holding the key.

The price: the sentinel is shared mutable state, so it must be reset and is not thread-safe, and == NIL checks replace == null checks everywhere. Use it where the code is intricate (red-black fix-up), and null elsewhere.

Java

1static class Node {
2    int key;
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static Node nil() { Node n = new Node(0); n.left = n; n.right = n; return n; }
7static final Node NIL = nil();
8static Node root = NIL;
9
10static boolean contains(int key) {
11    NIL.key = key;                               // the search is guaranteed to stop: no null check in the loop
12    Node n = root;
13    while (n.key != key) n = key < n.key ? n.left : n.right;
14    return n != NIL;
15}
16static void insert(int key) {
17    Node fresh = new Node(key);
18    fresh.left = NIL; fresh.right = NIL;
19    if (root == NIL) { root = fresh; return; }
20    Node n = root;
21    for (;;) {
22        if (key == n.key) return;
23        Node next = key < n.key ? n.left : n.right;
24        if (next == NIL) { if (key < n.key) n.left = fresh; else n.right = fresh; return; }
25        n = next;
26    }
27}

26.06.2

Parent pointers

A **parent pointer** lets a node find its parent without a stack or a search from the root. It makes the successor easy to compute and an inorder iterator possible with O(1) extra space: if there is a right subtree, take its leftmost node; otherwise climb until you arrive from a left child. The cost is one more field per node and one more link to keep correct in every rotation, insertion and deletion.

Red-black delete, transplant and many iterators rely on it. Libraries that expose iterators over a tree (like TreeMap) store the parent for exactly this reason.

Java

1static class Node {
2    int key;
3    Node left, right, parent;
4    Node(int key) { this.key = key; }
5}
6static Node successor(Node x) {                  // the next node in inorder, or null
7    if (x.right != null) {
8        Node n = x.right;
9        while (n.left != null) n = n.left;       // the leftmost node of the right subtree
10        return n;
11    }
12    Node p = x.parent;
13    while (p != null && x == p.right) { x = p; p = p.parent; }   // climb until we come from a left child
14    return p;
15}

26.06.3

Rotations

A rotation is a local rewrite of three links plus the parent's link (and the parent pointers, if the nodes have them). The standard mistakes are forgetting to update the **parent's** pointer to the new subtree root, forgetting a child's parent field, and updating **heights or sizes in the wrong order**: update the lower node first, because the upper node's value depends on it.

A defensive habit: after writing a rotation, check an inorder traversal before and after (it must be identical) and check every parent link in a test. The animation of the AVL tree shows the rotations one at a time, with the nodes involved marked.

Java

1static class Node {
2    int key;
3    Node left, right, parent;
4    Node(int key) { this.key = key; }
5}
6static Node root;
7static void rotateLeft(Node x) {                 // x.right moves up; every link and parent pointer is rewritten
8    Node y = x.right;
9    x.right = y.left;
10    if (y.left != null) y.left.parent = x;
11    y.parent = x.parent;
12    if (x.parent == null) root = y;              // x was the root
13    else if (x == x.parent.left) x.parent.left = y;
14    else x.parent.right = y;
15    y.left = x;
16    x.parent = y;
17}

AVL tree: insertion and deletion with rotations

Interactive · edit the input

Setup

An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.

Step 1 / 34

Java

1static class Node { int key, height; Node left, right; Node(int k) { key = k; } }   // a leaf has height 0
2static int h(Node n) { return n == null ? -1 : n.height; }
3static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
4static int balance(Node n) { return h(n.left) - h(n.right); }
5static Node rotateRight(Node y) {                // the left child x becomes the subtree root
6    Node x = y.left;
7    y.left = x.right;
8    x.right = y;
9    update(y); update(x);
10    return x;
11}
12static Node rotateLeft(Node x) {
13    Node y = x.right;
14    x.right = y.left;
15    y.left = x;
16    update(x); update(y);
17    return y;
18}
19static Node rebalance(Node n) {
20    update(n);
21    int b = balance(n);
22    if (b > 1) {                                 // left-heavy
23        if (balance(n.left) < 0) n.left = rotateLeft(n.left);       // LR: first turn it into LL
24        return rotateRight(n);
25    }
26    if (b < -1) {                                // right-heavy
27        if (balance(n.right) > 0) n.right = rotateRight(n.right);   // RL: first turn it into RR
28        return rotateLeft(n);
29    }
30    return n;
31}
32static Node insert(Node n, int key) {
33    if (n == null) return new Node(key);
34    if (key < n.key) n.left = insert(n.left, key);
35    else if (key > n.key) n.right = insert(n.right, key);
36    else return n;                               // duplicates are ignored
37    return rebalance(n);                         // repair this node on the way back up
38}
39static Node delete(Node n, int key) {
40    if (n == null) return null;
41    if (key < n.key) n.left = delete(n.left, key);
42    else if (key > n.key) n.right = delete(n.right, key);
43    else {
44        if (n.left == null) return n.right;
45        if (n.right == null) return n.left;
46        Node s = n.right;
47        while (s.left != null) s = s.left;       // inorder successor
48        n.key = s.key;
49        n.right = delete(n.right, s.key);
50    }
51    return rebalance(n);
52}

Live state

0 rotations

height

-1

No condition evaluated on this step

Execution trace (dry run table)Show 34 steps

Step	Line	State	What happens
1	L32	height=-1	An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.
2	L33	height=0 inserted=10	Insert 10: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
3	L35	height=0 inserted=20	20 > 10: go right.
4	L33	height=0 inserted=20	Insert 20: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
5	L22	height=1 node=10 balance=-1	Back at 10: heights updated, balance factor -1. Within ±1, so no rotation.
6	L35	height=1 inserted=30	30 > 10: go right.
7	L35	height=1 inserted=30	30 > 20: go right.
8	L33	height=1 inserted=30	Insert 30: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
9	L22	height=1 node=20 balance=-1	Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
10	L26	height=2 node=10 balance=-2 case=RR	Node 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 has balance -1, so this is the right-right (RR) case.
11	L28	height=1 case=RR	Rotate 10 left: 20 becomes the subtree root, 10 its left child. The subtree's height is back to 1.
12	L35	height=1 inserted=40	40 > 20: go right.
13	L35	height=1 inserted=40	40 > 30: go right.
14	L33	height=1 inserted=40	Insert 40: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
15	L22	height=1 node=30 balance=-1	Back at 30: heights updated, balance factor -1. Within ±1, so no rotation.
16	L22	height=2 node=20 balance=-1	Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
17	L35	height=2 inserted=50	50 > 20: go right.
18	L35	height=2 inserted=50	50 > 30: go right.
19	L35	height=2 inserted=50	50 > 40: go right.
20	L33	height=2 inserted=50	Insert 50: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
21	L22	height=2 node=40 balance=-1	Back at 40: heights updated, balance factor -1. Within ±1, so no rotation.
22	L26	height=2 node=30 balance=-2 case=RR	Node 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance -1, so this is the right-right (RR) case.
23	L28	height=2 case=RR	Rotate 30 left: 40 becomes the subtree root, 30 its left child. The subtree's height is back to 1.
24	L22	height=2 node=20 balance=-1	Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
25	L35	height=2 inserted=25	25 > 20: go right.
26	L34	height=2 inserted=25	25 < 40: go left.
27	L34	height=2 inserted=25	25 < 30: go left.
28	L33	height=2 inserted=25	Insert 25: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
29	L22	height=2 node=30 balance=+1	Back at 30: heights updated, balance factor +1. Within ±1, so no rotation.
30	L22	height=2 node=40 balance=+1	Back at 40: heights updated, balance factor +1. Within ±1, so no rotation.
31	L26	height=3 node=20 balance=-2 case=RL	Node 20 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance +1, so this is the right-left (RL) case.
32	L27	height=3 case=RL	RL step 1: rotate 40 right, so 30 moves above it. Now the case is RR.
33	L28	height=2 case=RL	Rotate 20 left: 30 becomes the subtree root, 20 its left child. The subtree's height is back to 2.
34	L50	keys=6 height=2 minimum height=2	4 rotations in total. Height 2 for 6 keys; a perfectly balanced tree would have 2.

26.06.4

Height/size augmentation

**Augmenting** a node means storing extra information that can be recomputed from its children in O(1): a height (AVL), a size (rank queries), a subtree sum, a maximum. After every rotation or update, recompute the field bottom-up, **lower node first**. With a size field, the k-th smallest key and the rank of a key take O(log n) on a balanced tree.

The tree below is an AVL tree that stores both height and size. The k-th smallest walk is the one from the BST chapter: compare k with the size of the left subtree to decide where to go.

Java

1static class Node {
2    int key, height, size = 1;                   // height for balance, size for order statistics
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static int h(Node n) { return n == null ? -1 : n.height; }
7static int size(Node n) { return n == null ? 0 : n.size; }
8static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); n.size = 1 + size(n.left) + size(n.right); }
9static Node rotateRight(Node y) { Node x = y.left; y.left = x.right; x.right = y; update(y); update(x); return x; }
10static Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; update(x); update(y); return y; }
11static Node rebalance(Node n) {
12    update(n);
13    int b = h(n.left) - h(n.right);
14    if (b > 1) { if (h(n.left.left) < h(n.left.right)) n.left = rotateLeft(n.left); return rotateRight(n); }
15    if (b < -1) { if (h(n.right.right) < h(n.right.left)) n.right = rotateRight(n.right); return rotateLeft(n); }
16    return n;
17}
18static Node insert(Node n, int key) {
19    if (n == null) return new Node(key);
20    if (key < n.key) n.left = insert(n.left, key);
21    else if (key > n.key) n.right = insert(n.right, key);
22    else return n;
23    return rebalance(n);
24}
25static int kth(Node n, int k) {                  // 1-based k-th smallest in O(log n)
26    int left = size(n.left);
27    if (k <= left) return kth(n.left, k);
28    if (k == left + 1) return n.key;
29    return kth(n.right, k - left - 1);
30}
31static int rank(Node n, int x) {                 // how many keys are smaller than x
32    if (n == null) return 0;
33    return x <= n.key ? rank(n.left, x) : size(n.left) + 1 + rank(n.right, x);
34}

26.06.5

Comparator correctness

Every ordered tree trusts its comparator completely, and a broken one corrupts the structure silently. A comparator must be **consistent**: compare(a, b) and compare(b, a) have opposite signs, it is transitive, and it returns 0 exactly for elements that should count as the same key. A comparator that never returns 0 (for example (a, b) -> 1) makes every key look different from itself: the map's get cannot find what was just put.

Check the equality it implies, too. A TreeSet whose comparator ignores a field drops elements that differ only in that field. When a comparison has several fields, compare all of them in order, with Integer.compare instead of subtraction. The example below shows a map that loses its own key.

Java

1static void brokenComparator() {
2    TreeMap<Integer, String> m = new TreeMap<>((a, b) -> 1);     // never "equal": compare(a, a) == 1
3    m.put(1, "one");
4    m.put(1, "uno");
5    System.out.println(m.size());                // 2: the same key was stored twice
6    System.out.println(m.get(1));                // null: the lookup can never find an equal key
7}

Practice ladder

Now try it yourself

Easy

Design a TreeSet wrapper (concept)
Kth Largest Element in an Array

Medium

Inorder Successor in BST II
Count of Smaller Numbers After Self

Advanced

Implement an order-statistic tree
Range Module

Key takeaways

A sentinel NIL removes null checks; a search sentinel removes the null test from the loop.
Parent pointers allow stackless inorder iteration but must be fixed in every rotation.
Rotations: update the lower node's height or size first, and rewire the parent's link.
Augment nodes with fields recomputable from the children, such as size for k-th smallest and rank.
A comparator defines equality; an inconsistent one corrupts a tree without any error.