Balanced BSTs: AVL & Red-Black Trees
A plain binary search tree is only as good as the order its keys arrive in: random keys give height about , sorted keys give a linked list of height . A balanced binary search tree enforces a structural invariant after every insert and delete so that its height stays for every input sequence. Search, insert, delete, successor, floor, ceiling and rank then all cost in the worst case.
This lesson covers the two that matter in practice. The AVL tree keeps every node's two subtree heights within one of each other. The red-black tree colours nodes so that no root-to-leaf path is more than twice as long as another; it is looser, cheaper to update, and sits behind java.util.TreeMap, std::map and the Linux kernel's epoll. Both are built from one primitive, the rotation. The lesson ends where binary trees stop being the right answer: on disk, where the B-tree wins. Previous lesson: Binary Search Trees; next: Treaps, Splay Trees & Skip Lists.
Why this exists
Ordered data is everywhere: a timer queue needs "the next timer to fire", a scheduler needs "the runnable task with the least virtual runtime", a trading engine needs "the best bid". A hash table gives lookups but no order: it cannot answer "next larger key" without scanning everything. A sorted array answers order questions with binary search but pays per insertion. A BST does both in time proportional to its height, so the only problem left is to keep the height small.
The first solution came from Moscow. In 1962 Georgy Adelson-Velsky and Evgenii Landis published "An algorithm for the organization of information" in Doklady Akademii Nauk SSSR; the tree carries their initials. Their invariant (subtree heights differ by at most one) and their repair operation (the rotation) are still taught unchanged. In 1972 Rudolf Bayer, fresh from co-inventing the B-tree, described symmetric binary B-trees, a binary encoding of B-trees of order 4. Leonidas Guibas and Robert Sedgewick recast these in 1978 as red-black trees ("A dichromatic framework for balanced trees", FOCS 1978), the name reportedly coming from the two pen colours available to them. Sedgewick returned in 2008 with the left-leaning red-black tree, which cuts the number of cases roughly in half.
Why two designs? AVL trees are shallower, which favours lookups; red-black trees restructure less per update (at most two rotations per insert, three per delete), which favours writes and augmentation. Most standard libraries chose red-black. On disk both lose to a tree with hundreds of children per node, which is why relational database indexes are B-trees.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "insert, delete and query the k-th smallest / rank of x" in an online stream | Order-statistic tree: a balanced BST augmented with subtree sizes |
| "next greater key", "largest key ≤ x", floor / ceiling, with inserts and deletes interleaved | Ordered map: TreeMap, std::map, SortedList (all balanced) |
| "sliding window median", "maintain a sorted window" | Ordered multiset (two heaps also work; the tree supports arbitrary deletes) |
| "count elements smaller than x to the right / left" | Augmented balanced BST, or a Fenwick tree after coordinate compression |
| "book an interval if it does not overlap" | Ordered map keyed by start: check floor and ceiling |
| "worst-case guaranteed", "adversarial input", "keys arrive sorted" | A balanced BST, not a plain BST |
| "rebalance this BST", "is this tree height-balanced?" | AVL invariant; rebuild from the inorder sequence |
Implement TreeMap / std::map yourself, or "design a leaderboard / order book" | Red-black or AVL with augmentation |
| "the index lives on disk", "millions of rows, minimize page reads" | B-tree / B+ tree, not a binary tree |
The signal: order (neighbours, ranks, ranges) and updates, with a worst-case guarantee. Membership only: hash set. Static data: sorted array.
Intuition & first principles
What "balanced" has to mean
The ideal is a perfectly balanced tree, every level but the last full, height (20 for a million keys). Keeping a tree perfect is too expensive: one insert can force every node to move. So every scheme relaxes perfection to an invariant that is:
- Strong enough that height is for a small constant .
- Weak enough that an insert or delete can restore it by touching nodes, ideally structural changes.
AVL trees bound subtree height differences and get ; red-black trees use a colouring rule and get ; B-trees vary the number of keys per node and keep all leaves at one depth. Same idea each time: a local invariant whose violation can be repaired locally.
Height conventions
This page uses height = number of nodes on the longest root-to-leaf path, so the empty tree has height 0 and a single node has height 1. CLRS counts edges instead (a single node has height 0). The conventions differ by one; every formula below is stated in the node-counting convention, which is what the code stores.
The balance factor of a node is . Positive means left-heavy.
Rotations: the only tool you need
A rotation is a constant-time pointer rearrangement that changes the shape of a tree while preserving its inorder sequence, and therefore its BST property. A right rotation at y lifts y's left child x into y's place:
flowchart TB
subgraph before["Before: right-rotate at y"]
Y1(("y")) --> X1(("x"))
Y1 --> C1["C: keys > y"]
X1 --> A1["A: keys < x"]
X1 --> B1["B: x < keys < y"]
end
subgraph after["After: x is the subtree root"]
X2(("x")) --> A2["A: keys < x"]
X2 --> Y2(("y"))
Y2 --> B2["B: x < keys < y"]
Y2 --> C2["C: keys > y"]
end
before ==>|"rotate right"| after
Both inorder sequences read A x B y C; only depths changed: A moved up a level, C down a level, B changed parent. A left rotation is the mirror image and undoes a right rotation:
flowchart TB
subgraph before["Before: left-rotate at x"]
X1(("x")) --> A1["A: keys < x"]
X1 --> Y1(("y"))
Y1 --> B1["B: x < keys < y"]
Y1 --> C1["C: keys > y"]
end
subgraph after["After: y is the subtree root"]
Y2(("y")) --> X2(("x"))
Y2 --> C2["C: keys > y"]
X2 --> A2["A: keys < x"]
X2 --> B2["B: x < keys < y"]
end
before ==>|"rotate left"| after
A rotation rewires three pointers (y.left, x.right, and y's parent's pointer) and recomputes the cached data of y then x: work regardless of subtree sizes.
Double rotations. A single rotation fixes a "straight line" imbalance (left child of a left child, or right child of a right child). It does not fix a "zig-zag" (the right child of a left child): rotating right at the top just moves the zig-zag to the other side. The fix is to first rotate the child so the zig-zag becomes a straight line, then rotate the top:
flowchart LR
subgraph s1["1. zig-zag: z left-heavy, x right-heavy"]
Z1(("z")) --> X1(("x"))
X1 --> Y1(("y"))
end
subgraph s2["2. after left-rotate at x"]
Z2(("z")) --> Y2(("y"))
Y2 --> X2(("x"))
end
subgraph s3["3. after right-rotate at z"]
Y3(("y")) --> X3(("x"))
Y3 --> Z3(("z"))
end
s1 ==> s2 ==> s3
The middle key y ends up on top with x and z as its children. A double rotation is two single rotations, so it is still .
AVL: the invariant
An AVL tree is a BST in which every node satisfies . The leaves can sit at different depths, but at no node may one side be two or more levels taller than the other.
Why this invariant? Because it is the weakest height-difference rule that still forces logarithmic height, and because a single insert can break it by at most one level at each ancestor, which a rotation can absorb.
Red-black: the invariant
A red-black tree is a BST in which every node is coloured red or black and:
- The root is black.
- Every
nilleaf (the empty subtree positions) is black. - A red node has no red child (no two reds in a row).
- Every path from a given node down to a
nilleaf passes through the same number of black nodes. That number, not counting the node itself, is its black-height .
Rule 4 says the tree is perfectly balanced if you ignore red nodes. Rule 3 says red nodes can at most double a path's length. Together they bound the height at . You will prove it below.
The colours cost one bit per node (the Linux kernel hides it in the low bit of the parent pointer) and are read only when rebalancing.
Mechanics
AVL insertion
Insert as in a plain BST, creating a new leaf. Then walk back up the path to the root, recomputing each ancestor's height. The first ancestor z whose balance factor becomes is fixed by one of four cases, named by the path from z toward the new key:
| Case | Shape | bf(z) | bf(child) | Fix |
|---|---|---|---|---|
| LL | new key in left subtree of left child | +2 | ≥ 0 | right-rotate at z |
| RR | new key in right subtree of right child | −2 | ≤ 0 | left-rotate at z |
| LR | new key in right subtree of left child | +2 | < 0 | left-rotate at child, then right-rotate at z |
| RL | new key in left subtree of right child | −2 | > 0 | right-rotate at child, then left-rotate at z |
flowchart TD
S["insert key as a BST leaf"] --> U["walk up, update heights"]
U --> Q{"bf(node) is +2 or -2?"}
Q -->|"no"| R{"reached root?"}
R -->|"no"| U
R -->|"yes"| D(["done"])
Q -->|"+2"| L{"bf(left child) < 0?"}
Q -->|"-2"| RR{"bf(right child) > 0?"}
L -->|"yes: LR"| LR1["left-rotate at left child"] --> LL1["right-rotate at node"]
L -->|"no: LL"| LL1
RR -->|"yes: RL"| RL1["right-rotate at right child"] --> RR1["left-rotate at node"]
RR -->|"no: RR"| RR1
LL1 --> D
RR1 --> D
The key fact, proved in the Correctness section: after an insertion, one single or double rotation at the lowest unbalanced ancestor restores the subtree to its pre-insert height, so no ancestor above it changes height and the walk can stop. Insertion therefore does at most one rebalancing (two rotations), plus height updates.
Trace: inserting 10, 20, 30, 40, 50, 25 into an empty AVL tree. Computed by script. Trees are written root(left,right) with . for an empty child.
| Insert | Path walked | First unbalanced node (bf) | Case | Rotation(s) | Tree after | Height |
|---|---|---|---|---|---|---|
| 10 | — | — | — | — | 10 | 1 |
| 20 | 10 | — | — | — | 10(.,20) | 2 |
| 30 | 10 → 20 | 10 (−2) | RR | left-rotate at 10 | 20(10,30) | 2 |
| 40 | 20 → 30 | — | — | — | 20(10,30(.,40)) | 3 |
| 50 | 20 → 30 → 40 | 30 (−2) | RR | left-rotate at 30 | 20(10,40(30,50)) | 3 |
| 25 | 20 → 40 → 30 | 20 (−2) | RL | right-rotate at 40, then left-rotate at 20 | 30(20(10,25),40(.,50)) | 3 |
At insert 50 the walk up meets 30 (balance −2) first and fixes it, so the root 20 is never seen unbalanced. Insert 25 is a zig-zag (right at 20, left at 40): a single left rotation at 20 would leave the tree unbalanced the other way, so the double rotation puts the middle key, 30, on top.
AVL deletion (summary)
Delete as in a plain BST: a node with zero or one child is spliced out; a node with two children takes its inorder successor's key, and the successor (which has no left child) is spliced out of the right subtree. Then walk up from the parent of the node physically removed, updating heights and applying the same four cases. Two differences from insertion:
- The child's balance factor can be 0 after a deletion. Treat it as a straight line: bf(child) = 0 under a +2 node is case LL, not LR.
- A rotation after a deletion can reduce the subtree's height, so the imbalance can propagate: the walk continues to the root, and one delete may rotate at levels (as when deleting from a minimal "Fibonacci" AVL tree).
Red-black insertion
Insert as in a plain BST and colour the new node red. Colouring it red keeps rule 4 (black-heights) intact automatically; the only rules that can break are rule 1 (if the tree was empty) and rule 3 (if the parent is red). The fix-up walks up while the current node z and its parent are both red. Let g be the grandparent (it exists and is black, because the parent is red and the root is black) and u the uncle, the grandparent's other child. With the parent on the left of g (mirror everything for the right):
| Case | Condition | Action | Effect |
|---|---|---|---|
| 1. Red uncle | u is red | recolour parent and u black, g red; set z = g and continue | pushes the red-red problem two levels up; no rotation |
| 2. Black uncle, triangle | u black, z is a right child | left-rotate at the parent, set z to the old parent | converts to case 3 |
| 3. Black uncle, line | u black, z is a left child | recolour parent black, g red; right-rotate at g | fixes the violation; loop ends |
Finally colour the root black. Case 1 can repeat up the tree (only recolouring), but cases 2 and 3 happen at most once and terminate, so an insertion performs at most two rotations. This is CLRS's RB-INSERT-FIXUP (§13.3).
flowchart TD
I["BST insert, colour new node z red"] --> W{"parent of z red?"}
W -->|"no"| F["colour root black"] --> D(["done"])
W -->|"yes"| U{"uncle red?"}
U -->|"yes: case 1"| C1["parent, uncle black. grandparent red. z = grandparent"] --> W
U -->|"no"| T{"z on the inside: triangle?"}
T -->|"yes: case 2"| C2["rotate at parent, z = old parent"] --> C3
T -->|"no"| C3["case 3: parent black, grandparent red, rotate at grandparent"]
C3 --> F
Trace: inserting 10, 20, 30, 15, 25, 5, 1, 3 into an empty red-black tree. Computed by script with the CLRS algorithm. B = black, R = red; bh is the root's black-height counting nil leaves.
| Insert | Fix-up applied | Tree after | bh |
|---|---|---|---|
| 10 | root recoloured black | 10B | 1 |
| 20 | none (parent black) | 10B(.,20R) | 1 |
| 30 | case 3 (mirrored, line): recolour 20 black, 10 red; left-rotate at 10 | 20B(10R,30R) | 1 |
| 15 | case 1: uncle 30 red; recolour 10, 30 black and 20 red; root recoloured black | 20B(10B(.,15R),30B) | 2 |
| 25 | none (parent 30 black) | 20B(10B(.,15R),30B(25R,.)) | 2 |
| 5 | none (parent 10 black) | 20B(10B(5R,15R),30B(25R,.)) | 2 |
| 1 | case 1: uncle 15 red; recolour 5, 15 black and 10 red | 20B(10R(5B(1R,.),15B),30B(25R,.)) | 2 |
| 3 | case 2: triangle, left-rotate at 1; case 3: recolour 3 black, 5 red; right-rotate at 5 | 20B(10R(3B(1R,5R),15B),30B(25R,.)) | 2 |
Insert 15 is where the black-height grows: case 1 pushes red up to the root, which is recoloured black, adding one black node to every path at once. That is the only way black-height grows, just as a B-tree grows only at the root.
Red-black deletion (summary)
Splice out the node as in a BST. If the node physically removed was red, nothing breaks. If it was black, every path through its position lost a black node; CLRS treats this as an "extra black" on the replacing child and pushes it up with four cases (sibling red; sibling black with two black children; near child red; far child red). Only the "two black children" case repeats, and it only recolours; at most three rotations happen in total. Know the shape: insertion breaks rule 3, deletion breaks rule 4, and each fix-up pushes the problem rootward until a rotation absorbs it.
The 2-3-4 tree behind every red-black tree
A 2-3-4 tree (a B-tree of order 4) is a search tree whose nodes hold 1, 2 or 3 keys and have 2, 3 or 4 children, with every leaf at the same depth. A red-black tree is a 2-3-4 tree written in binary: merge every red node into its black parent and each black node with its red children becomes one 2-, 3- or 4-node.
flowchart LR
subgraph rb["Red-black fragment"]
B1(("20 B")) --> R1(("10 R"))
B1 --> R2(("30 R"))
B2(("50 B")) --> R3(("40 R"))
B3(("70 B"))
end
subgraph t234["Same keys as 2-3-4 nodes"]
N4["4-node: 10 | 20 | 30"]
N3["3-node: 40 | 50"]
N2["2-node: 70"]
end
rb ==>|"absorb red children into black parent"| t234
Every rule translates:
| Red-black rule | 2-3-4 meaning |
|---|---|
| Rule 3: no red-red | A 2-3-4 node holds at most three keys (one black plus at most two reds) |
| Rule 4: equal black-height | Every 2-3-4 leaf is at the same depth |
| Case 1 recolour (red uncle) | Splitting a full 4-node and pushing its middle key up to the parent |
| Cases 2/3 rotation | Turning a 3-node into a 4-node by absorbing the new key, re-drawn so the middle key is black |
| Root recoloured black, bh + 1 | The root splits and the tree grows one level |
This is how you derive the cases instead of memorizing them. A 3-node has two binary encodings (red child left or right), hence the mirror-image cases; restrict 3-nodes to one encoding and the cases halve.
Left-leaning red-black trees
Sedgewick's left-leaning red-black (LLRB) tree adds one rule: a red link always leans left. Now each 2-3-4 node (or, in the simplest variant, each 2-3 node) has exactly one binary encoding, and insertion becomes three lines appended to the ordinary recursive BST insert, applied on the way back up:
- If the right child is red and the left is not, rotate left (fix a right-leaning red).
- If the left child and its left child are both red, rotate right (fix two reds in a row).
- If both children are red, flip colours (split a temporary 4-node).
That is the version in Sedgewick & Wayne, Algorithms (4th ed., §3.3), and the shortest correct balanced BST you can write in an interview (runnable code in Variations). The price: more rotations than classic red-black trees and a still-intricate deletion; benchmarks such as Eddie Kohler's "Left-leaning red-black trees considered harmful" found classic implementations faster. Use LLRB for clarity, the classic algorithm for a library.
From binary to many-way: B-trees
A B-tree of minimum degree (CLRS's parametrization) is a search tree in which:
- Every node except the root holds between and keys in sorted order; an internal node with keys has children, and the keys separate the children's key ranges.
- The root holds between 1 and keys (if the tree is non-empty).
- All leaves are at the same depth.
Search binary-searches the keys inside a node, then descends into one child. Insert descends to a leaf and inserts the key there; if a node is full ( keys) it is split: its median key moves up into the parent and the remaining keys form two nodes of keys each. CLRS splits full nodes on the way down (proactive splitting), so the parent always has room for the promoted median. If the root splits, a new root with one key is created: B-trees grow at the root, never at the leaves, which is exactly why all leaves stay at the same depth.
flowchart TB
subgraph before["Before: insert 25, t = 2, leaf is full"]
P1["10 | 40"] --> L1["5"]
P1 --> M1["20 | 30 | 35"]
P1 --> R1["50"]
end
subgraph after["After: split, median 30 moves up, 25 goes left"]
P2["10 | 30 | 40"] --> L2["5"]
P2 --> M2["20 | 25"]
P2 --> M3["35"]
P2 --> R2["50"]
end
before ==>|"split full child, then insert"| after
A 2-3-4 tree is the B-tree with . Database B-trees use in the hundreds, sized so that one node fills one disk page. The "why" is in Real-world uses; a runnable B-tree insert is in Variations.
The ladder: brute force → better → optimal
The problem: maintain a dynamic set of keys under insert, delete, search and ordered queries (successor, k-th smallest), with a worst-case bound per operation.
Rung 1: sorted array
Keep the keys sorted in a dynamic array. Search, floor and ceiling are , k-th is , but insert and delete shift elements: each, about moves for 100,000 random inserts. Fine for read-mostly data, hopeless for a write-heavy stream.
Rung 2: plain BST
Inserts and deletes no longer shift anything: each. With random insertion order (about 50 for a million keys) and average depth about . But the bound is on expected height over random orders, and real inputs are not random: inserting already-sorted keys produces . One sorted batch load turns every subsequent operation into . There is no worst-case guarantee.
Rung 3: rebuild periodically
Rebuild the tree perfectly balanced whenever it gets too tall. Rebuilding the whole tree is and can be triggered repeatedly; rebuilding only the subtree that became unbalanced is the scapegoat tree: height, but updates only amortized .
Rung 4: balanced BST (AVL or red-black)
Maintain a local invariant on every update with rotations per insertion and bookkeeping. Every operation is worst case: for a million keys, at most 28 levels for AVL and at most 39 for red-black, against 20 for a perfect tree. Augment each node with its subtree size and k-th smallest and rank become too.
Rung 5 (on disk): B-tree
When nodes live in pages and a page read costs about a million times more than a comparison, the metric changes from comparisons to page reads. A B-tree with fanout around 1,000 answers a lookup among a billion keys in three or four page reads instead of thirty.
| Approach | Search | Insert / delete | k-th / rank | Worst-case guarantee | Notes |
|---|---|---|---|---|---|
| Sorted array | / | yes | Best for static data | ||
| Plain BST | with sizes | no: up to | Expected on random input | ||
| Scapegoat tree | amortized | with sizes | height yes, updates amortized | No per-node balance field | |
| AVL tree | , | with sizes | yes | Shallowest; ≤ 2 rotations per insert, per delete | |
| Red-black tree | , | with sizes | yes | ≤ 2 rotations per insert, ≤ 3 per delete | |
| B-tree, fanout | page reads | page writes | with counts | yes | The on-disk answer |
Correctness
Rotations preserve the BST property
Take the right rotation at y with left child x and subtrees A, B, C as in the diagram. Before: every key in A is less than x; every key in B is between x and y (it is in x's right subtree and y's left subtree); every key in C is greater than y. After: x's left subtree is A (keys < x ✓); x's right subtree is y with B and C, all > x ✓; y's left subtree is B, all < y ✓; y's right subtree is C, all > y ✓. Subtrees A, B, C are internally unchanged, and the rest of the tree sees the same set of keys under the same parent pointer. So the inorder sequence A x B y C is unchanged and the tree is still a BST. The left rotation is symmetric.
The AVL height bound
Let be the minimum number of nodes in an AVL tree of height . A minimal tree of height has a root, one subtree of height (some subtree must reach that height) and, to use as few nodes as possible, the other subtree as short as the invariant allows, height . Both subtrees must themselves be minimal. So
The first values are 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143. Adding 1 to both sides gives , the Fibonacci recurrence, and matching initial values gives
where . These minimal trees are called Fibonacci trees. Since with , any AVL tree with nodes and height satisfies
Solving for : , so . With and ,
This is the bound in Knuth, The Art of Computer Programming, Vol. 3, §6.2.3 (where it is stated for the node-counting height used here). A script confirms it for every up to 44 and gives concrete maxima: an AVL tree with 1,000 nodes has height at most 14, with a million at most 28, with a billion at most 42. A perfect tree would need 10, 20 and 30. AVL trees are at most about 44% taller than perfect, and on typical inputs much closer.
AVL insertion: one rebalance restores the old height
Let z be the lowest ancestor of the new node with , say with left child x. Before the insertion, was (it changed by one), so if x's subtree had height before, z's right subtree has height and z had height . After the insertion, x's subtree has height , and since x is not itself unbalanced and its height grew, the insertion went into exactly one of its subtrees, which now has height while the other has height .
- LL (the taller subtree of
xis its left, height ; its right has height ): after a right rotation atz,zhas children of heights (x's old right) and (z's right), so height ;xhas children of heights and , so height , balance 0. - LR (
x's right childwhas height ,x's left has height ):w's two subtrees have heights and in some order (or both 0 ifwis the new node). After the double rotation,wis on top with childrenx(subtrees of heights and at most ) andz(subtrees of heights at most and ); both have height , sowhas height , balance 0.
In both cases the rebalanced subtree has height , exactly its height before the insertion. Ancestors above z therefore see no height change and remain balanced, which is why one fix suffices. The four cases are mirror pairs, so RR and RL follow by symmetry. Combined with the rotation lemma, the result is a valid AVL tree.
The red-black height bound
Lemma 1. The subtree rooted at any node contains at least internal nodes.
Proof by induction on the height of . If is a nil leaf, and the subtree has internal nodes. Otherwise is internal with two children. Each child has black-height (if is red) or (if is black), so at least in both cases. By the induction hypothesis each child's subtree has at least internal nodes, so 's subtree has at least . ∎
Lemma 2. On any root-to-leaf path, at least half the nodes (not counting the root, which is black anyway) are black.
Proof. Rule 3: every red node's child is black, so reds cannot be consecutive and at most every other node on the path is red. ∎
Theorem. A red-black tree with internal nodes has height at most .
Proof. Let be the height (in internal nodes along the longest path). By Lemma 2, . By Lemma 1, . Rearranging, . ∎
This is CLRS Lemma 13.1. For a million keys the bound is 39.9 levels. Real trees are much shallower: in a script, 100,000 random insertions produced red-black height 20 (AVL: also 20), while 100,000 sorted insertions produced red-black height 31 against AVL's 17, the minimum possible. Sorted input is exactly where the looser invariant shows.
Red-black insertion: why the fix-up is correct
The loop invariant (CLRS §13.3): at the start of each iteration, z is red; if z's parent is the root, it is black; and there is at most one violation, either rule 1 (z is the red root) or rule 3 (z and its parent are both red). Rule 4 holds throughout because the new node was red, case 1 swaps the colours of a black node and its two red children (each path through those nodes keeps the same black count), and cases 2 and 3 are rotations combined with recolourings that keep the black count on each of the subtrees A, B, C, … unchanged. Case 1 moves the violation two levels up; cases 2/3 eliminate it. Since the tree has finite height, the loop terminates, and the final "colour the root black" fixes a possible rule 1 violation without breaking rule 4 (it adds one black to every path at once).
B-tree height
A B-tree of minimum degree with keys and height (counting levels below the root, CLRS's convention) satisfies . Proof sketch: the root has at least 2 children, each other internal node at least , so level has at least nodes, each with at least keys. Summing, . With in the hundreds this is a height of 2 to 4 for any realistic table.
Complexity
| Operation | AVL | Red-black | Notes |
|---|---|---|---|
| Search, floor, ceiling, successor | worst | worst | AVL path ≤ 1.44 log₂ n, RB ≤ 2 log₂ n |
| Insert | ; ≤ 1 single or double rotation | ; ≤ 2 rotations | Plus height updates or recolourings |
| Delete | ; up to rotations | ; ≤ 3 rotations | RB recolourings can climb to the root |
| Min / max | , or with cached pointers | same | Linux's rb_root_cached caches the leftmost node |
| k-th smallest, rank | with subtree sizes | same | Rotations must update sizes |
| Build from sorted input | by building from the middle | Inserting one by one is | |
| Inorder traversal | |||
| Space | nodes + 1 small integer (height or balance) each | nodes + 1 bit each | Plus 2 child pointers (3 with parent pointers) |
Amortized behaviour. For red-black (and 2-3-4) trees the amortized number of recolourings and rotations per update is over any sequence starting from an empty tree; AVL deletions lack this guarantee. Fewer structural changes is one reason red-black trees are the usual base for augmented trees, where every change forces recomputing a field.
Constants and cache behaviour. A balanced BST chases pointers: each level is a dependent load to a node probably not in cache, so a lookup in a million-key tree costs roughly 20 to 30 cache misses. An in-memory B-tree (Rust's BTreeMap, Abseil's btree_map) packs many keys per node and turns most of those misses into in-cache scans. That is why the textbook answer is often not the fastest in-memory ordered map. A 64-bit red-black node with parent pointer also carries 24 bytes of pointers plus the colour, before key and value.
Implementation
A complete AVL tree storing a set of integers: insert, remove, contains, inorder, height, and check, which walks the whole tree and fails if the BST order, a stored height, the AVL balance or the size is wrong. The tests run the trace above, insert 1 to 1,023 in sorted order (the input that turns a plain BST into a list; here the height must be exactly 10), delete all the even keys, then run 2,000 random inserts and deletes from the same deterministic generator (MINSTD, ) in all four languages, checking every invariant after every operation against a boolean reference array.
import math
from dataclasses import dataclass
@dataclass
class Node:
key: int
left: "Node | None" = None
right: "Node | None" = None
height: int = 1
def h(n: Node | None) -> int:
return n.height if n else 0
def update(n: Node) -> None:
n.height = 1 + max(h(n.left), h(n.right))
def balance(n: Node) -> int:
return h(n.left) - h(n.right)
def rotate_right(y: Node) -> Node:
x = y.left
assert x is not None
y.left, x.right = x.right, y # x's right subtree (keys between x and y) moves under y
update(y) # y is now below x: update it first
update(x)
return x
def rotate_left(x: Node) -> Node:
y = x.right
assert y is not None
x.right, y.left = y.left, x
update(x)
update(y)
return y
def rebalance(n: Node) -> Node:
update(n)
b = balance(n)
if b > 1: # left-heavy
if balance(n.left) < 0: # LR: straighten first
n.left = rotate_left(n.left)
return rotate_right(n) # LL (also bf(child) == 0 after a delete)
if b < -1: # right-heavy
if balance(n.right) > 0: # RL: straighten first
n.right = rotate_right(n.right)
return rotate_left(n) # RR
return n
class AVLTree:
def __init__(self) -> None:
self.root: Node | None = None
self.size = 0
def contains(self, key: int) -> bool:
n = self.root
while n:
if key == n.key:
return True
n = n.left if key < n.key else n.right
return False
def insert(self, key: int) -> None:
def go(n: Node | None) -> Node:
if n is None:
self.size += 1
return Node(key)
if key < n.key:
n.left = go(n.left)
elif key > n.key:
n.right = go(n.right)
else:
return n # duplicate: set semantics
return rebalance(n)
self.root = go(self.root)
def remove(self, key: int) -> None:
def go(n: Node | None, key: int) -> Node | None:
if n is None:
return None # key absent: no-op
if key < n.key:
n.left = go(n.left, key)
elif key > n.key:
n.right = go(n.right, key)
else:
if n.left is None or n.right is None:
self.size -= 1
return n.left or n.right # 0 or 1 child: splice out
s = n.right # 2 children: copy successor, delete it
while s.left:
s = s.left
n.key = s.key
n.right = go(n.right, s.key)
return rebalance(n)
self.root = go(self.root, key)
def inorder(self) -> list[int]:
out: list[int] = []
stack: list[Node] = []
n = self.root
while stack or n:
while n:
stack.append(n)
n = n.left
n = stack.pop()
out.append(n.key)
n = n.right
return out
def height(self) -> int:
return h(self.root)
def check(self) -> None:
"""Raise if BST order, stored heights, AVL balance or size are wrong."""
def go(n: Node | None, lo: int | None, hi: int | None) -> tuple[int, int]:
if n is None:
return 0, 0
if (lo is not None and n.key <= lo) or (hi is not None and n.key >= hi):
raise AssertionError(f"BST order broken at {n.key}")
lh, lc = go(n.left, lo, n.key)
rh, rc = go(n.right, n.key, hi)
if n.height != 1 + max(lh, rh):
raise AssertionError(f"stale height at {n.key}")
if abs(lh - rh) > 1:
raise AssertionError(f"AVL balance broken at {n.key}")
return n.height, lc + rc + 1
_, count = go(self.root, None, None)
if count != self.size:
raise AssertionError("size mismatch")
if __name__ == "__main__":
t = AVLTree()
for k in [10, 20, 30, 40, 50, 25]:
t.insert(k)
t.check()
assert t.inorder() == [10, 20, 25, 30, 40, 50]
assert t.root is not None and t.root.key == 30 and t.height() == 3
t.insert(30) # duplicate ignored
assert t.size == 6 and t.contains(25) and not t.contains(35)
t.remove(35) # absent key: no-op
assert t.size == 6
t = AVLTree()
for k in range(1, 1024): # sorted input: a plain BST would be a 1023-deep list
t.insert(k)
t.check()
assert t.height() == 10
for k in range(2, 1024, 2):
t.remove(k)
t.check()
assert t.size == 512 and t.height() == 10 and not t.contains(512) and t.contains(511)
x = 42 # MINSTD generator, identical in all four languages
def nxt() -> int:
global x
x = x * 48271 % 2147483647
return x
t, ref = AVLTree(), [False] * 500
for _ in range(2000):
k, op = nxt() % 500, nxt() % 3
if op == 0:
t.remove(k); ref[k] = False
else:
t.insert(k); ref[k] = True
t.check()
assert t.inorder() == [i for i in range(500) if ref[i]]
assert t.size == 344 and t.height() == 10
assert t.height() < 1.4405 * math.log2(t.size + 2) - 0.3277
print("AVL OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class AVLTree {
static final class Node {
int key, height = 1;
Node left, right;
Node(int key) { this.key = key; }
}
Node root;
int size;
static int h(Node n) { return n == null ? 0 : n.height; }
static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
static int balance(Node n) { return h(n.left) - h(n.right); }
static Node rotateRight(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
update(y);
update(x);
return x;
}
static Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
update(x);
update(y);
return y;
}
static Node rebalance(Node n) {
update(n);
int b = balance(n);
if (b > 1) {
if (balance(n.left) < 0) n.left = rotateLeft(n.left); // LR
return rotateRight(n); // LL
}
if (b < -1) {
if (balance(n.right) > 0) n.right = rotateRight(n.right); // RL
return rotateLeft(n); // RR
}
return n;
}
boolean contains(int key) {
Node n = root;
while (n != null) {
if (key == n.key) return true;
n = key < n.key ? n.left : n.right;
}
return false;
}
void insert(int key) { root = insert(root, key); }
private Node insert(Node n, int key) {
if (n == null) { size++; return new Node(key); }
if (key < n.key) n.left = insert(n.left, key);
else if (key > n.key) n.right = insert(n.right, key);
else return n; // duplicate: set semantics
return rebalance(n);
}
void remove(int key) { root = remove(root, key); }
private Node remove(Node n, int key) {
if (n == null) return null; // key absent: no-op
if (key < n.key) n.left = remove(n.left, key);
else if (key > n.key) n.right = remove(n.right, key);
else {
if (n.left == null || n.right == null) { // 0 or 1 child: splice out
size--;
return n.left != null ? n.left : n.right;
}
Node s = n.right; // 2 children: copy successor, delete it
while (s.left != null) s = s.left;
n.key = s.key;
n.right = remove(n.right, s.key);
}
return rebalance(n);
}
List<Integer> inorder() {
List<Integer> out = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
Node n = root;
while (n != null || !stack.isEmpty()) {
while (n != null) { stack.push(n); n = n.left; }
n = stack.pop();
out.add(n.key);
n = n.right;
}
return out;
}
int height() { return h(root); }
/** Throws if BST order, stored heights or AVL balance are wrong. Returns {height, count}. */
private static int[] check(Node n, long lo, long hi) {
if (n == null) return new int[]{0, 0};
if (n.key <= lo || n.key >= hi) throw new IllegalStateException("BST order broken at " + n.key);
int[] l = check(n.left, lo, n.key), r = check(n.right, n.key, hi);
if (n.height != 1 + Math.max(l[0], r[0])) throw new IllegalStateException("stale height at " + n.key);
if (Math.abs(l[0] - r[0]) > 1) throw new IllegalStateException("AVL balance broken at " + n.key);
return new int[]{n.height, l[1] + r[1] + 1};
}
void check() {
if (check(root, Long.MIN_VALUE, Long.MAX_VALUE)[1] != size) throw new IllegalStateException("size mismatch");
}
static void expect(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
static long x = 42; // MINSTD generator, identical in all four languages
static int next() { x = x * 48271 % 2147483647L; return (int) x; }
public static void main(String[] args) {
AVLTree t = new AVLTree();
for (int k : new int[]{10, 20, 30, 40, 50, 25}) { t.insert(k); t.check(); }
expect(t.inorder().equals(List.of(10, 20, 25, 30, 40, 50)), "inorder");
expect(t.root.key == 30 && t.height() == 3, "shape");
t.insert(30);
expect(t.size == 6 && t.contains(25) && !t.contains(35), "contains");
t.remove(35);
expect(t.size == 6, "remove absent");
t = new AVLTree();
for (int k = 1; k < 1024; k++) t.insert(k);
t.check();
expect(t.height() == 10, "sorted-input height");
for (int k = 2; k < 1024; k += 2) t.remove(k);
t.check();
expect(t.size == 512 && t.height() == 10 && !t.contains(512) && t.contains(511), "after removals");
t = new AVLTree();
boolean[] ref = new boolean[500];
for (int i = 0; i < 2000; i++) {
int k = next() % 500, op = next() % 3;
if (op == 0) { t.remove(k); ref[k] = false; } else { t.insert(k); ref[k] = true; }
t.check();
}
List<Integer> want = new ArrayList<>();
for (int i = 0; i < 500; i++) if (ref[i]) want.add(i);
expect(t.inorder().equals(want), "random ops inorder");
expect(t.size == 344 && t.height() == 10, "random ops size/height");
expect(t.height() < 1.4405 * (Math.log(t.size + 2) / Math.log(2)) - 0.3277, "height bound");
System.out.println("AVL OK");
}
}
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <stack>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
class AVLTree {
struct Node {
int key;
int height = 1;
Node* left = nullptr;
Node* right = nullptr;
explicit Node(int k) : key(k) {}
};
Node* root_ = nullptr;
int size_ = 0;
static int h(const Node* n) { return n ? n->height : 0; }
static void update(Node* n) { n->height = 1 + std::max(h(n->left), h(n->right)); }
static int balance(const Node* n) { return h(n->left) - h(n->right); }
static Node* rotateRight(Node* y) {
Node* x = y->left;
y->left = x->right;
x->right = y;
update(y);
update(x);
return x;
}
static Node* rotateLeft(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
update(x);
update(y);
return y;
}
static Node* rebalance(Node* n) {
update(n);
int b = balance(n);
if (b > 1) {
if (balance(n->left) < 0) n->left = rotateLeft(n->left); // LR
return rotateRight(n); // LL
}
if (b < -1) {
if (balance(n->right) > 0) n->right = rotateRight(n->right); // RL
return rotateLeft(n); // RR
}
return n;
}
Node* insert(Node* n, int key) {
if (!n) { ++size_; return new Node(key); }
if (key < n->key) n->left = insert(n->left, key);
else if (key > n->key) n->right = insert(n->right, key);
else return n; // duplicate: set semantics
return rebalance(n);
}
Node* remove(Node* n, int key) {
if (!n) return nullptr; // key absent: no-op
if (key < n->key) n->left = remove(n->left, key);
else if (key > n->key) n->right = remove(n->right, key);
else {
if (!n->left || !n->right) { // 0 or 1 child: splice out
Node* child = n->left ? n->left : n->right;
delete n;
--size_;
return child;
}
Node* s = n->right; // 2 children: copy successor, delete it
while (s->left) s = s->left;
n->key = s->key;
n->right = remove(n->right, s->key);
}
return rebalance(n);
}
// Throws if BST order, stored heights or AVL balance are wrong. Returns {height, count}.
static std::pair<int, int> check(const Node* n, std::int64_t lo, std::int64_t hi) {
if (!n) return {0, 0};
if (n->key <= lo || n->key >= hi) throw std::logic_error("BST order broken at " + std::to_string(n->key));
auto [lh, lc] = check(n->left, lo, n->key);
auto [rh, rc] = check(n->right, n->key, hi);
if (n->height != 1 + std::max(lh, rh)) throw std::logic_error("stale height at " + std::to_string(n->key));
if (std::abs(lh - rh) > 1) throw std::logic_error("AVL balance broken at " + std::to_string(n->key));
return {n->height, lc + rc + 1};
}
static void destroy(Node* n) {
if (!n) return;
destroy(n->left);
destroy(n->right);
delete n;
}
public:
AVLTree() = default;
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
~AVLTree() { destroy(root_); }
void insert(int key) { root_ = insert(root_, key); }
void remove(int key) { root_ = remove(root_, key); }
int size() const { return size_; }
int height() const { return h(root_); }
int rootKey() const { return root_->key; }
bool contains(int key) const {
const Node* n = root_;
while (n) {
if (key == n->key) return true;
n = key < n->key ? n->left : n->right;
}
return false;
}
std::vector<int> inorder() const {
std::vector<int> out;
std::stack<const Node*> st;
const Node* n = root_;
while (n || !st.empty()) {
while (n) { st.push(n); n = n->left; }
n = st.top();
st.pop();
out.push_back(n->key);
n = n->right;
}
return out;
}
void check() const {
auto lim = std::numeric_limits<std::int64_t>::max();
if (check(root_, -lim, lim).second != size_) throw std::logic_error("size mismatch");
}
};
static void expect(bool ok, const char* what) {
if (!ok) {
std::cerr << "FAILED: " << what << "\n";
std::exit(1);
}
}
static std::int64_t x = 42; // MINSTD generator, identical in all four languages
static int nextRand() {
x = x * 48271 % 2147483647;
return static_cast<int>(x);
}
int main() {
{
AVLTree t;
for (int k : {10, 20, 30, 40, 50, 25}) { t.insert(k); t.check(); }
expect(t.inorder() == std::vector<int>{10, 20, 25, 30, 40, 50}, "inorder");
expect(t.rootKey() == 30 && t.height() == 3, "shape");
t.insert(30);
expect(t.size() == 6 && t.contains(25) && !t.contains(35), "contains");
t.remove(35);
expect(t.size() == 6, "remove absent");
}
{
AVLTree t;
for (int k = 1; k < 1024; ++k) t.insert(k);
t.check();
expect(t.height() == 10, "sorted-input height");
for (int k = 2; k < 1024; k += 2) t.remove(k);
t.check();
expect(t.size() == 512 && t.height() == 10 && !t.contains(512) && t.contains(511), "after removals");
}
{
AVLTree t;
std::vector<bool> ref(500, false);
for (int i = 0; i < 2000; ++i) {
int k = nextRand() % 500;
int op = nextRand() % 3;
if (op == 0) { t.remove(k); ref[k] = false; } else { t.insert(k); ref[k] = true; }
t.check();
}
std::vector<int> want;
for (int i = 0; i < 500; ++i)
if (ref[i]) want.push_back(i);
expect(t.inorder() == want, "random ops inorder");
expect(t.size() == 344 && t.height() == 10, "random ops size/height");
expect(t.height() < 1.4405 * std::log2(t.size() + 2) - 0.3277, "height bound");
}
std::cout << "AVL OK\n";
}
class AVLNode {
key: number;
height = 1;
left: AVLNode | null = null;
right: AVLNode | null = null;
constructor(key: number) {
this.key = key;
}
}
const h = (n: AVLNode | null): number => (n ? n.height : 0);
const update = (n: AVLNode): void => {
n.height = 1 + Math.max(h(n.left), h(n.right));
};
const balance = (n: AVLNode): number => h(n.left) - h(n.right);
function rotateRight(y: AVLNode): AVLNode {
const x = y.left!;
y.left = x.right;
x.right = y;
update(y);
update(x);
return x;
}
function rotateLeft(x: AVLNode): AVLNode {
const y = x.right!;
x.right = y.left;
y.left = x;
update(x);
update(y);
return y;
}
function rebalance(n: AVLNode): AVLNode {
update(n);
const b = balance(n);
if (b > 1) {
if (balance(n.left!) < 0) n.left = rotateLeft(n.left!); // LR
return rotateRight(n); // LL
}
if (b < -1) {
if (balance(n.right!) > 0) n.right = rotateRight(n.right!); // RL
return rotateLeft(n); // RR
}
return n;
}
class AVLTree {
root: AVLNode | null = null;
size = 0;
contains(key: number): boolean {
let n = this.root;
while (n) {
if (key === n.key) return true;
n = key < n.key ? n.left : n.right;
}
return false;
}
insert(key: number): void {
const go = (n: AVLNode | null): AVLNode => {
if (!n) {
this.size++;
return new AVLNode(key);
}
if (key < n.key) n.left = go(n.left);
else if (key > n.key) n.right = go(n.right);
else return n; // duplicate: set semantics
return rebalance(n);
};
this.root = go(this.root);
}
remove(key: number): void {
const go = (n: AVLNode | null, k: number): AVLNode | null => {
if (!n) return null; // key absent: no-op
if (k < n.key) n.left = go(n.left, k);
else if (k > n.key) n.right = go(n.right, k);
else {
if (!n.left || !n.right) {
this.size--; // 0 or 1 child: splice out
return n.left ?? n.right;
}
let s = n.right; // 2 children: copy successor, delete it
while (s.left) s = s.left;
n.key = s.key;
n.right = go(n.right, s.key);
}
return rebalance(n);
};
this.root = go(this.root, key);
}
inorder(): number[] {
const out: number[] = [];
const stack: AVLNode[] = [];
let n = this.root;
while (n || stack.length) {
while (n) {
stack.push(n);
n = n.left;
}
n = stack.pop()!;
out.push(n.key);
n = n.right;
}
return out;
}
height(): number {
return h(this.root);
}
/** Throws if BST order, stored heights, AVL balance or size are wrong. */
check(): void {
const go = (n: AVLNode | null, lo: number, hi: number): [number, number] => {
if (!n) return [0, 0];
if (n.key <= lo || n.key >= hi) throw new Error(`BST order broken at ${n.key}`);
const [lh, lc] = go(n.left, lo, n.key);
const [rh, rc] = go(n.right, n.key, hi);
if (n.height !== 1 + Math.max(lh, rh)) throw new Error(`stale height at ${n.key}`);
if (Math.abs(lh - rh) > 1) throw new Error(`AVL balance broken at ${n.key}`);
return [n.height, lc + rc + 1];
};
if (go(this.root, -Infinity, Infinity)[1] !== this.size) throw new Error("size mismatch");
}
}
function expect(ok: boolean, what: string): void {
if (!ok) throw new Error(`FAILED: ${what}`);
}
const same = (a: number[], b: number[]): boolean => a.length === b.length && a.every((v, i) => v === b[i]);
let t = new AVLTree();
for (const k of [10, 20, 30, 40, 50, 25]) {
t.insert(k);
t.check();
}
expect(same(t.inorder(), [10, 20, 25, 30, 40, 50]), "inorder");
expect(t.root!.key === 30 && t.height() === 3, "shape");
t.insert(30);
expect(t.size === 6 && t.contains(25) && !t.contains(35), "contains");
t.remove(35);
expect(t.size === 6, "remove absent");
t = new AVLTree();
for (let k = 1; k < 1024; k++) t.insert(k);
t.check();
expect(t.height() === 10, "sorted-input height");
for (let k = 2; k < 1024; k += 2) t.remove(k);
t.check();
expect(t.size === 512 && t.height() === 10 && !t.contains(512) && t.contains(511), "after removals");
let x = 42; // MINSTD generator, identical in all four languages (x * 48271 < 2^53, exact in a double)
const next = (): number => (x = (x * 48271) % 2147483647);
t = new AVLTree();
const ref: boolean[] = new Array(500).fill(false);
for (let i = 0; i < 2000; i++) {
const k = next() % 500;
const op = next() % 3;
if (op === 0) {
t.remove(k);
ref[k] = false;
} else {
t.insert(k);
ref[k] = true;
}
t.check();
}
const want: number[] = [];
for (let i = 0; i < 500; i++) if (ref[i]) want.push(i);
expect(same(t.inorder(), want), "random ops inorder");
expect(t.size === 344 && t.height() === 10, "random ops size/height");
expect(t.height() < 1.4405 * Math.log2(t.size + 2) - 0.3277, "height bound");
console.log("AVL OK");
Design notes that apply to all four:
- Recursive insert/delete returning the new subtree root: each call rebalances its own node on the way back up, so no parent pointers are needed, and recursion depth is at most 1.44 log₂ n.
- Storing the height costs a few bytes per node and keeps the code obvious; production AVL trees often store only the balance factor −1/0/+1 in spare pointer bits.
- Deletion copies the successor's key. Fine for a set of integers; if nodes are referenced from outside (iterators, intrusive containers), relink the successor node instead.
checkafter every operation on a randomized workload catches every balanced-tree bug (stale height, wrong case, lost subtree). See Testing & Debugging Algorithms.
Real-world uses
Language standard libraries. java.util.TreeMap and TreeSet are red-black trees; the Javadoc says so in its first sentence ("A Red-Black tree based NavigableMap implementation") and credits the algorithms to CLRS. Java's HashMap also turns a bucket into a red-black tree (TreeNode) once it holds 8 or more entries and the table has at least 64 buckets, so a flood of colliding keys degrades lookups to rather than . In C++, std::map, std::set, std::multimap and std::multiset are red-black trees in all three major implementations: libstdc++'s _Rb_tree in bits/stl_tree.h, libc++'s __tree, and Microsoft's STL. .NET's SortedSet<T> is a red-black tree. Python's standard library has no balanced tree; sortedcontainers uses a list of sorted lists instead. Rust's BTreeMap is an in-memory B-tree (up to 11 keys per node), for the cache reasons in the Complexity section.
The Linux kernel. lib/rbtree.c with include/linux/rbtree.h provides an intrusive red-black tree: you embed a struct rb_node in your own struct and write the search loop yourself, so there is no comparison callback and no allocation inside the tree. Users include:
epoll: each epoll instance keeps the file descriptors it monitors in a red-black tree (struct rb_root_cached rbrinfs/eventpoll.c), givingepoll_ctladd/modify/delete. The ready list is a separate linked list, which is whyepoll_waitis rather than .- The CPU scheduler: CFS (Linux 2.6.23, 2007) kept runnable tasks in a red-black tree ordered by virtual runtime and ran the cached leftmost node; its successor EEVDF (6.6, 2023) still uses an augmented red-black tree. See CPU Scheduling.
- High-resolution timers, and until Linux 6.1 the per-process tree of virtual memory areas (now a maple tree, a B-tree variant). See Virtual Memory.
Other systems. nginx keeps its timers in a red-black tree (ngx_rbtree). AVL trees appear too: OpenZFS has a general-purpose AVL library used throughout the file system, and the Windows kernel runtime library exposes AVL-based generic tables (RtlInsertElementGenericTableAvl).
Databases: why B-trees instead. A database index lives in fixed-size pages on disk or SSD: 16 KB in MySQL's InnoDB, 8 KB in PostgreSQL, 4 KB by default in SQLite. Reading a page costs on the order of 100 microseconds from an SSD, versus nanoseconds for comparing two keys in memory, so the cost model becomes "pages touched", and a binary tree wastes a page read on every comparison. The fix is to make each node a page holding as many keys as fit: the fanout. A worked estimate: with 8-byte integer keys plus child pointers and record overhead, an internal 16 KB page holds on the order of 1,000 entries; leaf pages holding rows of about 150 bytes hold about 100 rows. Height (levels, including the leaves) then grows like this:
# B-tree height for a clustered index: internal fanout f, rows per leaf page L.
def levels_needed(rows: int, f: int = 1000, leaf_rows: int = 100) -> int:
levels, capacity = 1, leaf_rows
while capacity < rows:
capacity *= f
levels += 1
return levels
def binary_height(rows: int) -> int: # perfectly balanced binary tree: ceil(log2(n + 1))
return rows.bit_length()
assert [levels_needed(n) for n in (10**5, 10**6, 10**7, 10**8, 10**9)] == [2, 3, 3, 3, 4]
assert [binary_height(n) for n in (10**6, 10**9)] == [20, 30]
assert binary_height(7) == 3 and binary_height(8) == 4
print("B-tree heights OK")
Three levels hold up to rows; four hold . A ten-million-row table has a primary-key index of height 3, and because the root and second level (about a thousand pages, some 16 MB) stay in the buffer pool, a point lookup costs about one page read. A perfectly balanced binary tree over the same keys would be 24 levels deep, nearly every level a separate random read. These are order-of-magnitude figures, not measurements of a particular engine: real fanout depends on key size, record headers, fill factor and prefix compression.
Databases use the B+ tree variant: values live only in the leaves, internal nodes hold only separator keys (more fit per page), and leaves are linked so a range scan walks them sequentially. See Indexing Deep Dive for how indexes are used and chosen, Storage Engines for B-trees versus LSM trees, and How Databases Work for the page-and-buffer-pool picture. Build one yourself in Build a Key-Value Store.
Pitfalls & edge cases
- Updating heights in the wrong order during a rotation. After a right rotation at
y,yis the child ofx, soy's height must be recomputed beforex's. Reversing the two lines computesx's height fromy's stale value. The invariant checker catches this on the first double rotation. - Choosing the double rotation when the child's balance is 0. After an insertion the child of an unbalanced node always leans one way. After a deletion it can be perfectly balanced, and then a single rotation is correct; a double rotation leaves the tree unbalanced. Write the test as
balance(child) < 0(for the left side), not<= 0. - Stopping the walk too early on delete. Insertion can stop after one rebalance; deletion cannot. Recursive code handles this automatically; iterative parent-pointer code often does not.
- Forgetting augmented fields. Subtree sizes or interval maxima must be recomputed in every rotation (bottom node first) and along the whole update path.
- Duplicates. Decide up front: reject (set) or keep a
countper node (multiset, tree stays strictly ordered). Allowing equal keys on one side complicates search and deletion. - Comparator inconsistency. A comparator that is not a strict weak ordering (NaN keys, or comparing
ints by subtraction, which overflows) corrupts the tree silently. Java'sTreeMapfinds keys withcompareTo, notequals, so the two must agree. - Mutating keys inside the tree. Changing a compared field after insertion leaves the node in the wrong place. Remove, mutate, reinsert.
- Red-black: colouring the new node black. It breaks rule 4 on every insert. New nodes are red.
- Red-black: treating
nilas "no colour". The fix-up reads the uncle's colour, and the uncle is oftennil. Use a black sentinel (CLRS) or anisRed(n)that returns false for null.
Variations
Left-leaning red-black tree (Sedgewick 2008). The shortest balanced BST to write. Insertion only, with an invariant checker that verifies the LLRB rules (no right-leaning red links, no two reds in a row, equal black counts) and the 2 log₂ n height bound:
import math
RED, BLACK = True, False
class LNode:
__slots__ = ("key", "left", "right", "color")
def __init__(self, key: int) -> None:
self.key, self.left, self.right, self.color = key, None, None, RED
def is_red(n: LNode | None) -> bool:
return n is not None and n.color == RED
def rotate_left(h: LNode) -> LNode: # a right-leaning red link becomes left-leaning
x = h.right
h.right, x.left = x.left, h
x.color, h.color = h.color, RED
return x
def rotate_right(h: LNode) -> LNode: # two left reds in a row: lift the middle one
x = h.left
h.left, x.right = x.right, h
x.color, h.color = h.color, RED
return x
def flip_colors(h: LNode) -> None: # split a temporary 4-node, pass the middle key up
h.color = RED
h.left.color = h.right.color = BLACK
def insert(h: LNode | None, key: int) -> LNode:
if h is None:
return LNode(key)
if key < h.key:
h.left = insert(h.left, key)
elif key > h.key:
h.right = insert(h.right, key)
if is_red(h.right) and not is_red(h.left):
h = rotate_left(h)
if is_red(h.left) and is_red(h.left.left):
h = rotate_right(h)
if is_red(h.left) and is_red(h.right):
flip_colors(h)
return h
def put(root: LNode | None, key: int) -> LNode:
root = insert(root, key)
root.color = BLACK
return root
def check(n: LNode | None) -> int:
"""Return the black count of every path below n; raise if an LLRB rule is broken."""
if n is None:
return 1
if is_red(n.right):
raise AssertionError("right-leaning red link")
if is_red(n) and is_red(n.left):
raise AssertionError("two reds in a row")
bl, br = check(n.left), check(n.right)
if bl != br:
raise AssertionError("unequal black height")
return bl + (0 if is_red(n) else 1)
def height(n: LNode | None) -> int:
return 0 if n is None else 1 + max(height(n.left), height(n.right))
def keys(n: LNode | None) -> list[int]:
return [] if n is None else keys(n.left) + [n.key] + keys(n.right)
root = None
for k in range(1, 1001): # sorted input again
root = put(root, k)
check(root)
assert keys(root) == list(range(1, 1001))
assert height(root) <= 2 * math.log2(1000 + 1)
print("LLRB OK, height", height(root))
B-tree insertion with proactive splitting (CLRS §18.2). Minimum degree t; a node is full at 2t − 1 keys. The root is split before descending if it is full, and every full child is split before the descent enters it, so a split never has to propagate upward:
from bisect import bisect_left, insort
class BNode:
def __init__(self, leaf: bool) -> None:
self.keys: list[int] = []
self.children: list["BNode"] = []
self.leaf = leaf
class BTree:
def __init__(self, t: int) -> None:
self.t = t
self.root = BNode(leaf=True)
def search(self, key: int) -> bool:
n = self.root
while True:
i = bisect_left(n.keys, key)
if i < len(n.keys) and n.keys[i] == key:
return True
if n.leaf:
return False
n = n.children[i]
def _split_child(self, parent: BNode, i: int) -> None:
t, full = self.t, parent.children[i]
right = BNode(full.leaf)
median = full.keys[t - 1]
right.keys, full.keys = full.keys[t:], full.keys[: t - 1]
if not full.leaf:
right.children, full.children = full.children[t:], full.children[:t]
parent.keys.insert(i, median)
parent.children.insert(i + 1, right)
def insert(self, key: int) -> None:
if self.search(key):
return
if len(self.root.keys) == 2 * self.t - 1: # grow at the root
new_root = BNode(leaf=False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
n = self.root
while not n.leaf:
i = bisect_left(n.keys, key)
if len(n.children[i].keys) == 2 * self.t - 1:
self._split_child(n, i)
if key > n.keys[i]:
i += 1
n = n.children[i]
insort(n.keys, key)
def check(self) -> tuple[int, int]:
"""Return (height, key count); raise if order, fill or leaf-depth rules break."""
depths: set[int] = set()
def go(n: BNode, lo: float, hi: float, d: int, is_root: bool) -> int:
if n.keys != sorted(n.keys) or any(not lo < k < hi for k in n.keys):
raise AssertionError("order")
if len(n.keys) > 2 * self.t - 1 or (not is_root and len(n.keys) < self.t - 1):
raise AssertionError("fill")
if n.leaf:
depths.add(d)
return len(n.keys)
if len(n.children) != len(n.keys) + 1:
raise AssertionError("child count")
bounds = [lo] + n.keys + [hi]
return len(n.keys) + sum(go(c, bounds[j], bounds[j + 1], d + 1, False)
for j, c in enumerate(n.children))
count = go(self.root, float("-inf"), float("inf"), 1, True)
if len(depths) != 1:
raise AssertionError("leaves at different depths")
return depths.pop(), count
bt = BTree(t=2) # a 2-3-4 tree: the split diagram above
bt.root = BNode(leaf=False)
bt.root.keys = [10, 40]
for ks in ([5], [20, 30, 35], [50]):
leaf = BNode(leaf=True)
leaf.keys = ks
bt.root.children.append(leaf)
bt.check()
bt.insert(25) # full child [20, 30, 35] splits, 30 moves up
assert bt.root.keys == [10, 30, 40]
assert [c.keys for c in bt.root.children] == [[5], [20, 25], [35], [50]]
assert bt.check() == (2, 8)
big = BTree(t=50) # up to 99 keys per node
for k in range(100_000):
big.insert((k * 7919) % 100_003)
h, count = big.check()
assert count == 100_000 and h == 3 # 100,000 keys, three levels
assert all(big.search((k * 7919) % 100_003) for k in range(0, 100_000, 997))
print("B-tree OK, height", h)
Weight-balanced trees (Nievergelt & Reingold, 1972) bound the ratio of subtree sizes; sizes also serve rank queries and fast set union, which is why Haskell's Data.Map uses them. AA trees (Andersson, 1993) allow only right children to be red, giving two operations (skew, split). WAVL trees (Haeupler, Sen & Tarjan, 2015) are exactly AVL trees under insertions only and relax under deletions, keeping AVL-like height with amortized rotations. Scapegoat trees (Galperin & Rivest, 1993) store no balance data and rebuild a subtree when a node gets too deep.
Augmented trees. Add a field per node that can be recomputed from the node and its two children and every operation stays (CLRS Theorem 14.1). Subtree size gives an order-statistic tree (k-th smallest, rank); the maximum endpoint in the subtree gives an interval tree, covered with other geometric structures in Spatial Trees. For range aggregates over a fixed index range, a segment tree or Fenwick tree is simpler.
Randomized and self-adjusting alternatives. Treaps, splay trees and skip lists reach expected or amortized without strict invariants; that is the next lesson, Treaps, Splay Trees & Skip Lists.
B-tree relatives. B+ trees (values only in linked leaves), B* trees (split two full nodes into three to keep nodes at least two-thirds full), and LSM trees, which give up in-place updates altogether for write throughput; compare them in Storage Engines.
Practice ladder
Problems described in my own words; Python solutions run with this page's checks.
1. Balanced Binary Tree (LeetCode 110) — Easy. Decide whether every node's subtrees differ in height by at most one, which is exactly the AVL condition. Teaches computing height and balance in one post-order pass.
Hint
Return the height from the recursion, or a sentinel −1 meaning "already unbalanced below". That turns an "compute height at every node" solution into .
Solution
from dataclasses import dataclass
@dataclass
class TreeNode:
val: int
left: "TreeNode | None" = None
right: "TreeNode | None" = None
def is_balanced(root: TreeNode | None) -> bool:
def height(n: TreeNode | None) -> int: # -1 means "unbalanced somewhere below"
if n is None:
return 0
lh = height(n.left)
if lh < 0:
return -1
rh = height(n.right)
if rh < 0 or abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return height(root) >= 0
balanced = TreeNode(30, TreeNode(20, TreeNode(10), TreeNode(25)), TreeNode(40, None, TreeNode(50)))
chain = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
roots_ok = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))), TreeNode(5, None, TreeNode(6, None, TreeNode(7))))
assert is_balanced(balanced) and is_balanced(None)
assert not is_balanced(chain)
assert not is_balanced(roots_ok) # root is level, but node 2 and node 5 are not
Time , space . The third test is the trap: checking only the root's subtrees would say yes.
2. Convert Sorted Array to Binary Search Tree (LeetCode 108) — Easy. Build a height-balanced BST from sorted keys. Teaches the build that beats AVL insertions.
Hint
The middle element is the root; recurse on the halves. Pass indices, not slices, to stay .
Solution
from dataclasses import dataclass
@dataclass
class TreeNode:
val: int
left: "TreeNode | None" = None
right: "TreeNode | None" = None
def sorted_array_to_bst(nums: list[int]) -> TreeNode | None:
def build(lo: int, hi: int) -> TreeNode | None: # half-open [lo, hi)
if lo >= hi:
return None
mid = (lo + hi) // 2
return TreeNode(nums[mid], build(lo, mid), build(mid + 1, hi))
return build(0, len(nums))
def height(n: TreeNode | None) -> int:
return 0 if n is None else 1 + max(height(n.left), height(n.right))
def inorder(n: TreeNode | None) -> list[int]:
return [] if n is None else inorder(n.left) + [n.val] + inorder(n.right)
for size in range(0, 70):
keys = list(range(size))
root = sorted_array_to_bst(keys)
assert inorder(root) == keys
assert height(root) == size.bit_length() # ceil(log2(size + 1)): perfectly balanced
Time , space recursion. The result is not just AVL-balanced but of minimum possible height.
3. Convert Sorted List to Binary Search Tree (LeetCode 109) — Medium. Same, from a linked list. Teaches the inorder-simulation build: without random access.
Hint
Build by size: the left subtree consumes the first list nodes, the next node is the root.
4. Balance a Binary Search Tree (LeetCode 1382) — Medium. Given an arbitrarily skewed BST, return a balanced one with the same keys. Teaches that "rebalance" can be done offline in : flatten, then rebuild.
Hint
Inorder traversal gives the sorted keys; problem 2 does the rest. Use an iterative traversal: the input can be a chain thousands deep.
Solution
from dataclasses import dataclass
@dataclass
class TreeNode:
val: int
left: "TreeNode | None" = None
right: "TreeNode | None" = None
def balance_bst(root: TreeNode | None) -> TreeNode | None:
nodes: list[TreeNode] = []
stack: list[TreeNode] = []
n = root
while stack or n: # iterative inorder: safe on a long chain
while n:
stack.append(n)
n = n.left
n = stack.pop()
nodes.append(n)
n = n.right
def build(lo: int, hi: int) -> TreeNode | None: # reuse the existing nodes, [lo, hi)
if lo >= hi:
return None
mid = (lo + hi) // 2
node = nodes[mid]
node.left, node.right = build(lo, mid), build(mid + 1, hi)
return node
return build(0, len(nodes))
def height(n: TreeNode | None) -> int:
if n is None:
return 0
best, stack = 0, [(n, 1)]
while stack:
node, d = stack.pop()
best = max(best, d)
stack.extend((c, d + 1) for c in (node.left, node.right) if c)
return best
chain = None
for v in range(5000, 0, -1): # right-leaning chain 1 -> 2 -> ... -> 5000
chain = TreeNode(v, None, chain)
assert height(chain) == 5000
b = balance_bst(chain)
assert height(b) == 13 # ceil(log2(5001))
Time , extra space for the node list. An in-place -space alternative exists: the Day–Stout–Warren algorithm, which straightens the tree into a "vine" by rotations and then rebalances it by more rotations.
5. My Calendar I (LeetCode 729) — Medium. Accept a half-open booking only if it overlaps no accepted booking. Teaches the floor/ceiling pattern on an ordered map, which in Java is TreeMap.floorKey / ceilingKey.
Hint
Keyed by start time, only two existing bookings can conflict with a new [s, e): the one with the largest start ≤ s, and the one with the smallest start ≥ s.
Solution
class _Node:
__slots__ = ("key", "end", "left", "right", "h")
def __init__(self, key: int, end: int) -> None:
self.key, self.end, self.left, self.right, self.h = key, end, None, None, 1
def _h(n: "_Node | None") -> int:
return n.h if n else 0
def _up(n: _Node) -> None:
n.h = 1 + max(_h(n.left), _h(n.right))
def _rot_r(y: _Node) -> _Node:
x = y.left
y.left, x.right = x.right, y
_up(y); _up(x)
return x
def _rot_l(x: _Node) -> _Node:
y = x.right
x.right, y.left = y.left, x
_up(x); _up(y)
return y
def _insert(n: "_Node | None", key: int, end: int) -> _Node:
if n is None:
return _Node(key, end)
if key < n.key:
n.left = _insert(n.left, key, end)
else:
n.right = _insert(n.right, key, end)
_up(n)
b = _h(n.left) - _h(n.right)
if b > 1:
if _h(n.left.left) < _h(n.left.right):
n.left = _rot_l(n.left)
return _rot_r(n)
if b < -1:
if _h(n.right.right) < _h(n.right.left):
n.right = _rot_r(n.right)
return _rot_l(n)
return n
class MyCalendar:
"""AVL tree keyed by booking start, storing the end: floor and ceiling in O(log n)."""
def __init__(self) -> None:
self.root: _Node | None = None
def book(self, start: int, end: int) -> bool:
floor = ceil = None
n = self.root
while n:
if n.key <= start:
floor, n = n, n.right
else:
ceil, n = n, n.left
if floor and floor.end > start: # previous booking runs into ours
return False
if ceil and ceil.key < end: # next booking starts before we end
return False
self.root = _insert(self.root, start, end)
return True
cal = MyCalendar()
answers = [cal.book(s, e) for s, e in [(10, 20), (15, 25), (20, 30), (5, 10), (5, 11), (30, 31), (29, 30)]]
assert answers == [True, False, True, True, False, True, False]
import random
rng = random.Random(7)
cal, accepted = MyCalendar(), []
for _ in range(2000): # compare with an O(n) brute force
s = rng.randrange(0, 5000); e = s + rng.randrange(1, 40)
want = all(e <= a or b <= s for a, b in accepted)
assert cal.book(s, e) == want
if want:
accepted.append((s, e))
Time per booking, space . In Java the whole tree is TreeMap<Integer, Integer> with floorEntry and ceilingEntry.
6. Contains Duplicate III (LeetCode 220) — Hard. Find two indices at most k apart whose values are within t. Teaches the sliding-window ordered set: keep the last k values in a balanced BST and ask for the ceiling of x − t.
Hint
Only the window's ceiling of x − t matters: is it ≤ x + t? Buckets of width t + 1 give .
7. Count of Smaller Numbers After Self (LeetCode 315) — Hard. For each position, count the strictly smaller values to its right. Teaches the order-statistic tree: a balanced BST whose nodes store subtree sizes.
Hint
Scan right to left. Before inserting x, ask the tree how many stored keys are < x: walk down; whenever you go right past a node, add its left subtree's size plus its own count. Keep sizes correct through rotations.
Solution
import random
class ONode:
__slots__ = ("key", "cnt", "left", "right", "h", "size")
def __init__(self, key: int) -> None:
self.key, self.cnt, self.left, self.right, self.h, self.size = key, 1, None, None, 1, 1
def _h(n: "ONode | None") -> int:
return n.h if n else 0
def _s(n: "ONode | None") -> int:
return n.size if n else 0
def _up(n: ONode) -> None:
n.h = 1 + max(_h(n.left), _h(n.right))
n.size = n.cnt + _s(n.left) + _s(n.right) # the augmented field
def _rot_r(y: ONode) -> ONode:
x = y.left
y.left, x.right = x.right, y
_up(y); _up(x)
return x
def _rot_l(x: ONode) -> ONode:
y = x.right
x.right, y.left = y.left, x
_up(x); _up(y)
return y
def _insert(n: "ONode | None", key: int) -> ONode:
if n is None:
return ONode(key)
if key < n.key:
n.left = _insert(n.left, key)
elif key > n.key:
n.right = _insert(n.right, key)
else:
n.cnt += 1 # multiset: count duplicates in place
_up(n)
return n
_up(n)
b = _h(n.left) - _h(n.right)
if b > 1:
if _h(n.left.left) < _h(n.left.right):
n.left = _rot_l(n.left)
return _rot_r(n)
if b < -1:
if _h(n.right.right) < _h(n.right.left):
n.right = _rot_r(n.right)
return _rot_l(n)
return n
def _count_less(n: "ONode | None", key: int) -> int:
total = 0
while n:
if key <= n.key:
n = n.left
else:
total += _s(n.left) + n.cnt
n = n.right
return total
def count_smaller(nums: list[int]) -> list[int]:
root, out = None, [0] * len(nums)
for i in range(len(nums) - 1, -1, -1):
out[i] = _count_less(root, nums[i])
root = _insert(root, nums[i])
return out
assert count_smaller([7, 3, 9, 3, 1]) == [3, 1, 2, 1, 0]
assert count_smaller([]) == [] and count_smaller([4, 4, 4]) == [0, 0, 0]
rng = random.Random(1)
for _ in range(200):
a = [rng.randrange(-20, 20) for _ in range(rng.randrange(0, 40))]
assert count_smaller(a) == [sum(a[j] < a[i] for j in range(i + 1, len(a))) for i in range(len(a))]
sorted_input = list(range(100_000)) # sorted input: a plain BST would go quadratic
assert count_smaller(sorted_input)[-1] == 0 and count_smaller(sorted_input)[0] == 0
Time , space . The last test inserts 100,000 increasing values from the right, a decreasing sequence, which would build a 100,000-deep chain in an unbalanced BST. A Fenwick tree over compressed values or merge sort with inversion counting also solve it; see Merge Sort.
8. Sliding Window Median (LeetCode 480) — Hard. Median of every window of size k. Teaches the ordered multiset with arbitrary deletion.
Hint
The median is one or two k-th queries on an order-statistic tree; two heaps need lazy deletion.
9. Data Stream as Disjoint Intervals (LeetCode 352) — Hard. Maintain a stream of integers as merged intervals. Teaches neighbour lookups and merging in an ordered map.
Hint
Key intervals by start; a new value can only touch its floor and ceiling intervals.
10. The Skyline Problem (LeetCode 218) — Hard. Outline of overlapping rectangles. Teaches a sweep line over an ordered multiset of active heights.
Hint
At each x event update the multiset and emit a point when its maximum changes.
11. Range Module (LeetCode 715) — Hard. Add, remove and query half-open ranges. Teaches interval splitting in an ordered map.
Hint
Keep disjoint intervals keyed by start; find overlaps with a floor lookup and iterate forward.
12. Concert Tickets (CSES 1091) — Medium. Each customer takes the priciest remaining ticket within budget. Teaches floor plus delete on a multiset.
Hint
Prices with counts: find the floor, decrement, remove at zero.
13. Traffic Lights (CSES 1163) — Hard. After each light is added, report the longest unlit stretch. Teaches two ordered structures together: positions and a multiset of gaps.
Hint
A light at p between a and b replaces gap b − a with p − a and b − p.
14. Order statistic set (SPOJ ORDERSET) — Hard. Insert, delete, k-th smallest and count-less-than. Teaches writing a complete augmented balanced BST under time pressure.
Hint
Add a size field to this page's AVL tree, maintain it in update(), and walk down comparing k with the left subtree's size.
Common mistakes & interview follow-ups
"AVL or red-black?" AVL for lookup-heavy workloads (1.44 log₂ n against 2 log₂ n worst-case height); red-black for update-heavy, augmented or intrusive trees (bounded rotations, amortized restructuring). The height difference is a few levels, so measure; cache behaviour often dominates.
"Why do databases use B-trees rather than red-black trees?" Because the cost is page reads, not comparisons. A node the size of a page with fanout around 1,000 makes the tree three or four levels deep for billions of keys, with the top levels cached; a binary tree would be 30-plus levels with nearly every level a separate I/O. B+ trees additionally make range scans sequential.
"Can you get k-th smallest in O(log n)?" Yes: augment each node with its subtree size, maintain it in rotations, and walk down comparing k to the left subtree's size. Same trick gives rank.
"How many rotations does an insert do? A delete?" AVL insert: at most one single or double rotation. AVL delete: up to . Red-black insert: at most 2. Red-black delete: at most 3.
"Why is the new node red in a red-black tree?" A red node does not change any path's black count, so rule 4 is preserved for free and only the local "no red-red" rule can break, which is fixed near the insertion point. A black node would unbalance every path through it.
"What if many threads use the tree?" Fine-grained locking is hard because a rebalance touches nodes above the insertion point. Concurrent ordered maps tend to be skip lists (Java's ConcurrentSkipListMap) or optimistic B-tree variants, whose updates are more local; see the next lesson and Lock-Free Programming.
"The data is static, or arrives as one sorted bulk load." Then skip the balancing machinery: binary-search a sorted array, or build a perfectly balanced tree from it in rather than by repeated insertion. Databases bulk-load B-trees bottom-up for the same reason.
Quick quiz
- What is the minimum number of nodes in an AVL tree of height 6 (node-counting convention), and what does the minimal tree look like?
Answer
, which is . It is a Fibonacci tree: a root whose left subtree is a minimal tree of height 5 and right subtree a minimal tree of height 4 (or the mirror), recursively, so every internal node has balance factor ±1.
- You insert into an AVL tree and the lowest unbalanced node
zhas balance +2 while its left child has balance −1. Which rotations do you perform, and why does a single right rotation atzfail?
Answer
Case LR: left-rotate at the left child, then right-rotate at z. A single right rotation at z would move the left child's tall right subtree under z on the right side, leaving the new root with balance −2: the zig-zag just flips sides.
- Prove in two sentences that a red-black tree with black-height at the root has at least internal nodes.
Answer
Induct on height: each child of a node with black-height has black-height at least , so by induction each child subtree has at least internal nodes. Adding the node itself gives .
- In the red-black trace, inserting 15 into
20B(10R,30R)increased the black-height. Which fix-up case did it, and what is the corresponding 2-3-4 tree operation?
Answer
Case 1 (red uncle 30): recolour 10 and 30 black and 20 red, then the root 20 is recoloured black. In 2-3-4 terms the root was a full 4-node 10 | 20 | 30; inserting 15 splits it, 20 moves up into a new root, and the tree grows by one level.
- A table has 50 million rows and its primary-key B+ tree has internal fanout about 1,000 and about 100 rows per leaf page. How many levels does the index have, and how many page reads does a cold point lookup cost versus a warm one?
Answer
Two levels hold rows and three hold , so 50 million rows need 3 levels. A completely cold lookup reads 3 pages; with the root and the second level resident in the buffer pool (they total about a thousand pages), it reads 1.
Further reading / sources
- G. M. Adelson-Velsky & E. M. Landis, "An algorithm for the organization of information", Doklady Akademii Nauk SSSR 146 (1962), 263–266 — the original AVL paper.
- D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.2.3 "Balanced Trees" — the Fibonacci-tree analysis and the bound .
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 3rd/4th ed., Chapter 13 "Red-Black Trees" (Lemma 13.1 is the height bound; §13.3–13.4 insertion and deletion), Chapter 14/17 "Augmenting Data Structures", Chapter 18 "B-Trees".
- R. Sedgewick & K. Wayne, Algorithms, 4th ed., §3.3 "Balanced Search Trees" — 2-3 trees and left-leaning red-black trees. R. Sedgewick, "Left-leaning Red-Black Trees" (2008).
- L. J. Guibas & R. Sedgewick, "A dichromatic framework for balanced trees", FOCS 1978. R. Bayer, "Symmetric binary B-Trees: Data structure and maintenance algorithms", Acta Informatica 1 (1972).
- R. Bayer & E. McCreight, "Organization and maintenance of large ordered indexes", Acta Informatica 1 (1972) — the B-tree. D. Comer, "The Ubiquitous B-Tree", ACM Computing Surveys 11(2), 1979.
- B. Haeupler, S. Sen & R. E. Tarjan, "Rank-balanced trees", ACM Transactions on Algorithms 11(4), 2015 — WAVL trees.
- Java SE 21
java.util.TreeMapJavadoc; libstdc++bits/stl_tree.h; LinuxDocumentation/core-api/rbtree.rstandfs/eventpoll.c. - Wikipedia: AVL tree, Red–black tree.
Prev: Binary Search Trees · Next: Treaps, Splay Trees & Skip Lists
Related: Module 3 — Trees · Trees (Overview) · Binary Trees & Traversals · Heaps & Priority Queues · Segment Trees in Depth · Advanced Data Structures · Indexing Deep Dive · Storage Engines · DSA: Zero to Mastery