PK

PKBytes

Explore tracks
Chapter 26: Self-Balancing Search Trees and B-Trees
26.03Intermediate / Advanced5 topics17 min2 interactive animations

Other balanced BSTs

Other balancing schemes: 2-3 trees, 2-3-4 trees, AA trees, scapegoat trees and weight-balanced trees, each with a short Java sketch.

Learning goals

  • Describe how 2-3 and 2-3-4 trees stay perfectly balanced by splitting nodes
  • Relate 2-3-4 trees to red-black trees
  • Implement the skew and split steps of an AA tree
  • Explain scapegoat rebuilding and the weight-balance condition

Prerequisites

AVL treesRed-black trees

AVL and red-black trees are two answers to the same question. Others trade code size, update cost or memory differently, and each is a useful idea on its own.

26.03.1

2-3 trees

A **2-3 tree** is a search tree where every node has either one key and two children, or two keys and three children, and all leaves are at the **same depth**. Balance is perfect by construction: the tree only grows taller when the root splits. Insert into a leaf; if it now holds three keys, **split** it: the middle key moves up to the parent and the other two become separate nodes. A split may overflow the parent in turn, so the splitting can continue up to the root.

The code is a bottom-up insertion that returns the promoted key and the new right node when a split happens. It is the same idea as the B-tree insert of the next group with the smallest possible node size. In the B-tree animation, wider nodes work the same way.

Java
1static class Node {
2    List<Integer> keys = new ArrayList<>();      // 1 or 2 keys after every operation
3    List<Node> kids = new ArrayList<>();         // empty in a leaf, else keys.size() + 1 children
4}
5static Node root = new Node();
6static Object[] insert(Node n, int k) {          // null, or {promoted key, new right node} after a split
7    int i = 0;
8    while (i < n.keys.size() && k > n.keys.get(i)) i++;
9    if (i < n.keys.size() && n.keys.get(i) == k) return null;           // duplicate
10    if (n.kids.isEmpty()) n.keys.add(i, k);
11    else {
12        Object[] up = insert(n.kids.get(i), k);
13        if (up == null) return null;
14        n.keys.add(i, (Integer) up[0]);
15        n.kids.add(i + 1, (Node) up[1]);
16    }
17    if (n.keys.size() <= 2) return null;
18    Node right = new Node();                     // three keys: split around the middle one
19    int mid = n.keys.get(1);
20    right.keys.add(n.keys.get(2));
21    if (!n.kids.isEmpty()) { right.kids.addAll(n.kids.subList(2, 4)); n.kids.subList(2, 4).clear(); }
22    n.keys.subList(1, 3).clear();
23    return new Object[]{mid, right};
24}
25static void add(int k) {
26    Object[] up = insert(root, k);
27    if (up != null) {                            // the root split: the tree grows taller
28        Node r = new Node();
29        r.keys.add((Integer) up[0]); r.kids.add(root); r.kids.add((Node) up[1]);
30        root = r;
31    }
32}

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

Your input

Try

B-tree (each box is one node) · 1 node

·
Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used
Setup

A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.

Step 1 / 19
Java
1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

t

2

max keys

3

No condition evaluated on this step
Execution trace (dry run table)Show 19 steps
StepLineStateWhat happens
1L1t=2 max keys=3A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2L34t=2 max keys=3 inserted=1010 goes into the leaf at position 0.
3L34t=2 max keys=3 inserted=2020 goes into the leaf at position 1.
4L34t=2 max keys=3 inserted=55 goes into the leaf at position 0.
5L26t=2 max keys=3 inserted=6The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6L16t=2 max keys=3 median=10Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7L1t=2 max keys=3 inserted=6Descend into child 0 of this node.
8L34t=2 max keys=3 inserted=66 goes into the leaf at position 1.
9L1t=2 max keys=3 inserted=12Descend into child 1 of this node.
10L34t=2 max keys=3 inserted=1212 goes into the leaf at position 0.
11L1t=2 max keys=3 inserted=30Descend into child 1 of this node.
12L34t=2 max keys=3 inserted=3030 goes into the leaf at position 2.
13L1t=2 max keys=3 inserted=7Descend into child 0 of this node.
14L34t=2 max keys=3 inserted=77 goes into the leaf at position 2.
15L1t=2 max keys=3 inserted=17Descend into child 1 of this node.
16L35t=2 max keys=3 inserted=17The child is full (3 keys): split it before descending, so there is always room to push a key up.
17L16t=2 max keys=3 median=20Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18L34t=2 max keys=3 inserted=1717 goes into the leaf at position 1.
19L1keys=8 height=1 t=28 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.
26.03.2

