---
title: Balanced Search Trees
module: Data Structures
moduleNumber: 4
lessonNumber: 5
order: 405
summary: |
  An ordinary BST can degrade to height $\Theta(n)$; balanced search trees
  guarantee $h = O(\log n)$ by maintaining invariants and repairing them after
  every update. We meet rotations, the local restructuring primitive, then
  red-black trees, whose color invariants force logarithmic height, and finally
  B-trees, which trade tall-and-thin for short-and-wide to win on disk.
topics: [Balanced Trees]
sources:
  - book: CLRS
    ref: "Ch. 13 & 18 — Red-Black Trees, B-Trees"
  - book: Skiena
    ref: "§3.4 — Balanced Search Trees"
  - book: Erickson
    ref: "Ch. — Balanced Binary Search Trees"
practice:
  - title: 'Balanced Binary Tree'
    slug: balanced-binary-tree
    difficulty: Easy
  - title: 'Convert Sorted Array to BST'
    slug: convert-sorted-array-to-binary-search-tree
    difficulty: Easy
  - title: 'My Calendar I'
    slug: my-calendar-i
    difficulty: Medium
  - title: 'Count of Smaller Numbers After Self'
    slug: count-of-smaller-numbers-after-self
    difficulty: Hard
  - title: 'Count of Range Sum'
    slug: count-of-range-sum
    difficulty: Hard
---

The previous lesson left us with a sharp problem. A [binary search tree](/algorithms/data-structures/binary-search-trees) does
everything in $O(h)$ time, which is $\Theta(\log n)$ when the tree is
balanced and $\Theta(n)$ when it is not, and we cannot control the
order in which keys arrive. A **balanced search tree** removes the dependence on
luck. It maintains a structural **invariant** strong enough to force
$h = O(\log n)$, and after every insertion or deletion it does a small amount of
**rebalancing** to restore that invariant.[^erickson-balanced] The guarantee becomes worst-case, not
best-case: $O(\log n)$ per operation, on every input.

Different balanced trees enforce different invariants. [AVL trees](/algorithms/data-structures/avl-trees) bound the
height difference of sibling subtrees, red-black trees color the nodes, and B-trees
pack many keys per node, but they all share one mechanical primitive for
reshaping the tree without disturbing its sorted order: the **rotation**.

## Rotations: local surgery that preserves order

A **rotation** rearranges three pointers to change a tree's shape, and hence its
height, while keeping the BST property intact. A _right rotation_ at a node $y$
makes $y$'s left child $x$ the new subtree root, with $y$ becoming $x$'s right
child; a _left rotation_ is the exact inverse. The subtree that was "in the
middle" (call it $T_2$) switches parents but stays between $x$ and $y$ in key
order.

$$
% caption: Left and right rotations reshape a BST while preserving sorted order
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=5mm, inner sep=1pt},
  level distance=11mm]
  % left tree (rooted at y)
  \begin{scope}
    \node (y) {$y$}
      child {node (x) {$x$}
        child {node[tri] {$T_1$}}
        child {node[tri] {$T_2$}}
      }
      child {node[tri] {$T_3$}};
  \end{scope}
  % two labeled arrows, one per direction (label nodes override the circle style)
  \draw[->, thick] (2.0,-1.0) -- node[draw=none, above, font=\footnotesize] {righ\/t rotate at $y$} (4.2,-1.0);
  \draw[<-, thick] (2.0,-1.9) -- node[draw=none, below, font=\footnotesize] {lef\/t rotate at $x$} (4.2,-1.9);
  % right tree (rooted at x)
  \begin{scope}[xshift=6.4cm]
    \node (x2) {$x$}
      child {node[tri] {$T_1$}}
      child {node (y2) {$y$}
        child {node[tri] {$T_2$}}
        child {node[tri] {$T_3$}}
      };
  \end{scope}
\end{tikzpicture}
$$

