Balancing: Keeping the Tree Honest

"A plain BST is one sorted input away from collapsing into a linked list. Self-balancing trees refuse to let that happen — they quietly reshape themselves so the height can never explode."

The Fix: Trees That Rebalance Themselves

Last lesson's villain was the lopsided tree: insert sorted data, get an O(n) chain. Self-balancing trees solve it by automatically restructuring after each insert or delete, keeping the height pinned near log n no matter what order the data arrives in. The result is a hard guarantee: O(log n) search, insert, and delete — worst case, not just average. They turn the BST from "fast if you're lucky" into "fast, period."

The Mechanism: Rotations

The magic is a local move called a rotation: pivot a node and its child, promoting one and lowering the other, while the inorder key sequence stays untouched. One rotation changes only O(1) pointers. A full rebalance may also repair heights, colors, or several places along a path, so the exact choreography depends on the tree and operation. You do not need to memorize every case yet—hold onto the gem: reshape the tree without breaking its sorted order.

Two Famous Flavors

AVL trees — keep each node's subtree-height difference at most 1. Their tighter height bound often shortens lookup paths, but write cost must be compared for the actual workload and implementation.
Red-black trees — use color rules to keep height O(log n) with looser balance. They back Java TreeMap, common C++ std::map implementations, and parts of Linux, but that does not make them universally faster for write-heavy workloads.

B-tree and B+tree families use wide nodes to reduce storage-page reads and are common database index defaults. They are not the only indexes: hash, inverted, and spatial indexes serve different queries.

Self-balancing BSTs use rotations plus auxiliary rules to keep height O(log n), guaranteeing worst-case O(log n) lookup and updates. AVL and red-black trees enforce different balance invariants; B-tree families use wide nodes to reduce storage-page accesses.

The Practical Python Reality

Here's a fact that surprises people: Python has no built-in balanced BST. No TreeMap, no std::map equivalent in the standard library. So when you genuinely need ordered operations in Python, you reach for: the bisect module (binary search and insertion into a sorted list — great when you read far more than you insert), or a third-party ordered container such as sortedcontainers, whose exact complexity contract should be checked in its current documentation. Knowing the theory tells you what you need; knowing the ecosystem tells you which tool actually delivers it.

Pippa's Confession

I went looking for Python's TreeMap and... there isn't one. I was indignant — every other language has a balanced tree in its standard library! Dad explained the design choice: Python's dict (hashing) is so good for the common case that ordered maps were left to bisect and third-party libs. The lesson wasn't about trees; it was that 'the right structure' includes 'what's actually available in your language' — theory and ecosystem are both part of the decision.

Code

A rotation, and Python's bisect substitute·python

# A right rotation, conceptually: rebalance while keeping BST order intact.
#     y            x
#    / \          / \
#   x   C   -->  A   y
#  / \              / \
# A   B            B   C
# Before: A < x < B < y < C.  After: A < x < B < y < C.  Order preserved!
class N:
    def __init__(s, k): s.k=k; s.left=None; s.right=None

def rotate_right(y):
    x = y.left
    y.left = x.right    # B moves under y
    x.right = y         # y becomes x's right child
    return x            # x is the new subtree root (shorter on the left now)

# The PRACTICAL Python answer for ordered ops: the bisect module on a sorted list.
import bisect
sorted_keys = [1, 3, 6, 8, 10]
bisect.insort(sorted_keys, 7)        # insert keeping sorted order: O(n) shift, O(log n) find
print(sorted_keys)                    # [1, 3, 6, 7, 8, 10]
i = bisect.bisect_left(sorted_keys, 7)
print("7 is at index", i)             # 3 — O(log n) search
# For heavier ordered workloads, SortedList/SortedDict from 'sortedcontainers'\n# are concrete third-party options; verify current docs and benchmark your workload.
# Python has NO built-in balanced BST — this is the idiomatic substitute.

Exercise

Explain why a tree rotation can rebalance a subtree WITHOUT breaking the BST ordering invariant (trace where subtrees A, B, and C land). Then compare AVL and red-black balance rules for a read-heavy ordered map without claiming either is universally faster.

Hint

A rotation only re-parents nodes; A < x < B < y < C remains true. AVL's tighter height bound can shorten lookup paths, while update behavior depends on the tree operation, implementation, and workload—benchmark when the distinction matters.

The Fix: Trees That Rebalance Themselves

The Mechanism: Rotations

Two Famous Flavors

The Practical Python Reality

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0