2-3-4 trees

A **2-3-4 tree** allows nodes of two, three or four children (one to three keys), and splits a full node **on the way down**, before descending, so no split ever has to propagate back up. It is exactly a **B-tree of minimum degree t = 2**. Run the B-tree animation with t = 2: the first preset (10, 20, 5, 6, 12, 30, 7, 17) ends at height 1 after 2 splits.

The link to red-black trees is the reason to know them. A red-black tree **is** a 2-3-4 tree drawn as a binary tree: a black node with no red child is a 2-node; a black node with one red child forms a 3-node; a black node with two red children forms a 4-node. Recolouring (case 1) is a node split, and rotations rearrange the inside of a node. Reading a red-black tree this way makes its fix-up cases easy to remember.

2-3-4 nodeRed-black picture
2-node: one keya black node with two black (or NIL) children
3-node: two keysa black node with one red child
4-node: three keysa black node with two red children
Split of a 4-noderecolouring: parent and uncle black, grandparent red (insertion case 1)

B-tree: search, insertion with node splits, deletion with borrow and merge

Interactive · edit the input

Your input

Try

B-tree (each box is one node) · 1 node

·
Node being examinedSearch pathKey found / new nodeChanged by split, borrow or mergeSibling used
Setup

A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.

Step 1 / 19
Java
1static int T = 2;                                // minimum degree: every node but the root holds T-1 .. 2T-1 keys
2static class Node {
3    List<Integer> keys = new ArrayList<>();
4    List<Node> kids = new ArrayList<>();         // empty in a leaf
5    boolean leaf = true;
6}
7static Node root = new Node();
8static boolean contains(Node x, int k) {
9    int i = 0;
10    while (i < x.keys.size() && k > x.keys.get(i)) i++;          // first key >= k
11    if (i < x.keys.size() && x.keys.get(i) == k) return true;
12    return !x.leaf && contains(x.kids.get(i), k);
13}
14static void splitChild(Node x, int i) {          // x.kids[i] is full (2T-1 keys)
15    Node y = x.kids.get(i), z = new Node();
16    z.leaf = y.leaf;
17    z.keys.addAll(y.keys.subList(T, 2 * T - 1));                 // the upper T-1 keys move to the new node
18    int median = y.keys.get(T - 1);
19    y.keys.subList(T - 1, 2 * T - 1).clear();                    // y keeps the lower T-1 keys
20    if (!y.leaf) { z.kids.addAll(y.kids.subList(T, 2 * T)); y.kids.subList(T, 2 * T).clear(); }
21    x.keys.add(i, median);                       // the median moves up
22    x.kids.add(i + 1, z);
23}
24static void insert(int k) {
25    if (contains(root, k)) return;
26    if (root.keys.size() == 2 * T - 1) {         // a full root: the tree grows in height here
27        Node s = new Node(); s.leaf = false; s.kids.add(root); root = s; splitChild(s, 0);
28    }
29    insertNonFull(root, k);
30}
31static void insertNonFull(Node x, int k) {
32    int i = 0;
33    while (i < x.keys.size() && k > x.keys.get(i)) i++;
34    if (x.leaf) { x.keys.add(i, k); return; }
35    if (x.kids.get(i).keys.size() == 2 * T - 1) {                // split a full child before descending
36        splitChild(x, i);
37        if (k > x.keys.get(i)) i++;
38    }
39    insertNonFull(x.kids.get(i), k);
40}
41static void delete(int k) {
42    delete(root, k);
43    if (root.keys.isEmpty() && !root.leaf) root = root.kids.get(0);   // the tree shrinks in height
44}
45static void delete(Node x, int k) {
46    int i = 0;
47    while (i < x.keys.size() && k > x.keys.get(i)) i++;
48    if (i < x.keys.size() && x.keys.get(i) == k) {
49        if (x.leaf) x.keys.remove(i);                            // case 1: the key is in a leaf
50        else if (x.kids.get(i).keys.size() >= T) {               // case 2a: use the predecessor
51            int pred = max(x.kids.get(i)); x.keys.set(i, pred); delete(x.kids.get(i), pred);
52        } else if (x.kids.get(i + 1).keys.size() >= T) {         // case 2b: use the successor
53            int succ = min(x.kids.get(i + 1)); x.keys.set(i, succ); delete(x.kids.get(i + 1), succ);
54        } else { merge(x, i); delete(x.kids.get(i), k); }        // case 2c: merge both children around the key
55    } else if (!x.leaf) {
56        if (x.kids.get(i).keys.size() == T - 1) {                // the child needs a spare key before we descend
57            if (i > 0 && x.kids.get(i - 1).keys.size() >= T) borrowFromLeft(x, i);          // case 3a
58            else if (i < x.keys.size() && x.kids.get(i + 1).keys.size() >= T) borrowFromRight(x, i);
59            else { if (i == x.keys.size()) i--; merge(x, i); }                               // case 3b
60        }
61        delete(x.kids.get(i), k);
62    }
63}
64static void merge(Node x, int i) {               // kids[i] + keys[i] + kids[i+1] become kids[i]
65    Node y = x.kids.get(i), z = x.kids.get(i + 1);
66    y.keys.add(x.keys.remove(i));
67    y.keys.addAll(z.keys);
68    y.kids.addAll(z.kids);
69    x.kids.remove(i + 1);
70}
71static void borrowFromLeft(Node x, int i) {
72    Node c = x.kids.get(i), s = x.kids.get(i - 1);
73    c.keys.add(0, x.keys.get(i - 1));
74    x.keys.set(i - 1, s.keys.remove(s.keys.size() - 1));
75    if (!s.leaf) c.kids.add(0, s.kids.remove(s.kids.size() - 1));
76}
77static void borrowFromRight(Node x, int i) {
78    Node c = x.kids.get(i), s = x.kids.get(i + 1);
79    c.keys.add(x.keys.get(i));
80    x.keys.set(i, s.keys.remove(0));
81    if (!s.leaf) c.kids.add(s.kids.remove(0));
82}
83static int min(Node x) { while (!x.leaf) x = x.kids.get(0); return x.keys.get(0); }
84static int max(Node x) { while (!x.leaf) x = x.kids.get(x.kids.size() - 1); return x.keys.get(x.keys.size() - 1); }