In both trees the sorted order is $T_1 < x < T_2 < y < T_3$ — a rotation
never violates the BST property.[^clrs-rotate] What it _does_ change is height: rotating can
pull a deep subtree up a level and push a shallow one down — the mechanism a
balanced tree uses to repair itself.

```algorithm
caption: $\textsc{Left-Rotate}(T, x)$ — pivot $x$ down-left, its right child $y$ up
$y \gets right(x)$
$right(x) \gets left(y)$ // $T_2$ becomes x's right child
if $left(y) \ne \text{nil}$ then
  $parent(left(y)) \gets x$
$parent(y) \gets parent(x)$ // splice y where x was
if $parent(x) = \text{nil}$ then
  $root(T) \gets y$
else if $x = left(parent(x))$ then
  $left(parent(x)) \gets y$
else
  $right(parent(x)) \gets y$
$left(y) \gets x$ // x hangs under y
$parent(x) \gets y$
```

A rotation touches only a constant number of pointers, so it runs in $O(1)$
time. Every balanced-tree rebalancing operation is built from a handful of
rotations (plus, for red-black trees, recolorings) along a single root-to-leaf
path, hence $O(\log n)$ work to repair the tree after an update.

For a concrete instance, suppose $y = 10$ has
left child $x = 5$, and $x$'s children are $T_1$ (keys $< 5$) and $T_2$ (keys in
$(5, 10)$), while $y$'s right child is $T_3$ (keys $> 10$). A **right rotation at
$10$** promotes $5$ to the subtree root: $10$ becomes $5$'s right child, $T_2$
(the "middle" subtree) detaches from $5$ and reattaches as $10$'s _left_ child,
and $T_1$, $T_3$ stay put. Reading the keys left to right before the rotation,
$T_1 < 5 < T_2 < 10 < T_3$; after it, $T_1 < 5 < T_2 < 10 < T_3$, unchanged.
Only three pointers moved ($5$'s right, $10$'s left, and the parent link that
now points at $5$), yet the node that was at depth $2$ ($5$) is now at depth $1$
and $10$ has dropped one level, the height change a balanced tree exploits.

## Red-black trees: balance by color

A **red-black tree** is a BST in which every node carries one extra bit, its
**color** — red or black.[^clrs-rb] Five invariants on those colors squeeze the tree into
logarithmic height:

> **Invariant (red-black).** A red-black tree is a BST satisfying:
> 1. Every node is either **red** or **black**.
> 2. The **root** is black.
> 3. Every **leaf** (the `nil` sentinel) is black.
> 4. If a node is **red**, then both its children are **black** (no two reds in a
>    row).
> 5. For each node, every path from it down to a descendant leaf contains the
>    _same number of black nodes_ — its **black-height**.

Properties 4 and 5 are what force balance. Property 5 says all root-to-leaf paths have
the same number of black nodes; property 4 says reds cannot cluster, so reds can
at most _double_ a path's length by interleaving. Together they bound how
lopsided the tree can get.

The **black-height** $bh(x)$ of a node $x$ is the number of black nodes on any
path from $x$ down to a leaf, _not counting_ $x$ itself; property 5 asserts
precisely that this number is well defined. Consider a concrete tree:

