ZERO / HERO
Straightening a leaning tower

Self-Balancing Trees & Rotations

The analogy

A search tree only stays fast if it stays bushy. Insert numbers in increasing order into a naive tree and you get a straight line — a linked list wearing a tree costume, and every search walks the whole thing. A self-balancing tree notices when one side is getting too tall and performs a small local rearrangement to straighten it.

Visualizer

Rotating a leaning tree

step 1 / 7
10

Insert 10, 20, 30 in increasing order into a plain BST. Watch the shape.inserted: 10

# Right rotation — O(1), and the in-order walk is unchanged
def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    return x            # x is the new subtree root

def height(n):  return 0 if n is None else n.height
def balance(n): return height(n.left) - height(n.right)
# AVL invariant: abs(balance(n)) <= 1 for every node

# In practice, in Python:
from sortedcontainers import SortedDict
d = SortedDict()
d.irange(10, 20)      # ordered range query
Check yourself

You insert 1,2,3,…,n into a plain (non-balancing) BST. Search cost?