Live state

0 splits0 merges0 borrows

t

2

max keys

3

No condition evaluated on this step
Execution trace (dry run table)Show 19 steps
StepLineStateWhat happens
1L1t=2 max keys=3A B-tree of minimum degree t = 2: every node except the root holds 1 to 3 keys, every internal node with m keys has m + 1 children, and all leaves are at the same depth. With t = 2 this is the 2-3-4 tree.
2L34t=2 max keys=3 inserted=1010 goes into the leaf at position 0.
3L34t=2 max keys=3 inserted=2020 goes into the leaf at position 1.
4L34t=2 max keys=3 inserted=55 goes into the leaf at position 0.
5L26t=2 max keys=3 inserted=6The root is full: create a new empty root above it and split the old root. This is the only way a B-tree grows taller.
6L16t=2 max keys=3 median=10Split the full node: its median 10 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
7L1t=2 max keys=3 inserted=6Descend into child 0 of this node.
8L34t=2 max keys=3 inserted=66 goes into the leaf at position 1.
9L1t=2 max keys=3 inserted=12Descend into child 1 of this node.
10L34t=2 max keys=3 inserted=1212 goes into the leaf at position 0.
11L1t=2 max keys=3 inserted=30Descend into child 1 of this node.
12L34t=2 max keys=3 inserted=3030 goes into the leaf at position 2.
13L1t=2 max keys=3 inserted=7Descend into child 0 of this node.
14L34t=2 max keys=3 inserted=77 goes into the leaf at position 2.
15L1t=2 max keys=3 inserted=17Descend into child 1 of this node.
16L35t=2 max keys=3 inserted=17The child is full (3 keys): split it before descending, so there is always room to push a key up.
17L16t=2 max keys=3 median=20Split the full node: its median 20 moves up into the parent, the lower 1 keys stay and the upper 1 keys go to a new node.
18L34t=2 max keys=3 inserted=1717 goes into the leaf at position 1.
19L1keys=8 height=1 t=28 keys in a tree of height 1: 2 splits, 0 borrows, 0 merges.
26.03.3

