Balanced Trees

A Balanced Tree is a Binary Search Tree that actively prevents itself from becoming too tall.

Why this matters: In a regular BST, search/insert/delete follow one root-to-leaf path. If the tree height is h, these operations take O(h). In the best case h ≈ log₂ n, but in the worst case (inserting sorted keys) h = n − 1, so operations degrade to O(n).

Balanced trees enforce a local invariant at each node—some small constraint about the relationship between its children. The key idea is:

• •The invariant is local (checkable near one node).
• •When the invariant is violated, we perform a local repair (rotation, plus metadata updates).
• •These local constraints are strong enough to force a global height bound: h = O(log n).

Two classic families:

1) AVL trees

• •Stronger invariant: each node’s left and right subtree heights differ by at most 1.
• •Result: very tightly balanced, excellent lookup performance.

2) Red-Black trees

• •Slightly weaker invariant: nodes are colored red/black with rules that limit long chains.
• •Result: still O(log n) height, typically fewer rotations on updates.

Both guarantee O(log n) search/insert/delete, but they trade off how strict the balancing is and how much work they do to maintain it.

A helpful mental model: balancing is not about making the tree perfectly symmetric—it's about ensuring you never get a long skinny path.

What “guaranteed O(log n)” really means

If n is the number of keys and the height is h, then:

• •Search: O(h)
• •Insert: O(h) to find the place + O(h) to fix up on the way back up
• •Delete: O(h) to find/remove + O(h) to fix up

Balanced trees ensure h ≤ c · log₂(n + 1) for some constant c.

• •For AVL, c is close to 1.44.
• •For Red-Black, c is at most 2.

So you keep predictable performance even under adversarial insertion orders.

Balanced trees rely on a single surgical tool: the rotation.

Why rotations exist: When a subtree becomes too tall on one side, we want to “tilt” it to redistribute height—but we must preserve the BST in-order property:

• •All keys in the left subtree < node key < all keys in the right subtree.

A rotation changes the shape while keeping the in-order sequence of keys exactly the same.

Left rotation

Consider a node x with right child y. A left rotation makes y the parent and x the left child.

Before:

• •x is root of this local subtree
• •y = x.right
• •β = y.left (a subtree)

After rotating left at x:

• •y becomes root
• •x becomes y.left
• •β becomes x.right

Key ordering remains valid because:

• •All keys in x.left are still < x
• •All keys in β are between x and y (so they must live as x.right)
• •All keys in y.right remain > y

Right rotation

Symmetric: rotate right at y when y has left child x.

Before:

• •y is root
• •x = y.left
• •β = x.right

After rotating right at y:

• •x becomes root
• •y becomes x.right
• •β becomes y.left

In-order preservation (why it works)

Think in terms of in-order traversal:

For the left rotation case, the in-order order of the local nodes/subtrees is:

• •(x.left), x, (β), y, (y.right)

After rotation, in-order becomes:

• •(x.left), x, (β), y, (y.right)

It’s identical.

Rotations and heights

Rotations are used because they change subtree heights in a controlled way.

If we define height as:

• •height(null) = −1 (common convention)
• •height(leaf) = 0
• •height(node) = 1 + max(height(left), height(right))

A rotation modifies only a constant-sized region, so height updates are local:

• •After rotation, recompute heights for the two nodes involved (and sometimes ancestors during fix-up).

Double rotations

Sometimes a single rotation is not enough. Two common cases:

• •Left-Right (LR) case: heavy on left child’s right side
• •Rotate left on left child
• •Then rotate right on the node

• •Right-Left (RL) case: heavy on right child’s left side
• •Rotate right on right child
• •Then rotate left on the node

These “double rotations” still act locally but correct more complex imbalance patterns.

Summary table: rotations

Rotations are the backbone of both AVL and Red-Black trees. The difference is the invariant that tells you when to rotate (and what extra metadata to update).

A balanced tree is defined less by rotations and more by the rule that determines when rotations are required.

AVL invariant (balance factor)

AVL trees track a height-based constraint at every node.

Define the balance factor:

bf(node) = height(left) − height(right)

AVL requires:

bf(node) ∈ {−1, 0, +1} for every node

Why this helps: If every node’s subtrees differ in height by at most 1, then long skewed chains can’t form.

AVL insertion repair (intuition)

Insertion is normal BST insertion first. Then, as you walk back up toward the root, you update heights and check balance factors.

If a node becomes unbalanced, bf becomes ±2, and you fix it using one of four cases:

• •LL case: inserted into left subtree of left child → Right rotation
• •RR case: inserted into right subtree of right child → Left rotation
• •LR case: inserted into right subtree of left child → Left rotation on child, then Right rotation
• •RL case: inserted into left subtree of right child → Right rotation on child, then Left rotation

A useful feature: for AVL insertion, after you rebalance at the first unbalanced node on the path upward, the subtree height is restored in a way that often stops further fixes.

AVL deletion repair (intuition)

Deletion can reduce heights, which may cause multiple ancestors to become unbalanced. AVL deletion may require rebalancing repeatedly up to the root.

Red-Black invariant (color + black-height)

Red-Black trees store one extra bit per node: color ∈ {red, black}.

They satisfy (one common formulation):

1) Every node is red or black.

2) The root is black.

3) All leaves (nulls) are black.

4) If a node is red, then both its children are black. (No two consecutive reds.)

5) For any node, every path from that node to any descendant leaf has the same number of black nodes. (Equal black-height.)

Why this helps:

• •Rule (4) prevents long red chains.
• •Rule (5) forces a form of uniformity: you can’t have one side with many more black nodes than the other.

Red-Black balancing is looser than AVL. It allows more shape variation, but still guarantees logarithmic height.

Height bound consequence (the big promise)

Balanced trees work because local constraints imply global height bounds.

Red-Black height sketch

Let bh be the black-height of the root (number of black nodes on any root→leaf path, excluding null leaf depending on convention).

From rule (4), between black nodes you can have at most one red node. So any root→leaf path has length at most:

h ≤ 2 · bh

Also, a subtree with black-height bh has at least 2ᵇʰ − 1 internal nodes (because each black level must branch enough to maintain that black-height; formally, the minimum-node RB tree of black-height bh is a perfect black-only tree).

So if n ≥ 2ᵇʰ − 1, then:

n + 1 ≥ 2ᵇʰ

log₂(n + 1) ≥ bh

Combine with h ≤ 2 · bh:

h ≤ 2 · log₂(n + 1)

Therefore search/insert/delete are O(log n).

AVL height sketch

AVL trees are even tighter. Let N(h) be the minimum number of nodes in an AVL tree of height h.

To minimize nodes for height h, you want children heights to be as small as allowed while still making height h:

• •One child has height h − 1
• •The other has height h − 2

So:

N(h) = 1 + N(h − 1) + N(h − 2)

With base cases:

• •N(−1) = 0
• •N(0) = 1

This is Fibonacci-like growth, implying N(h) grows exponentially in h, so h grows logarithmically in n.

A standard bound is:

h ≤ 1.44 · log₂(n + 2) − 1

The exact constant isn’t the key takeaway; the takeaway is: AVL forces h = O(log n) via a stricter local rule.

AVL vs Red-Black: practical comparison

Both are excellent. The right choice is often about engineering tradeoffs, not asymptotic complexity.

Balanced trees show up whenever you need an ordered collection with predictable performance.

Ordered maps and sets

Balanced trees implement:

• •Set: insert(x), delete(x), contains(x)
• •Map/dictionary: put(key, value), get(key), remove(key)

But unlike hash tables, they also support order-aware operations efficiently:

• •min/max
• •predecessor/successor
• •range queries: all keys in [a, b]
• •in-order traversal in sorted order

Because height is O(log n):

• •predecessor/successor are O(log n)
• •range query costs O(log n + k), where k is the number of reported elements

Why not just use hashing?

Hash tables are great for average-case O(1) lookups, but:

• •They don’t maintain sorted order.
• •Range queries are awkward.
• •Worst-case can degrade (depending on hashing and adversarial inputs).

Balanced trees give a clean, deterministic guarantee.

Where AVL vs Red-Black often appears

• •Many standard libraries implement TreeMap/TreeSet-like structures with Red-Black trees (good all-around performance, simpler rebalancing in practice).
• •AVL trees can be chosen when lookup speed is critical and updates are less frequent.

Rotations as a general technique

Rotations aren’t only for BSTs. The broader pattern is:

• •Maintain a local invariant
• •When it breaks, apply a constant-sized local transformation

You’ll see this in other data structures (e.g., B-trees have splits/merges; heaps have sift-up/down).

Performance summary

If a balanced tree maintains height h = O(log n), then:

• •Search: O(log n)
• •Insert: O(log n)
• •Delete: O(log n)
• •Space: O(n)

The “magic” is that the balancing work per operation is bounded by a constant number of rotations per violated node, and the number of visited nodes is proportional to the height.

In other words:

Time(operation) = O(height) = O(log n)

That guarantee is exactly why balanced trees are still a core part of CS—even in a world full of hash tables.