Self-balancing trees

In Lesson 10 you watched a binary search tree decay: insert already-sorted keys and every value keeps going right, so the tree becomes a straight chain of height $n-1$ and search collapses from $O(\log n)$ to $O(n)$. That is not a rare edge case - sorted or near-sorted input is everywhere (timestamps, autoincrement IDs, alphabetized names). Self-balancing trees fix it permanently: after every insert they do a small, cheap fix-up so the height can never drift far from ${\log }_{2}n$. This lesson gives you the intuition, the real bound, and a tree you can rotate with your own hands.

Why height is the whole game

Every operation on a search tree - find, insert, delete - walks one root-to-leaf path, so its cost is exactly the height $h$. A perfectly balanced tree of $n$ nodes has $h\approx {\log }_{2}n$; a fully skewed one has $h=n-1$. Same nodes, same ordering rule, wildly different cost. The entire job of a balancing scheme is to keep $h$ small no matter what order the data arrives in.

Rotate it yourself

This is the centerpiece. Insert values and watch each one fall into place, then - in AVL mode - watch the tree rotate the instant a node's two sides differ by more than one. Flip to plain BST mode to turn balancing off, press Insert 1->7, and watch the same sorted keys build a tall degenerate chain while the height readout climbs. Then try B-tree mode and watch an overfull node split.

Red-black trees and B-trees, and why they exist

You rarely hand-roll these. Red-black trees are the balance scheme hiding inside most standard-library ordered maps - C++ std::map, Java TreeMap, the Linux kernel's scheduler. They rebalance with rotations plus a one-bit color rule, favoring fewer rotations per update over the tightest possible height. Whenever you rely on an ordered map for guaranteed $O(\log n)$ lookups, a red-black tree is doing the work.

B-trees answer a different question: what if the tree lives on disk? Reading one node from disk (a page) costs thousands of times more than a comparison in RAM. So a B-tree makes each node wide - dozens or hundreds of keys - so the tree is only a handful of levels deep, and a lookup touches a handful of pages instead of ${\log }_{2}n$ of them. When a node overfills, it splits and pushes its middle key up (try B-tree mode above). Height grows as $O({\log }_{t}n)$ where $t$ is the branching factor, and the giant $t$ crushes it flat. This is why B-trees (and B+-trees) index nearly every relational database and filesystem on earth.

Insert with rebalancing is a small addition to the ordinary BST recursion - update the height, check the balance factor, and rotate if it exceeds one:

def insert(node, val):
    if node is None:
        return Node(val)
    if val < node.val:  node.left  = insert(node.left,  val)
    elif val > node.val: node.right = insert(node.right, val)
    else:              return node                # no duplicates

    node.height = 1 + max(h(node.left), h(node.right))
    bf = h(node.left) - h(node.right)     # balance factor

    if bf >  1 and h(node.left.left)  >= h(node.left.right):   return rotate_right(node)  # LL
    if bf < -1 and h(node.right.right)>= h(node.right.left):  return rotate_left(node)   # RR
    if bf >  1:  node.left  = rotate_left(node.left);   return rotate_right(node)  # LR
    if bf < -1: node.right = rotate_right(node.right); return rotate_left(node)   # RL
    return node

Check yourself