AA trees

An **AA tree** is a red-black tree where only **right** red children are allowed, which cuts the number of cases to two operations. Each node stores a **level** (about its black height). Rules: a left child has a lower level than its parent; a right child has the same or a lower level; a right grandchild has a lower level than the grandparent; every leaf is on level 1. A right child at the same level plays the part of a red node.

Insert recursively and, on the way back, apply **skew** (remove a left horizontal link by a right rotation) and **split** (remove two consecutive right horizontal links by a left rotation and lift the middle node one level). Those two functions are the whole balancing code, which is why AA trees are popular for teaching and for small implementations.

Java
1static class Node {
2    int key, level = 1;
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static Node nil() { Node n = new Node(0); n.level = 0; n.left = n; n.right = n; return n; }
7static final Node NIL = nil();
8
9static Node skew(Node n) {                       // a left child on the same level: rotate right
10    if (n.left.level == n.level) { Node l = n.left; n.left = l.right; l.right = n; return l; }
11    return n;
12}
13static Node split(Node n) {                      // two right links on the same level: rotate left, promote the middle
14    if (n.right.right.level == n.level) { Node r = n.right; n.right = r.left; r.left = n; r.level++; return r; }
15    return n;
16}
17static Node insert(Node n, int key) {
18    if (n == NIL) { Node fresh = new Node(key); fresh.left = NIL; fresh.right = NIL; return fresh; }
19    if (key < n.key) n.left = insert(n.left, key);
20    else if (key > n.key) n.right = insert(n.right, key);
21    else return n;
22    return split(skew(n));
23}
26.03.4

Scapegoat trees

A **scapegoat tree** stores no balance information at all, only subtree sizes. A parameter α between 0.5 and 1 (here 0.7) defines the target: the tree is allowed a depth of about log base 1/α of n. After an insertion, if the new node is too deep, walk back up to the first ancestor whose child holds more than α of its subtree: that ancestor is the **scapegoat**. **Rebuild** its whole subtree into a perfectly balanced one by flattening it with an inorder traversal and rebuilding from the middle.

A rebuild is expensive (linear in the subtree) but rare, so insertions cost O(log n) **amortised**, and searches are O(log n) worst case with no extra field per node but the size. (Supporting deletion adds a rule: rebuild the whole tree once it has shrunk enough since the last rebuild.) The method is attractive when memory is tight or when a rotation-free structure is preferred.

Java
1static class Node {
2    int key, size = 1;
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static final double ALPHA = 0.7;
7static Node root;
8static int n;
9static int size(Node x) { return x == null ? 0 : x.size; }
10
11static void insert(int key) {
12    List<Node> path = new ArrayList<>();
13    Node cur = root;
14    while (cur != null) {
15        if (key == cur.key) return;              // duplicate
16        path.add(cur);
17        cur = key < cur.key ? cur.left : cur.right;
18    }
19    Node fresh = new Node(key);
20    if (path.isEmpty()) { root = fresh; n = 1; return; }
21    Node p = path.get(path.size() - 1);
22    if (key < p.key) p.left = fresh; else p.right = fresh;
23    n++;
24    for (Node a : path) a.size++;
25    if (path.size() > Math.log(n) / Math.log(1 / ALPHA)) {     // the new node is too deep
26        Node child = fresh;
27        for (int i = path.size() - 1; i >= 0; i--) {
28            Node parent = path.get(i);
29            if (size(child) > ALPHA * size(parent)) {           // the scapegoat: a lopsided ancestor
30                Node rebuilt = rebuild(parent);
31                if (i == 0) root = rebuilt;
32                else { Node gp = path.get(i - 1); if (gp.left == parent) gp.left = rebuilt; else gp.right = rebuilt; }
33                return;
34            }
35            child = parent;
36        }
37    }
38}
39static Node rebuild(Node sub) {
40    List<Node> nodes = new ArrayList<>();
41    flatten(sub, nodes);                         // inorder: sorted
42    return build(nodes, 0, nodes.size() - 1);    // middle as the root, recursively
43}
44static void flatten(Node x, List<Node> out) {
45    if (x == null) return;
46    flatten(x.left, out); out.add(x); flatten(x.right, out);
47}
48static Node build(List<Node> a, int lo, int hi) {
49    if (lo > hi) return null;
50    int mid = (lo + hi) >>> 1;
51    Node x = a.get(mid);
52    x.left = build(a, lo, mid - 1);
53    x.right = build(a, mid + 1, hi);
54    x.size = 1 + size(x.left) + size(x.right);
55    return x;
56}
26.03.5

Weight-balanced trees

A **weight-balanced tree** balances by **subtree size** rather than height: for every node, neither child may hold more than a fixed fraction of the nodes, here at most three times as many as its sibling. The sizes double as order statistics, so rank and k-th smallest come for free. Functional libraries (Haskell's Data.Map and many Scala and OCaml sets) use this scheme because the persistent updates reuse unchanged subtrees.

After an insertion, balance compares the sizes of the children. If the right side is more than three times the left, rotate left, using a double rotation when the right child's inner grandchild is heavy. With the parameters 3 and 2 used here the invariant provably holds for insertions; deletion needs the same function with the mirrored checks.

Java
1static class Node {
2    int key, size = 1;
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static int size(Node n) { return n == null ? 0 : n.size; }
7static void update(Node n) { n.size = 1 + size(n.left) + size(n.right); }
8static Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; update(x); update(y); return y; }
9static Node rotateRight(Node y) { Node x = y.left; y.left = x.right; x.right = y; update(y); update(x); return x; }
10
11static Node balance(Node n) {
12    update(n);
13    int l = size(n.left), r = size(n.right);
14    if (l + r <= 1) return n;                    // tiny subtrees are always fine
15    if (r > 3 * l) {                             // too heavy on the right
16        if (size(n.right.left) >= 2 * size(n.right.right)) n.right = rotateRight(n.right);   // double rotation
17        return rotateLeft(n);
18    }
19    if (l > 3 * r) {
20        if (size(n.left.right) >= 2 * size(n.left.left)) n.left = rotateLeft(n.left);
21        return rotateRight(n);
22    }
23    return n;
24}
25static Node insert(Node n, int key) {
26    if (n == null) return new Node(key);
27    if (key < n.key) n.left = insert(n.left, key);
28    else if (key > n.key) n.right = insert(n.right, key);
29    else return n;
30    return balance(n);
31}

Practice ladder

Now try it yourself

Easy

  • Convert Sorted Array to Binary Search Tree
  • Balanced Binary Tree

Medium

  • Balance a Binary Search Tree
  • Implement a TreeSet with a scapegoat tree

Advanced

  • Implement a persistent weight-balanced tree
  • Implement an AA tree with deletion

Key takeaways

  • 2-3 and 2-3-4 trees stay perfectly balanced by splitting nodes; the tree grows only when the root splits.
  • A red-black tree is a 2-3-4 tree drawn as a binary tree.
  • An AA tree needs only skew and split to keep the balance.
  • A scapegoat tree rebuilds a lopsided subtree, giving amortised O(log n) with no balance field.
  • Weight-balanced trees balance by subtree size and give order statistics for free.