$$
% caption: A red-black tree with black-heights annotated. Every root-to-nil path
%          contains exactly two black nodes (counting the black nil leaves, not the
%          starting node), so $bh = 2$ at the root even though the paths differ in
%          length: reds pad some paths but never change the black count.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6.5mm, inner sep=0, font=\small},
  red/.style={draw=red, text=red, line width=0.6pt},
  blk/.style={draw=black, text=black},
  bh/.style={draw=none, font=\scriptsize},
  level distance=11mm,
  level 1/.style={sibling distance=32mm},
  level 2/.style={sibling distance=16mm},
  level 3/.style={sibling distance=9mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[blk] (n13) {$13$}
    child {node[red] (n8) {$8$}
      child {node[blk] (n1) {$1$}}
      child {node[blk] (n11) {$11$}}
    }
    child {node[red] (n17) {$17$}
      child {node[blk] (n15) {$15$}}
      child {node[blk] (n25) {$25$}
        child {node[red] (n22) {$22$}}
        child {node[red] (n27) {$27$}}
      }
    };
  \node[bh, text=acc, anchor=west] at ($(n13.east)+(0.15,0.1)$) {$bh=2$};
  \node[bh, text=acc, anchor=east] at ($(n8.west)+(-0.15,0.1)$) {$bh=2$};
  \node[bh, text=acc, anchor=west] at ($(n25.east)+(0.15,0.1)$) {$bh=1$};
  \node[bh, text=acc, anchor=west] at ($(n27.east)+(0.15,-0.1)$) {$bh=1$};
\end{tikzpicture}
$$

Check property 5 at the root: the path $13, 8, 1, \text{nil}$ crosses two black
nodes ($1$ and nil), and so does the longer path $13, 17, 25, 22, \text{nil}$
($25$ and nil). The red nodes $8$, $17$, $22$, $27$ stretch some paths without
contributing to any black count, and property 4 guarantees they never appear
twice in a row, which is what caps the stretching at a factor of two.

### Why the height is $O(\log n)$

The argument is short and worth seeing, because it explains _why_ the color rules
take exactly this form. Let $bh(x)$ be the black-height of node $x$ (the number of
black nodes on any path from $x$ down to a leaf, not counting $x$).

> **Lemma.** The subtree rooted at $x$ contains at least $2^{bh(x)} - 1$ internal
> nodes.

> **Proof by induction on height.** If $x$ is a leaf, $bh(x) = 0$ and the subtree
> has $2^0 - 1 = 0$ internal nodes. Otherwise each child of $x$ has black-height
> $bh(x)$ or $bh(x)-1$ (it drops by one only across a black child), so by induction
> each child's subtree has at least $2^{bh(x)-1} - 1$ internal nodes, and
>
> $$
> 2\parens{2^{bh(x)-1} - 1} + 1 = 2^{bh(x)} - 1. \qquad\square
> $$

Now let $h$ be the tree's height. By property 4 at least half the nodes on any
root-to-leaf path are black, so the root's black-height is at least $h/2$.
Applying the lemma at the root with $n$ internal nodes,

$$
n \ge 2^{bh(\text{root})} - 1 \ge 2^{h/2} - 1
\quad\Longrightarrow\quad
h \le 2\log_2(n + 1) = O(\log n).
$$

So _every_ operation that walks the tree (search, insert, delete, successor)
runs in $O(\log n)$ worst-case time, provided updates preserve the invariants.
That is the job of the fix-up procedures.

### Insertion: recolor when you can, rotate when you must

$\textsc{RB-Insert}$ starts as an ordinary BST insertion: walk down to a leaf
position and attach the new node $z$ there. Then color $z$ **red**. The choice of
color is deliberate. A red $z$ adds zero to every black count, so property 5
survives untouched; the only properties at risk are property 2 (if $z$ is the
root) and property 4 (if $z$'s parent happens to be red). Coloring $z$ black
instead would add one black node to exactly the paths through $z$ and break
property 5 — a _global_ violation that is much harder to localize. So insertion
trades a possible global breakage for a possible local one, and
$\textsc{RB-Insert-Fixup}$ repairs the local one by walking up the tree.[^clrs-rb-insert]

The fix-up loop runs while $z$'s parent is red. Write $P$ for the parent, $G$
for the grandparent (which must be black, since $P$ is red and the tree was valid
before), and $y$ for the **uncle** — $G$'s other child. Assume $P$ is $G$'s left
child; the other orientation mirrors every case left-for-right. Exactly three
cases arise:

**Case 1 (red uncle): recolor and climb.** If $y$ is red, paint $P$ and $y$
black and $G$ red, with no rotation at all. Locally, "no two reds" is restored;
globally, every path through $G$ still crosses the same number of blacks,
because the black that left $G$ reappears one level down on _both_ sides.
But $G$ is now red, so if _its_ parent is also red the violation has moved two
levels up. Set $z \gets G$ and repeat.

$$
% caption: Insert-fixup Case 1 — a red uncle $y$ lets us recolor instead of rotate,
%          pushing the violation up to grandparent $z.p.p$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  red/.style={draw=red, text=red, line width=0.6pt},
  blk/.style={draw=black, text=black},
  level distance=11mm,
  level 1/.style={sibling distance=26mm},
  level 2/.style={sibling distance=13mm}]
  \definecolor{acc}{HTML}{2348F2}
  % --- before ---
  \begin{scope}
    \node[blk] (g) {$G$}
      child {node[red] (p) {$P$}
        child {node[red] (z) {$z$}}
        child {node[blk] {$d$}}
      }
      child {node[red] (y) {$y$}};
    \node[draw=none, font=\footnotesize] at (-2.5,-1.1) {parent};
    \node[draw=none, font=\footnotesize] at (2.35,-1.1) {uncle};
  \end{scope}
  \draw[->, very thick] (3.2,-1.45) -- node[draw=none, above, font=\footnotesize] {recolor} (4.5,-1.45);
  % --- after ---
  \begin{scope}[xshift=62mm]
    \node[red] (g2) {$G$}
      child {node[blk] (p2) {$P$}
        child {node[red] (z2) {$z$}}
        child {node[blk] {$d$}}
      }
      child {node[blk] (y2) {$y$}};
    \node[draw=none, font=\footnotesize, text=acc] at (0,1.0) {new violation};
    \draw[->, acc, thick] (0,0.7) -- (g2);
  \end{scope}
\end{tikzpicture}
$$

**Case 2 (black uncle, zig-zag): straighten.** If $y$ is black and $z$ is $P$'s
_right_ child, the red pair $P, z$ forms a bent path (left, then right). A left
rotation at $P$ straightens it: the old $z$ rises, the old $P$ drops to become
its left child, and both are still red. Nothing is fixed yet — this move exists
only to convert the configuration into Case 3, with $z$ renamed to the node that
is now the lower red.

**Case 3 (black uncle, zig-zig): rotate and finish.** Now $z$ is $P$'s _left_
child and the two reds lie on a straight line. Right-rotate at $G$, then swap
the colors of $P$ and $G$: the subtree's new root $P$ is black, its children $z$
and $G$ are red. Every path that used to pass through black $G$ now passes
through black $P$ instead, so all black counts are preserved, and the new
subtree root is black, so no red-red pair can exist at its top. The loop
terminates.

$$
% caption: Insert-fixup Cases 2 and 3, uncle $y$ black. A left rotation at $P$
%          straightens the zig-zag into a zig-zig; a right rotation at $G$ plus a
%          color swap then ends the fix-up with a black subtree root. Labels track
%          the code's renaming: after the first rotation, $z$ again names the lower
%          red and $P$ its parent.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6.5mm, inner sep=0, font=\small},
  red/.style={draw=red, text=red, line width=0.6pt},
  blk/.style={draw=black, text=black},
  tri/.style={draw=black, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=4mm, inner sep=1pt, font=\scriptsize},
  lbl/.style={draw=none, font=\footnotesize},
  level distance=10mm,
  level 1/.style={sibling distance=18mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=7mm}]
  \definecolor{acc}{HTML}{2348F2}
  % --- panel 1: Case 2 (zig-zag) ---
  \begin{scope}
    \node[blk] (g) {$G$}
      child {node[red] (p) {$P$}
        child {node[tri] {$a$}}
        child {node[red] (z) {$z$}
          child {node[tri] {$b$}}
          child {node[tri] {$c$}}
        }
      }
      child {node[blk] (y) {$y$}};
    \node[lbl] at (0,0.85) {Case 2: zig-zag};
  \end{scope}
  \draw[->, very thick] (1.9,-1.4) -- node[lbl, above, align=center] {rotate\\at $P$} (3.3,-1.4);
  % --- panel 2: Case 3 (zig-zig), pointers renamed as in the code ---
  \begin{scope}[xshift=50mm]
    \node[blk] (g2) {$G$}
      child {node[red] (p2) {$P$}
        child {node[red] (z2) {$z$}
          child {node[tri] {$a$}}
          child {node[tri] {$b$}}
        }
        child {node[tri] {$c$}}
      }
      child {node[blk] (y2) {$y$}};
    \node[lbl] at (0,0.85) {Case 3: zig-zig};
  \end{scope}
  \draw[->, very thick] (6.8,-1.4) -- node[lbl, above, align=center] {rotate at $G$,\\swap colors} (8.5,-1.4);
  % --- panel 3: done ---
  \begin{scope}[xshift=103mm]
    \node[blk] (p3) {$P$}
      child {node[red] (z3) {$z$}
        child {node[tri] {$a$}}
        child {node[tri] {$b$}}
      }
      child {node[red] (g3) {$G$}
        child {node[tri] {$c$}}
        child {node[blk] (y3) {$y$}}
      };
    \node[lbl] at (0,0.85) {done: root black};
  \end{scope}
