On this page

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 streamOrder-statistic tree: a balanced BST augmented with subtree sizes
"next greater key", "largest key ≤ x", floor / ceiling, with inserts and deletes interleavedOrdered 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:

  1. Strong enough that height is for a small constant .
  2. 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:

  1. The root is black.
  2. Every nil leaf (the empty subtree positions) is black.
  3. A red node has no red child (no two reds in a row).
  4. Every path from a given node down to a nil leaf 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:

CaseShapebf(z)bf(child)Fix
LLnew key in left subtree of left child+2≥ 0right-rotate at z
RRnew key in right subtree of right child−2≤ 0left-rotate at z
LRnew key in right subtree of left child+2< 0left-rotate at child, then right-rotate at z
RLnew key in left subtree of right child−2> 0right-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.

InsertPath walkedFirst unbalanced node (bf)CaseRotation(s)Tree afterHeight
10————101
2010———10(.,20)2
3010 → 2010 (−2)RRleft-rotate at 1020(10,30)2
4020 → 30———20(10,30(.,40))3
5020 → 30 → 4030 (−2)RRleft-rotate at 3020(10,40(30,50))3
2520 → 40 → 3020 (−2)RLright-rotate at 40, then left-rotate at 2030(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.

A single rotation fixes a straight-line imbalance; a zig-zag needs a double rotation that lifts the middle key — either way one fix restores the subtree's old height.

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):

CaseConditionActionEffect
1. Red uncleu is redrecolour parent and u black, g red; set z = g and continuepushes the red-red problem two levels up; no rotation
2. Black uncle, triangleu black, z is a right childleft-rotate at the parent, set z to the old parentconverts to case 3
3. Black uncle, lineu black, z is a left childrecolour parent black, g red; right-rotate at gfixes 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.

InsertFix-up appliedTree afterbh
10root recoloured black10B1
20none (parent black)10B(.,20R)1
30case 3 (mirrored, line): recolour 20 black, 10 red; left-rotate at 1020B(10R,30R)1
15case 1: uncle 30 red; recolour 10, 30 black and 20 red; root recoloured black20B(10B(.,15R),30B)2
25none (parent 30 black)20B(10B(.,15R),30B(25R,.))2
5none (parent 10 black)20B(10B(5R,15R),30B(25R,.))2
1case 1: uncle 15 red; recolour 5, 15 black and 10 red20B(10R(5B(1R,.),15B),30B(25R,.))2
3case 2: triangle, left-rotate at 1; case 3: recolour 3 black, 5 red; right-rotate at 520B(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 rule2-3-4 meaning
Rule 3: no red-redA 2-3-4 node holds at most three keys (one black plus at most two reds)
Rule 4: equal black-heightEvery 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 rotationTurning a 3-node into a 4-node by absorbing the new key, re-drawn so the middle key is black
Root recoloured black, bh + 1The 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:

  1. If the right child is red and the left is not, rotate left (fix a right-leaning red).
  2. If the left child and its left child are both red, rotate right (fix two reds in a row).
  3. 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.

ApproachSearchInsert / deletek-th / rankWorst-case guaranteeNotes
Sorted array / yesBest for static data
Plain BST with sizesno: up to Expected on random input
Scapegoat tree amortized with sizesheight yes, updates amortizedNo per-node balance field
AVL tree, with sizesyesShallowest; ≤ 2 rotations per insert, per delete
Red-black tree, with sizesyes≤ 2 rotations per insert, ≤ 3 per delete
B-tree, fanout page reads page writeswith countsyesThe 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 x is its left, height ; its right has height ): after a right rotation at z, z has children of heights (x's old right) and (z's right), so height ; x has children of heights and , so height , balance 0.
  • LR (x's right child w has height , x's left has height ): w's two subtrees have heights and in some order (or both 0 if w is the new node). After the double rotation, w is on top with children x (subtrees of heights and at most ) and z (subtrees of heights at most and ); both have height , so w has 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

OperationAVLRed-blackNotes
Search, floor, ceiling, successor worst worstAVL path ≤ 1.44 log₂ n, RB ≤ 2 log₂ n
Insert; ≤ 1 single or double rotation; ≤ 2 rotationsPlus height updates or recolourings
Delete; up to rotations; ≤ 3 rotationsRB recolourings can climb to the root
Min / max, or with cached pointerssameLinux's rb_root_cached caches the leftmost node
k-th smallest, rank with subtree sizessameRotations must update sizes
Build from sorted input by building from the middleInserting one by one is
Inorder traversal
Space nodes + 1 small integer (height or balance) each nodes + 1 bit eachPlus 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.
  • check after 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 rbr in fs/eventpoll.c), giving epoll_ctl add/modify/delete. The ready list is a separate linked list, which is why epoll_wait is 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, y is the child of x, so y's height must be recomputed before x's. Reversing the two lines computes x's height from y'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 count per 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's TreeMap finds keys with compareTo, not equals, 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 nil as "no colour". The fix-up reads the uncle's colour, and the uncle is often nil. Use a black sentinel (CLRS) or an isRed(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

  1. 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.

  1. You insert into an AVL tree and the lowest unbalanced node z has balance +2 while its left child has balance −1. Which rotations do you perform, and why does a single right rotation at z fail?
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.

  1. 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 .

  1. 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.

  1. 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.TreeMap Javadoc; libstdc++ bits/stl_tree.h; Linux Documentation/core-api/rbtree.rst and fs/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