--- title: 'Balanced Search Trees' source: 'https://academia.sh/en/courses/data-structures/balanced-search-trees' course: 'Data Structures' language: en updated: '2026-08-17T18:08:00+00:00' license: 'CC BY-SA 4.0' --- # Balanced Search Trees The rotation operation, the AVL balance criterion and its four cases, red–black tree color invariants, and a comparison of the two families. The previous lesson ended with a problem: a binary search tree's height depends on insertion order, and sorted input turns the tree into a linked list. The solution is to check the tree after every change and **rearrange** it whenever imbalance occurs. This lesson's subject is the operation that performs the rearrangement, and two classic rule sets that say when to apply it. ## Rotation **Rotation** is a local operation that changes a tree's height by redirecting a link. Its most important property is that **it does not break the ordering invariant.** ``` right rotation (about y) left rotation (y) (x) (x) (y) / \ / \ / \ / \ (x) C → A (y) A (y) → (x) C / \ / \ / \ / \ A B B C B C A B ``` In a right rotation, `x` moves up and `y` moves down; subtree `B` moves from `x`'s right to `y`'s left. Nothing changes in terms of ordering: the relation `A < x < B < y < C` holds in both forms. The only thing that changes is height. A rotation writes a fixed number of links; its cost is $O(1)$. ```python class AVLNode: def __init__(self, value: int) -> None: self.value = value self.left: "AVLNode | None" = None self.right: "AVLNode | None" = None self.height = 0 # leaf: 0 def h(node: AVLNode | None) -> int: return -1 if node is None else node.height def update(node: AVLNode) -> None: node.height = 1 + max(h(node.left), h(node.right)) def balance(node: AVLNode | None) -> int: """Left height minus right height.""" return 0 if node is None else h(node.left) - h(node.right) def rotate_right(y: AVLNode) -> AVLNode: x = y.left y.left = x.right # subtree B changes place x.right = y update(y); update(x) # the lower node is updated first return x # new root def rotate_left(x: AVLNode) -> AVLNode: y = x.right x.right = y.left y.left = x update(x); update(y) return y ``` The order of the height update matters: the lower node must be updated first, because the height of the one above depends on it. ## AVL Tree An **AVL tree** enforces the following condition at every node: > The difference between the left and right subtrees' heights is at most one. This difference is the node's **balance factor**. Its value must be $-1$, $0$, or $+1$; when it becomes $\pm 2$, there is imbalance, and it is corrected. The condition is strict, and in exchange it gives a tight height bound: the height of an AVL tree with $n$ nodes never exceeds $1.44 \log_2 n$. Search, insertion, and deletion are therefore always $O(\log n)$ — a degenerate case is impossible. ## Four Cases Imbalance after insertion arises in four forms. Their names describe the path from the unbalanced node to the inserted node. | Case | Symptom | Fix | |---|---|---| | Left–left | Balance $> 1$, left child's balance $\geq 0$ | Right rotation | | Right–right | Balance $< -1$, right child's balance $\leq 0$ | Left rotation | | Left–right | Balance $> 1$, left child's balance $< 0$ | Rotate the left child left, then rotate right | | Right–left | Balance $< -1$, right child's balance $> 0$ | Rotate the right child right, then rotate left | In the last two cases a single rotation is not enough: the imbalance is "zigzag" shaped, and it is first straightened out, then corrected. ```python def insert_avl(root: AVLNode | None, value: int) -> AVLNode: if root is None: return AVLNode(value) if value < root.value: root.left = insert_avl(root.left, value) elif value > root.value: root.right = insert_avl(root.right, value) else: return root # duplicate value update(root) d = balance(root) if d > 1 and balance(root.left) >= 0: # left–left return rotate_right(root) if d < -1 and balance(root.right) <= 0: # right–right return rotate_left(root) if d > 1: # left–right root.left = rotate_left(root.left) return rotate_right(root) if d < -1: # right–left root.right = rotate_right(root.right) return rotate_left(root) return root def inorder(node, result=None): result = [] if result is None else result if node is not None: inorder(node.left, result) result.append(node.value) inorder(node.right, result) return result # Sorted insertion: this would degenerate in a plain search tree. root = None for value in (3, 7, 10, 12, 25, 30): root = insert_avl(root, value) print(inorder(root)) # [3, 7, 10, 12, 25, 30] print(root.value) # 12 — the root settled in the middle on its own print(h(root)) # 2 — this would be 5 in a degenerate tree ``` Inserting the six values in ascending order produced a chain of height five in the previous lesson. The AVL rule keeps the height at two on the same input; the rotations ran on their own during insertion. At most **one** rotation (or a double rotation) is needed after an insertion; height updates are performed along the path down from the root. The cost of insertion therefore stays $O(\log n)$. ## Red–Black Trees The second classic family tracks balance not with heights but with **colors**. Every node is colored red or black, and four invariants are maintained: 1. The root is black. 2. A red node's children are black — two red nodes cannot be consecutive. 3. Every path from the root to any empty link contains the same number of black nodes. 4. Empty links count as black. The third condition ensures the tree is perfectly balanced in terms of "black height." The longest path can be at most twice the shortest — because the longest path alternates red and black, while the shortest is entirely black. From this the height bound follows: $$ h \leq 2 \log_2 (n + 1) $$ This is looser than AVL's $1.44 \log_2 n$ bound; the tree can be slightly deeper. In exchange, the amount of rearrangement needed to maintain balance is small: a constant number of rotations suffices for insertion and deletion, whereas in AVL a chain of rotations up to the root's path can occur during deletion. ## Choosing Between the Two Families | Criterion | AVL | Red–black | |---|---|---| | Height bound | $\approx 1.44 \log_2 n$ | $\approx 2 \log_2 n$ | | Search | Slightly faster | Slightly slower | | Insert/delete | More rotations | Fewer rotations | | Suited to | Read-heavy | Write-heavy | General-purpose libraries' ordered map and ordered set structures mostly use red–black trees: more predictable update cost is worth more, in general use, than the difference in search speed. The shared cost of both families is code complexity. Deletion cases are especially numerous and are a common source of error in hand-written implementations. The skip list from the Linear Structures topic is an alternative, since it gives the same expected cost with far shorter code — the difference is that its guarantee is expected, not certain. ## Summary - Rotation is a constant-cost operation that changes height by redirecting links while preserving the ordering invariant. - In an AVL tree every node's balance factor must be $-1$, $0$, or $+1$; a violation is fixed with one of four cases. - Zigzag-shaped imbalances (left–right, right–left) are first straightened with a single rotation. - The AVL height bound is about $1.44 \log_2 n$; a degenerate case is impossible. - A red–black tree tracks balance with color invariants; its bound is looser but it requires fewer rotations on update. - AVL is preferred under a read-heavy load, red–black under a write-heavy one. ## Next Step In binary trees, balance is repaired after the fact with rotations. A different approach is to hold more than one key per node and keep **all of the tree's leaves at the same depth**. The next lesson takes up 2-3 trees, which build on this idea.