\end{tikzpicture}
$$

After the loop ends, one line remains: color the root black. If the loop pushed
the red up to the root (or the very first insertion created a red root), this
restores property 2 without disturbing property 5, since adding a black at the
root adds one to _every_ path's count equally.

The cost accounting: each Case 1 iteration is $O(1)$ recoloring and lifts $z$
two levels, so there are at most $h/2 = O(\log n)$ of them; Cases 2 and 3
execute at most once each and end the loop. An insertion therefore performs
$O(\log n)$ recolorings but **at most two rotations**. Deletion has a symmetric
(if fussier) fix-up with four cases per side and at most three rotations, also
$O(\log n)$ overall; CLRS works through it in full.[^clrs-rb-delete]

### A worked trace

Insert the keys $10, 20, 30, 15, 12$ into an empty tree, in that order. Every
fix-up case appears exactly once.

1. **Insert $10$.** The tree was empty, so $10$ becomes the root; the final
   recolor-the-root step paints it black.
2. **Insert $20$.** It lands as the red right child of black $10$. No red
   parent, no violation.
3. **Insert $30$.** It lands as the red right child of red $20$: a violation.
   The uncle ($10$'s left child) is nil, hence black, and $z = 30$ lies on a
   straight line with $P = 20$ under $G = 10$ — the mirror of Case 3.
   Left-rotate at $10$ and swap colors: $20$ (black) is the new root with red
   children $10$ and $30$.
4. **Insert $15$.** It lands as the red right child of red $10$. The uncle $30$
   is _red_, so Case 1 applies. Recolor: $10$ and $30$ turn black, $20$ turns red, and
   $z$ jumps to $20$. The loop exits ($20$ has no parent) and the final line
   repaints the root black. No rotation.
5. **Insert $12$.** It descends $20 \to 10 \to 15$ and lands as the red left
   child of red $15$. The uncle (left child of $10$) is nil, hence black, and
   the reds $15, 12$ form a bent path under $10$, the mirror of Case 2.
   Right-rotate at $15$: now $12$ is the lower parent with $15$ below it,
   a straight line. The mirror of Case 3 finishes: left-rotate at $10$, swap
   colors, and the subtree root $12$ is black with red children $10$ and $15$.

$$
% caption: The trace at four checkpoints. Insert $30$ triggers a rotation (Case 3),
%          insert $15$ a pure recolor (Case 1), insert $12$ the double rotation
%          (Case 2 then Case 3). Black-heights stay equal on every path throughout.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  red/.style={draw=red, text=red, line width=0.6pt},
  blk/.style={draw=black, text=black},
  lbl/.style={draw=none, font=\footnotesize},
  level distance=9mm,
  level 1/.style={sibling distance=13mm},
  level 2/.style={sibling distance=8mm}]
  \definecolor{acc}{HTML}{2348F2}
  % --- panel 1: after inserting 30, before fixup ---
  \begin{scope}
    \node[blk] (a1) {$10$}
      child[missing]
      child {node[red] (a2) {$20$}
        child[missing]
        child {node[red] (a3) {$30$}}
      };
    \node[lbl] at (0.4,0.8) {insert $30$};
    \node[lbl, text=red] at (1.05,-2.45) {red-red};
  \end{scope}
  \draw[->, very thick] (1.7,-1.2) -- node[lbl, above, align=center] {Case 3} (3.0,-1.2);
  % --- panel 2: after fixup ---
  \begin{scope}[xshift=42mm]
    \node[blk] (b1) {$20$}
      child {node[red] {$10$}}
      child {node[red] {$30$}};
    \node[lbl] at (0,0.8) {rotated};
  \end{scope}
  \draw[->, very thick] (5.6,-1.2) -- node[lbl, above, align=center] {insert $15$,\\Case 1} (7.1,-1.2);
  % --- panel 3: after inserting 15 + recolor ---
  \begin{scope}[xshift=85mm]
    \node[blk] (c1) {$20$}
      child {node[blk] (c2) {$10$}
        child[missing]
        child {node[red] (c3) {$15$}}
      }
      child {node[blk] (c4) {$30$}};
    \node[lbl] at (0,0.8) {recolored};
  \end{scope}
  \draw[->, very thick] (10.1,-1.2) -- node[lbl, above, align=center] {insert $12$,\\Cases 2+3} (11.7,-1.2);
  % --- panel 4: final ---
  \begin{scope}[xshift=132mm]
    \node[blk] (d1) {$20$}
      child {node[blk] (d2) {$12$}
        child {node[red] {$10$}}
        child {node[red] {$15$}}
      }
      child {node[blk] (d3) {$30$}};
    \node[lbl] at (0,0.8) {done};
  \end{scope}
