Balanced Trees (Intro)

In the previous lesson on the Binary Search Tree you saw that a BST's O(log n) promise for search, insert, and delete only holds if the tree is roughly balanced — meaning its height is close to log₂(n). Insert already-sorted data into a plain BST and you don't get a nicely balanced tree at all; you get a skewed tree that behaves like a linked list. This lesson explains why that happens, the general idea of "self-balancing" trees that fix it, and where Java actually uses these structures under the hood.

The Skewed-Tree Problem

Consider inserting 10, 20, 30, 40, 50 — already sorted — into a plain BST. Every new value is larger than everything before it, so each node only ever gets a right child:

10
 \
  20
   \
    30
     \
      40
       \
        50

This is a valid BST, but its height is n instead of log n. Searching for 50 now means walking every node — the exact O(n) behavior a BST was supposed to avoid, identical to scanning a linked list.

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

// Inserting 10, 20, 30, 40, 50 in order into a plain BST
// produces a right-skewed chain — height n, not log n.
boolean contains(Node root, int target) {
    Node curr = root;
    while (curr != null) {
        if (curr.val == target) return true;
        curr = target < curr.val ? curr.left : curr.right;
    }
    return false;
}

Time complexity: O(h) where h is the tree's height — this becomes O(n) on the skewed tree above, but O(log n) on a balanced one. Space complexity: O(1) for the iterative search shown, since no extra structure grows with input size.

The Balance Concept

"Balanced" doesn't mean perfectly symmetric — it means the height difference between a node's left and right subtrees is kept small (bounded by a constant), so the overall height stays proportional to log n. Different self-balancing trees enforce this with different rules:

AVL Trees: Balance Factor

An AVL tree defines the balance factor of a node as:

A node is considered balanced if its balance factor is -1, 0, or 1. The moment an insert or delete pushes any node's balance factor outside that range, the tree performs a rotation to restore it — before the imbalance can compound further up the tree.

Rotation, Worked on 3 Nodes

The simplest case is inserting 10, then 20, then 30 in that order into an empty AVL tree. After inserting 30, the tree looks like this — right-skewed, balance factor of the root is -2:

Before rotation (unbalanced):

  10
   \
    20
     \
      30

Root (10): balance factor = 0 - 2 = -2   ← violation (right-heavy)

This is a "right-right" case, fixed with a single left rotation around the root. The middle node (20) becomes the new root, the old root (10) becomes its left child, and 30 stays the right child:

After a left rotation around 10:

      20
     /  \
    10   30

Balance factor of 20: 1 - 1 = 0   ← balanced

The mirror image — inserting 30, then 20, then 10 (left-left case) — is fixed with a single right rotation instead: the middle value (20) again ends up as the new root. When the imbalance zig-zags (e.g. left-right or right-left), AVL trees perform two rotations back to back to straighten it out. The mechanics differ slightly, but the goal is always the same: pull the middle value up to become the new subtree root so both sides end up roughly equal in height.

Red-Black Trees: What Java Actually Uses

AVL trees keep a very tight balance (height difference of at most 1), which makes lookups slightly faster but makes inserts/deletes more expensive because rebalancing happens more often. Red-Black trees relax that constraint — each node is colored red or black, and a small set of coloring rules (root is black, no two red nodes in a row, every path from root to a null leaf passes through the same number of black nodes) guarantees the height never exceeds roughly 2 · log2(n). That's a looser bound than AVL, but it means fewer rotations on average during modification.

This trade-off is exactly why Java's TreeMap and TreeSet are implemented internally as Red-Black trees — they favor balanced overall performance across inserts, deletes, and lookups rather than optimizing lookups alone.

// TreeMap keeps keys sorted using a Red-Black tree internally.
// You never see rotations or colors — they're an implementation detail.
TreeMap<Integer, String> map = new TreeMap<>();
map.put(50, "fifty");
map.put(20, "twenty");
map.put(70, "seventy");
map.put(10, "ten");

System.out.println(map.firstKey());  // 10 — smallest key
System.out.println(map.get(20));     // "twenty" — guaranteed O(log n) even after many inserts

Time complexity: O(log n) for get/put/firstKey — Red-Black balancing guarantees height stays logarithmic no matter the insertion order. Space complexity: O(n) to store n key-value entries plus a small constant overhead per node for color/parent pointers.