Balanced Search Trees

The previous lesson left us with a sharp problem. A binary search tree 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.¹ The guarantee becomes worst-case, not best-case: $O(\log n)$ per operation, on every input.

Different balanced trees enforce different invariants. 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.

In both trees the sorted order is $T_1<x<T_2<y<T_3$ — a rotation never violates the BST property.² 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.

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.³ Five invariants on those colors squeeze the tree into logarithmic 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:

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$).

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,

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

$\text{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 $\text{RB-Insert-Fixup}$ repairs the local one by walking up the tree.⁴

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\leftarrow G$ and repeat.

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.

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

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

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.

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.

Red-black versus AVL

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.⁶ Both cost $O(\log n)$ per operation either way; the difference is in the constants.

from collections.abc import Iterator
from enum import Enum
from typing import Generic, Optional, TypeVar

from comparable import Comparable

Key = TypeVar("Key", bound=Comparable)

class Color(Enum):
  """
    A node's color bit. The nil sentinel and the root are always black.\n
  """
  RED = 0
  BLACK = 1

class RedBlackNode(Generic[Key]):
  """
    One red-black tree node: a key, a color, and links to its parent and\n
    two children. Absent children point at the tree's shared black `nil`\n
    sentinel rather than at None, which removes the special cases when a\n
    fix-up reads a missing child's color.\n
  """

  def __init__(self, key: Key, color: Color) -> None:
    self.key: Key = key
    self.color: Color = color
    self.left: RedBlackNode[Key] = self
    self.right: RedBlackNode[Key] = self
    self.parent: RedBlackNode[Key] = self

  def __repr__(self) -> str:
    return f"RedBlackNode({self.key!r}, {self.color.name})"

class RedBlackTree(Generic[Key]):
  """
    An ordered set of comparable keys with O(log n) search and updates.\n
    A single shared `nil` node stands in for every leaf and for the parent\n
    of the root; it is black, so the invariants hold trivially at the edges.\n
  """

  def __init__(self) -> None:
    # the sentinel is black and points at itself; every leaf and the root's
    # parent reference it, so fix-ups never special-case a missing child.
    self.nil: RedBlackNode[Key] = RedBlackNode.__new__(RedBlackNode)
    self.nil.color = Color.BLACK
    self.nil.left = self.nil
    self.nil.right = self.nil
    self.nil.parent = self.nil

    # an empty tree is just the sentinel.
    self.root: RedBlackNode[Key] = self.nil
    self._size: int = 0

  # -- rotations -------------------------------------------------------------

  def left_rotate(self, pivot: RedBlackNode[Key]) -> None:
    """
      Pivot `pivot` down-left so its right child rises into its place.\n
      Rearranges a constant number of pointers and preserves the BST\n
      property; runs in O(1) time.\n
    """
    # the right child rises; its left subtree becomes `pivot`'s new right.
    riser: RedBlackNode[Key] = pivot.right
    pivot.right = riser.left
    if riser.left is not self.nil:
      riser.left.parent = pivot

    # splice `riser` where `pivot` used to hang.
    riser.parent = pivot.parent
    if pivot.parent is self.nil:
      self.root = riser
    elif pivot is pivot.parent.left:
      pivot.parent.left = riser
    else:
      pivot.parent.right = riser

    # drop `pivot` under `riser`.
    riser.left = pivot
    pivot.parent = riser

  def right_rotate(self, pivot: RedBlackNode[Key]) -> None:
    """
      The mirror of left_rotate: pivot `pivot` down-right so its left\n
      child rises. Also O(1) and order-preserving.\n
    """
    # the left child rises; its right subtree becomes `pivot`'s new left.
    riser: RedBlackNode[Key] = pivot.left
    pivot.left = riser.right
    if riser.right is not self.nil:
      riser.right.parent = pivot

    # splice `riser` where `pivot` used to hang.
    riser.parent = pivot.parent
    if pivot.parent is self.nil:
      self.root = riser
    elif pivot is pivot.parent.right:
      pivot.parent.right = riser
    else:
      pivot.parent.left = riser

    # drop `pivot` under `riser`.
    riser.right = pivot
    pivot.parent = riser

  # -- search ----------------------------------------------------------------

  def _find_node(self, key: Key) -> RedBlackNode[Key]:
    """
      The node carrying `key`, or the `nil` sentinel if it is absent.\n
    """
    # branch left or right by comparison until the key or `nil` is reached.
    current: RedBlackNode[Key] = self.root
    while current is not self.nil and current.key != key:
      current = current.left if key < current.key else current.right
    return current

  def __contains__(self, key: Key) -> bool:
    return self._find_node(key) is not self.nil

  def minimum(self, subtree: Optional[RedBlackNode[Key]] = None) -> RedBlackNode[Key]:
    """
      The smallest-key node of a subtree (the whole tree by default).\n
      Returns the `nil` sentinel for an empty subtree.\n
    """
    current: RedBlackNode[Key] = self.root if subtree is None else subtree
    if current is self.nil:
      return self.nil

    # follow left links to the smallest key.
    while current.left is not self.nil:
      current = current.left
    return current

  def maximum(self, subtree: Optional[RedBlackNode[Key]] = None) -> RedBlackNode[Key]:
    """
      The largest-key node of a subtree (the whole tree by default).\n
    """
    current: RedBlackNode[Key] = self.root if subtree is None else subtree
    if current is self.nil:
      return self.nil

    # follow right links to the largest key.
    while current.right is not self.nil:
      current = current.right
    return current

  # -- insertion -------------------------------------------------------------

  def insert(self, key: Key) -> None:
    """
      Add `key`. Re-inserting a key already present is a no-op, so the\n
      tree behaves as a set. Restores the color invariants afterward.\n
    """
    # descend to the leaf where `key` belongs, bailing out if it already exists.
    parent: RedBlackNode[Key] = self.nil
    current: RedBlackNode[Key] = self.root
    while current is not self.nil:
      parent = current
      if key == current.key:
        return
      current = current.left if key < current.key else current.right

    # new nodes start red — that keeps every path's black-height unchanged,
    # so only the no-two-reds rule can break, which the fix-up repairs.
    fresh: RedBlackNode[Key] = RedBlackNode(key, Color.RED)
    fresh.left = self.nil
    fresh.right = self.nil
    fresh.parent = parent

    # hang the leaf off `parent` on the correct side (or make it the root).
    if parent is self.nil:
      self.root = fresh
    elif key < parent.key:
      parent.left = fresh
    else:
      parent.right = fresh

    self._size += 1
    self._insert_fixup(fresh)

  def _insert_fixup(self, node: RedBlackNode[Key]) -> None:
    """
      Restore the red-black invariants after inserting the red `node`.\n
      Walks toward the root recoloring on a red uncle and rotating on a\n
      black uncle, so it does O(1) work per level over an O(log n) path.\n
    """
    # climb while the red `node` sits under a red parent, fixing one level a step.
    while node.parent.color is Color.RED:
      grandparent: RedBlackNode[Key] = node.parent.parent
      if node.parent is grandparent.left:
        uncle: RedBlackNode[Key] = grandparent.right

        # case 1: red uncle — recolor and push the violation up two levels.
        if uncle.color is Color.RED:
          node.parent.color = Color.BLACK
          uncle.color = Color.BLACK
          grandparent.color = Color.RED
          node = grandparent
        else:

          # case 2: bend the zig-zag into a straight line, then fall through.
          if node is node.parent.right:
            node = node.parent
            self.left_rotate(node)

          # case 3: straighten with one rotation and recolor.
          node.parent.color = Color.BLACK
          grandparent.color = Color.RED
          self.right_rotate(grandparent)
      else:

        # mirror image of the three cases above.
        uncle = grandparent.left
        if uncle.color is Color.RED:
          node.parent.color = Color.BLACK
          uncle.color = Color.BLACK
          grandparent.color = Color.RED
          node = grandparent
        else:
          if node is node.parent.left:
            node = node.parent
            self.right_rotate(node)
          node.parent.color = Color.BLACK
          grandparent.color = Color.RED
          self.left_rotate(grandparent)

    # the root is always black.
    self.root.color = Color.BLACK

  # -- deletion --------------------------------------------------------------

  def _transplant(
    self,
    removed: RedBlackNode[Key],
    replacement: RedBlackNode[Key],
  ) -> None:
    """
      Replace the subtree rooted at `removed` with that of `replacement`,\n
      rewiring only the parent link (the caller fixes the children).\n
    """
    # point `removed`'s parent at `replacement` on the matching side.
    if removed.parent is self.nil:
      self.root = replacement
    elif removed is removed.parent.left:
      removed.parent.left = replacement
    else:
      removed.parent.right = replacement

    replacement.parent = removed.parent

  def delete(self, key: Key) -> bool:
    """
      Remove `key` if present, restoring the invariants. Returns False\n
      when the key was not in the tree.\n
    """
    target: RedBlackNode[Key] = self._find_node(key)
    if target is self.nil:
      return False

    # `moved` is the node leaving its position; track the color it gives up,
    # since losing a black node may break the equal-black-height rule.
    moved: RedBlackNode[Key] = target
    moved_original_color: Color = moved.color

    # at most one child: promote it straight into `target`'s slot.
    if target.left is self.nil:
      fixup_start: RedBlackNode[Key] = target.right
      self._transplant(target, target.right)
    elif target.right is self.nil:
      fixup_start = target.left
      self._transplant(target, target.left)
    else:

      # two children: the successor (right-subtree minimum) takes `target`'s place.
      successor: RedBlackNode[Key] = self.minimum(target.right)
      moved = successor
      moved_original_color = successor.color
      fixup_start = successor.right

      # detach the successor, carrying `target`'s right subtree with it.
      if successor.parent is target:
        fixup_start.parent = successor
      else:
        self._transplant(successor, successor.right)
        successor.right = target.right
        successor.right.parent = successor

      # move the successor over `target` and adopt its left subtree and color.
      self._transplant(target, successor)
      successor.left = target.left
      successor.left.parent = successor
      successor.color = target.color

    self._size -= 1

    # removing a black node leaves an extra black to resolve at `fixup_start`.
    if moved_original_color is Color.BLACK:
      self._delete_fixup(fixup_start)
    return True

  def _delete_fixup(self, node: RedBlackNode[Key]) -> None:
    """
      Restore the invariants after a black node was removed. `node` carries\n
      an extra unit of black that we push up or resolve with rotations and\n
      recolorings, O(1) per level along an O(log n) path.\n
    """
    # carry the extra black up until it lands on a red node or the root.
    while node is not self.root and node.color is Color.BLACK:
      if node is node.parent.left:
        sibling: RedBlackNode[Key] = node.parent.right

        # case 1: red sibling — recolor and rotate to get a black sibling.
        if sibling.color is Color.RED:
          sibling.color = Color.BLACK
          node.parent.color = Color.RED
          self.left_rotate(node.parent)
          sibling = node.parent.right

        # case 2: sibling's children both black — recolor, push black up.
        if (
          sibling.left.color is Color.BLACK
          and sibling.right.color is Color.BLACK
        ):
          sibling.color = Color.RED
          node = node.parent
        else:

          # case 3: bend so the sibling's far child is red.
          if sibling.right.color is Color.BLACK:
            sibling.left.color = Color.BLACK
            sibling.color = Color.RED
            self.right_rotate(sibling)
            sibling = node.parent.right

          # case 4: one rotation absorbs the extra black and ends the loop.
          sibling.color = node.parent.color
          node.parent.color = Color.BLACK
          sibling.right.color = Color.BLACK
          self.left_rotate(node.parent)
          node = self.root
      else:

        # mirror image of the four cases above.
        sibling = node.parent.left

        # case 1: red sibling.
        if sibling.color is Color.RED:
          sibling.color = Color.BLACK
          node.parent.color = Color.RED
          self.right_rotate(node.parent)
          sibling = node.parent.left

        # case 2: both of the sibling's children are black.
        if (
          sibling.right.color is Color.BLACK
          and sibling.left.color is Color.BLACK
        ):
          sibling.color = Color.RED
          node = node.parent
        else:

          # case 3: bend so the sibling's far child is red.
          if sibling.left.color is Color.BLACK:
            sibling.right.color = Color.BLACK
            sibling.color = Color.RED
            self.left_rotate(sibling)
            sibling = node.parent.left

          # case 4: one rotation absorbs the extra black and ends the loop.
          sibling.color = node.parent.color
          node.parent.color = Color.BLACK
          sibling.left.color = Color.BLACK
          self.right_rotate(node.parent)
          node = self.root

    # whatever the extra black landed on becomes black.
    node.color = Color.BLACK

  # -- traversal -------------------------------------------------------------

  def __iter__(self) -> Iterator[Key]:
    """
      Yield every key in ascending order via an in-order walk.\n
    """

    def walk(node: RedBlackNode[Key]) -> Iterator[Key]:
      if node is self.nil:
        return
      yield from walk(node.left)
      yield node.key
      yield from walk(node.right)

    yield from walk(self.root)

  def __len__(self) -> int:
    return self._size

  def height(self) -> int:
    """
      The number of edges on the longest root-to-leaf path (-1 if empty).\n
    """

    def measure(node: RedBlackNode[Key]) -> int:
      if node is self.nil:
        return -1
      return 1 + max(measure(node.left), measure(node.right))

    return measure(self.root)

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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 $\text{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.⁷ The high fan-out pushes the height down to

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

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

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.
• $\text{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.