\end{tikzpicture}
$$

Check the final tree against the invariants: the root $20$ is black; the reds
$10$ and $15$ have only (nil) black children; and every root-to-nil path crosses
exactly two black nodes. Height $2$ for $5$ keys, comfortably inside the
$2\log_2(n+1)$ bound.

> **Intuition.** Red nodes are "free riders" inserted between black levels; the
> no-two-reds rule keeps them from stacking, and the equal-black-height rule
> keeps the black skeleton perfectly balanced. The black skeleton has height
> $\le \log_2(n+1)$, and reds at most double it.

The contrast is clearest on the worst possible input for a plain BST: keys
arriving already sorted. A naive tree threads them into a single descending path
of height $n-1$; the red-black invariants instead rebalance on the fly into a
bushy tree of height $O(\log n)$, with every root-to-leaf path carrying the same
black-height.

$$
% caption: The same keys $\langle 1,2,3,4,5,6,7\rangle$ inserted in order: a plain BST
%          degenerates to height $6$, a red-black tree stays at height $2$ with equal
%          black-heights
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6.5mm, inner sep=0, font=\small},
  red/.style={draw=red, text=red, line width=0.6pt},
  blk/.style={draw=black, text=black},
  level distance=11mm,
  level 1/.style={sibling distance=20mm},
  level 2/.style={sibling distance=11mm},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- degenerate BST: a right-leaning path ---
  \foreach \k [count=\i from 0] in {1,2,3,4,5,6,7} {
    \node[blk] (d\k) at (\i*0.62, -\i*0.78) {$\k$};
  }
  \foreach \a/\b in {1/2,2/3,3/4,4/5,5/6,6/7} {
    \draw[->] (d\a) -- (d\b);
  }
  \node[draw=none, font=\footnotesize] at (1.9,0.55) {plain BST: $h=6$};
  % --- balanced red-black tree (perfect, all blacks) ---
  \begin{scope}[xshift=52mm, yshift=-2mm]
    \node[blk] (r4) {$4$}
      child {node[blk] (r2) {$2$}
        child {node[red] {$1$}}
        child {node[red] {$3$}}
      }
      child {node[blk] (r6) {$6$}
        child {node[red] {$5$}}
        child {node[red] {$7$}}
      };
    \node[draw=none, font=\footnotesize] at (0,0.9) {red-black: $h=2$, $bh=1$};
  \end{scope}
