Balanced Trees

A sign-up service stores its users in a binary search tree, keyed by user ID. In testing, IDs were random and lookups took a few dozen steps at most. In production, IDs are handed out in order: 1, 2, 3, and so on. Each new user is bigger than everyone before, so each one becomes the right child of the last. After a million sign-ups the tree is a stick, a million levels deep, and finding the newest user takes a million steps.

The BST code is fine. The shape is the problem, and it came from the order of the data. A balanced tree is a search tree that repairs its own shape after every change, so it stays short no matter what order the data arrives in.

#Why height matters

Search, insert and delete in a BST each walk one path from the root down, so they all cost O(h), where h is the height. Compare the best and worst shapes:

A balanced tree does not need to be perfectly short. It only needs a height that stays within a constant factor of log₂ n. That is enough for every operation to be O(log n) in the worst case, not only on lucky inputs.

#AVL trees: a strict height rule

The AVL tree, the oldest balanced BST, adds one rule to the BST rule:

Each node stores its own height, as defined in Binary Trees. Left height minus right height is the node's balance factor, and it must be −1, 0 or +1. That keeps the height below about 1.44 log₂ n.

Insert as in a normal BST. Then, on the way back up to the root, each node on the path updates its height and checks its balance factor. Only those nodes can have changed. If one is off by 2, a rotation fixes it on the spot.

#Rotations

A rotation changes the shape of a small part of the tree without breaking the search order. In a right rotation, a node x and its left child y swap roles: y moves up, x becomes its right child. Their three subtrees, called A, B and C, are reattached so that the left-to-right order stays the same.

Of the three subtrees, only B changes parent, from y to x. That is safe: everything in B is bigger than y and smaller than x. A rotation changes three links, so it costs O(1). A left rotation is the mirror image.

// Each node has val, left, right and height.
function height(node) {
  return node === null ? 0 : node.height;
}
function update(node) {
  node.height = 1 + Math.max(height(node.left), height(node.right));
}
 
// x's left child y moves up, and x becomes y's right child.
function rotateRight(x) {
  const y = x.left;
  x.left = y.right; // the middle subtree B changes parent
  y.right = x;
  update(x); // x is lower now, so update it first
  update(y);
  return y;  // the new top of this subtree
}
// rotateLeft is the mirror: swap every left and right.

# Each node has val, left, right and height.
def height(node):
    return 0 if node is None else node.height
 
def update(node):
    node.height = 1 + max(height(node.left), height(node.right))
 
# x's left child y moves up, and x becomes y's right child.
def rotate_right(x):
    y = x.left
    x.left = y.right  # the middle subtree B changes parent
    y.right = x
    update(x)  # x is lower now, so update it first
    update(y)
    return y   # the new top of this subtree
# rotate_left is the mirror: swap every left and right.

#Single and double rotations, traced

When a node is off by 2, look at the path from it down toward the new value. If the path goes in a straight line (left-left or right-right), one rotation at the unbalanced node fixes it. If it zig-zags (left-right or right-left), first rotate the child to straighten the line, then rotate the node. Watch both cases while inserting 10, 20, 30, 25 and 28.

insert like a normal BSTwalk back up; at each node:  update its height  if one side is 2 taller:    if the path zig-zags: rotate the child first    rotate the node toward the shorter side

An insert causes at most one fix (a single or a double rotation), and the walk back up is O(log n). A delete can need a rotation at several levels on the way up, but each is O(1), so it is O(log n) too.

#Red-black trees: looser rules, fewer fixes

A red-black tree colours every node red or black and keeps these rules:

• The root is black.
• A red node never has a red child.
• Every path from a node down to an empty spot passes the same number of black nodes.

Together, these mean the longest path can be at most twice the shortest, so the height stays below about 2 log₂ n. That is less strict than AVL, so lookups may take a few more steps. In exchange, inserts and deletes need fewer rotations: most fixes are cheap recolourings, and an insert never needs more than two rotations. For data that changes a lot, that is a good trade. That is why the sorted maps in standard libraries are usually red-black trees: Java's TreeMap is one, and so is C++'s std::map in the common implementations.

#B-trees: wide and shallow, for disks

Binary trees assume following a pointer is cheap. On a disk, each node visited can be a separate read, thousands of times slower than memory. So the goal becomes: make the tree as shallow as possible, even if each node does more work.

A B-tree node holds many sorted keys, often hundreds, and has one more child than it has keys. The keys split the range of values, just as a single BST key splits it into left and right. All leaves sit at the same depth. When a node overflows, it splits in two and passes its middle key up to its parent, so the tree grows at the root and stays perfectly even.

With 500 children per node, the fourth level already holds 500 × 500 × 500 = 125 million nodes, each full of keys. A lookup reads four nodes, fewer if the top levels are cached in memory. A balanced binary tree needs 27 levels for just 125 million keys. That is why databases and file systems store their indexes as B-trees, usually a variant called the B+ tree.

#Common mistakes

#Check yourself

#What to practise next

That closes the trees module. The next step generalises trees: once nodes can connect in any pattern, with cycles and many parents, you have a graph. Start with Graph Basics.