Rotations & Why a BST Degenerates
In short: a binary search tree is only fast if it's short. Insert keys in sorted order and a plain BST never branches — every new key goes right (or always left), and it degenerates into a linked list: search goes from O(log n) to O(n). A rotation fixes one lopsided spot in three pointer moves, without touching most of the tree and without breaking the BST ordering — everything still reads left-to-right the same way. It's the one move every self-balancing tree in this section builds on.
Inserting ids in order
Quarry's index layer sometimes gets keys that arrive already sorted —
auto-incrementing ids, timestamps, a bulk import from another system in
order. A plain BST insert (less than: go left, else go right) handles
this correctly, but not fast:
Height 8 for 8 keys — every key has exactly one child, a straight line.
Search, insert and delete all become O(n). A balanced arrangement of the
same 8 keys has height 4 (⌈log₂9⌉), and the gap only gets worse as n
grows: 20 keys in order gives height 20 instead of about 5.
The three pointer moves
A rotation takes a parent and its heavy child and swaps who's on top,
without changing what an in-order walk reads. Rotating right at x
(its left child y rises):
Three assignments, always — however big the subtrees hanging off y and
x are, because a rotation only re-points the nodes directly involved.
Everything below y.right or above x never gets touched, which is why a
rotation is O(1), not O(subtree size).
3 has a left child 2, which has a left child 1 — a straight line leaning left. A rotate-right at 3 straightens it in one move.
This is the straight-line shape: 3 over 2 over 1, all on the left. An in-order walk still reads 1, 2, 3. Binary tree, 3 nodes, height 3. At node 3.
Watch what stays the same
The whole point of a rotation is that it's invisible to anyone reading the tree in order — only the shape changes, never the answer to "what's here."
class Node:
def __init__(self, v):
self.v = v
self.left = self.right = None
def inorder(n, out):
if n is None:
return
inorder(n.left, out)
out.append(n.v)
inorder(n.right, out)
# 3 -> left 2 -> left 1 (a straight line)
one = Node(1)
two = Node(2)
two.left = one
three = Node(3)
three.left = two
def rotate_right(x):
y = x.left
x.left = y.right
y.right = x
return y
new_root = rotate_right(three)
out = []
inorder(new_root, out)
print(out)RecursionErrorThis builds a cycle instead of a rotation (x.left ends up equal to x), and walking it recurses forever. Swap the two assignment lines.
What it costs
| operation | cost | why |
|---|---|---|
| one rotation | O(1) | exactly 3 pointer reassignments, whatever the subtree sizes |
| height of a degenerate BST (n sorted inserts) | O(n) | every insert only ever extends one branch |
| height of a balanced BST | O(log n) | each level can hold twice as many keys as the one above |
| keeping a tree balanced after every insert | O(log n) rotations worst case per insert | later lessons in this section show how |
Quick practice
class Node:
def __init__(self, v):
self.v = v
self.left = self.right = None
def height(n):
if n is None:
return 0
return 1 + max(height(n.left), height(n.right))
a = Node(1)
a.right = Node(2)
a.right.right = Node(3)
a.right.right.right = Node(4)
print(height(a))This prints [4, 5, 3, 4] instead of [3, 4, 5, 6] — 6 vanishes and 4 duplicates. Fix the one word.
🎯 Your turn
Build single_rotation_report(values, direction): insert values one at a
time into a plain BST (no balancing), then perform exactly one rotation
at the root — "left" uses the root's right child, "right" uses the
root's left child. Return {"height_before": ..., "height_after": ..., "inorder": [...]}. If the needed child doesn't exist, return the
height_before value for both heights and an empty inorder.
single_rotation_report([1, 2, 3, 4, 5, 6, 7, 8], "left")→{"height_before": 8, "height_after": 7, "inorder": [1, 2, 3, 4, 5, 6, 7, 8]}single_rotation_report([3, 2, 1], "right")→{"height_before": 3, "height_after": 2, "inorder": [1, 2, 3]}
Hint: build the tree with the plain insert from this lesson, measure
height, rotate once at the root if the needed child exists, measure
height again, and walk the result in-order.
Press ▶ Run, then ✓ Check.