\end{tikzpicture}
$$

### Red-black versus AVL

[AVL trees](/algorithms/data-structures/avl-trees) reach the same $O(\log n)$ guarantee with a different invariant:
the heights of any node's two subtrees differ by at most $1$, enforced by
rotations. The two invariants trade against each other.

- **Height.** The AVL condition is stricter, giving height at most
  $\approx 1.44\log_2 n$, versus the red-black bound of $2\log_2(n+1)$. Searches
  in an AVL tree therefore inspect fewer nodes in the worst case.
- **Update cost.** The looser red-black invariant is cheaper to maintain. A
  red-black insertion performs at most $2$ rotations and a deletion at most $3$,
  with everything else recoloring; an AVL insertion also stops after one
  rebalancing step, but an AVL _deletion_ can cascade rotations all the way up
  the path, $\Theta(\log n)$ of them in the worst case.

The practical split follows: read-heavy workloads with rare updates favor AVL's
shorter trees, while mixed insert/delete workloads favor red-black's cheaper
repairs, which is why red-black trees back many standard-library ordered
maps.[^skiena-balanced] Both cost $O(\log n)$ per operation either way; the
difference is in the constants.

::impl{algo="red_black_tree"}

## B-trees: balance for the disk

Red-black and AVL trees minimize the _number of nodes_ on a root-to-leaf path,
which is the right cost in memory. But when the data lives on a disk or SSD, the
cost that dominates is not comparisons but **block transfers**: reading one page
is millions of times slower than a memory comparison, and a binary tree of
$10^9$ keys has height $\approx 30$ — up to $30$ disk reads per search. The fix
is to make each node _short and wide_, sizing it to fill one disk block.

A $\textsc{B-tree}$ of minimum degree $t$ packs between $t-1$ and $2t-1$ keys per
node (with one more child than keys) and keeps all leaves at the same depth.[^clrs-btree]
The high fan-out pushes the height down to

$$
h \le \log_t \frac{n+1}{2} = O\!\parens{\frac{\log n}{\log t}},
$$

so with $t$ on the order of a thousand keys per block, a billion-key tree is just
$2$ or $3$ levels deep — two or three disk reads instead of thirty. Updates keep
the leaves level by **splitting** full nodes and **merging** underfull ones, all
local $O(t)$ work. B-trees (and the leaf-linked **B+-tree**) are the index
structure databases and filesystems rely on for exactly this reason. The full
treatment — node invariants, search, split/merge, and the height proof — is in
the dedicated [B-Trees](/algorithms/data-structures/b-trees) lesson.

## Other ways to stay balanced

Red-black and AVL trees enforce balance _deterministically_ by structural rules,
but they are two points in a much larger design space, and the alternatives trade
worst-case guarantees for simpler code or new capabilities.

**Randomized balance.** A **treap** (Seidel and Aragon, 1996) gives each key a
random priority and keeps the tree a BST on keys and a heap on priorities;
rotations restore the heap order after an insert. Because the priorities are
random, the expected height is $O(\log n)$ with no explicit balance bookkeeping,
the entire insert is "attach as a leaf, then rotate up while your priority beats
your parent's." A **skip list** reaches the same expected bound with a different
mechanism, covered in
[Skip Lists & Probabilistic Structures](/algorithms/data-structures/skip-lists-and-probabilistic-structures).

**Self-adjusting balance.** A **splay tree** (Sleator and Tarjan, 1985) keeps no
balance information at all. After every access it _splays_ the touched node to
the root by a sequence of rotations; individually an operation can be $\Theta(n)$,
but any sequence of $m$ operations costs $O(m \log n)$ amortized, and frequently
accessed keys drift near the root, giving the tree a built-in caching effect that
static-balance trees lack.

**Simpler code, same bound.** Sedgewick's **left-leaning red-black tree** (2008)
restricts red links to lean left, collapsing the many insert/delete cases down to
a handful and making red-black trees far easier to implement correctly.
**Weight-balanced** and **scapegoat trees** balance by subtree _sizes_ rather
than heights, rebuilding an entire subtree from scratch when it grows too
lopsided, which keeps amortized $O(\log n)$ with no per-node balance field.

**Persistence.** Because a rotation touches only $O(\log n)$ nodes on one path,
balanced BSTs are naturally **persistent**: copying just the changed path (path
copying) yields a new version of the tree while the old one survives intact, in
$O(\log n)$ extra space per update. This is why immutable/functional languages
use balanced BSTs (typically red-black or weight-balanced) as their standard
ordered-map implementation.[^btb-balanced]

## Takeaways

- A **balanced search tree** maintains a structural **invariant** that forces
  height $h = O(\log n)$, repairing it after each update so every operation is
  worst-case $O(\log n)$, not merely best-case.
- **Rotations** are the $O(1)$ primitive that reshapes a tree to change its
  height while preserving the BST property and sorted order.
- **Red-black trees** color nodes and enforce no-two-reds plus equal
  black-height; a counting argument shows $h \le 2\log_2(n+1)$.
- **Insert-fixup** has three cases: red uncle means recolor and climb two
  levels (Case 1); black uncle means straighten a zig-zag (Case 2) and finish
  with one rotation plus a color swap (Case 3). Total: $O(\log n)$ recolorings,
  at most $2$ rotations per insert, at most $3$ per delete.
- **AVL trees** reach the same bound with a stricter height-difference invariant:
  shorter trees, more rotations.
- $\textsc{B-trees}$ trade tall-and-thin for short-and-wide, packing $\Theta(t)$ keys
  per node so height is $O(\log_t n)$, minimizing **disk block transfers**, the
  dominant cost for on-disk data.

[^erickson-balanced]: **Erickson**, Ch. — Balanced Binary Search Trees: invariant-plus-rebalancing forces worst-case $O(\log n)$ height.
[^clrs-rotate]: **CLRS**, Ch. 13 — Red-Black Trees (§13.2): rotations as the $O(1)$ restructuring primitive that preserves the BST property.
[^clrs-rb]: **CLRS**, Ch. 13 — Red-Black Trees (§13.1): the color invariants that bound height to $2\log_2(n+1)$.
[^clrs-rb-insert]: **CLRS**, Ch. 13 — Red-Black Trees (§13.3): RB-Insert-Fixup and its three-case analysis; at most two rotations per insertion.
[^clrs-rb-delete]: **CLRS**, Ch. 13 — Red-Black Trees (§13.4): RB-Delete-Fixup, four cases per side, at most three rotations.
[^skiena-balanced]: **Skiena**, §3.4 — Balanced Search Trees: red-black trees as the practical balanced BST behind library ordered maps.
[^clrs-btree]: **CLRS**, Ch. 18 — B-Trees (§18.1): the minimum-degree structure with $t-1$ to $2t-1$ keys per node, minimizing disk transfers.
[^btb-balanced]: Seidel & Aragon, "Randomized search trees" (treaps, 1996); Sleator & Tarjan, "Self-adjusting binary search trees" (splay trees, 1985); Sedgewick, "Left-leaning red-black trees" (2008); Driscoll, Sarnak, Sleator & Tarjan, "Making data structures persistent" (1989).