AVL Tree
An AVL tree is a self-balancing Binary Search Tree whose balance invariant is the strictest of any commonly-used balanced BST: at every node, the heights of the left and right subtrees differ by at most 1. The “balance factor” of a node — defined as
height(left) − height(right)— is therefore always in{−1, 0, +1}. Whenever an insertion or deletion would push some node’s balance factor outside this range, the tree is restored to balance via O(1) rotations (single or double, four cases total: LL, RR, LR, RL). The rigid balance guarantees the tree’s height stays within~1.44·log₂(n + 2)— provably optimal up to a small constant (Adelson-Velsky and Landis 1962). Search, insert, and delete are allO(log n)in the worst case, not just amortized. AVL trees were the first dynamic data structure with a logarithmic-height proof, and they remain the textbook example of “rotation-based rebalancing.” They predate (and inspired) Red-Black Trees by 17 years; AVL is more rigidly balanced (faster lookups), Red-Black is more loosely balanced (faster modifications).
1. Intuition — A BST That Refuses to Lean
An ordinary Binary Search Tree obeys an ordering invariant (every left descendant is smaller, every right descendant is larger) but says nothing about shape. Inserting keys in sorted order produces a degenerate right-leaning chain — search becomes O(n). Self-balancing BSTs add a shape invariant on top of the ordering invariant, and they enforce it by re-shaping the tree after every modification.
An AVL tree’s shape invariant is the simplest one a working programmer might invent: for every node, its left and right subtrees must have nearly equal heights (differ by at most 1). The intuition is that if every subtree is balanced “locally,” the whole tree must be balanced “globally” — and indeed the math (§5.3) confirms this: AVL trees of n nodes have height at most ~1.44·log₂(n + 2), so search, insert, and delete are all O(log n).
The mechanism for restoring balance is the rotation: a constant-time pointer reshuffling that pivots a parent and child around their shared edge. A rotation preserves the in-order traversal of the subtree (ordering invariant intact) and locally adjusts the heights (shape invariant restored). Every modification (insert or delete) walks back up from the affected leaf to the root, updating heights and performing at most O(log n) rotations along the way.
The real-world analogy: imagine a corporate org chart that has a rule “no manager has a lopsided team — at most one report can be deeper-reporting than another.” Whenever someone is hired or quits, you walk up from their position checking if anyone’s lopsidedness exceeded 1; if so, you do a small reshuffle (promote a senior, swap two reports) to restore balance. A rotation is that local reshuffle.
The cost of this strict balance is that AVL trees do more rotations on modification than Red-Black Trees. But they do fewer comparisons on lookup, because the tree is shorter on average. The classical trade-off: AVL for read-heavy workloads (databases doing many lookups per write), Red-Black for write-heavy workloads (general-purpose ordered maps).
2. The Balance Invariant — Stated Carefully
For every node v in an AVL tree:
balance_factor(v) := height(v.left) − height(v.right) ∈ {−1, 0, +1}
Where height(null) = -1 (some references use 0; the convention only shifts everything by 1) and height(v) = 1 + max(height(v.left), height(v.right)) for non-null v.
Worth pausing on the convention. With height(null) = -1:
- A leaf has
height = 0. - A node with one leaf child has
height = 1. - The empty tree has
height = -1.
This makes balance_factor symmetric (a leaf’s children are both null, both with height -1, so balance_factor = 0). Some references use height(null) = 0 and height(leaf) = 1; the analyses are equivalent up to constants.
A node is balanced if its balance factor is in {−1, 0, +1}. It is left-heavy if +1 (or +2 after an insertion temporarily violates the invariant), right-heavy if −1 (or −2).
The operations insert and delete may temporarily violate the invariant at one or more ancestors of the modified leaf; rotations restore the invariant on the walk back up to the root.
3. Tiny Worked Example — Insertion Triggering Rotations
Insert keys 10, 20, 30, 40, 50, 25 into an initially empty AVL tree.
3.1 Insert 10
10 (h=0, bf=0)
3.2 Insert 20
10 (h=1, bf=-1)
\
20 (h=0, bf=0)
Balance factors are all in {-1, 0, +1}. No rotation needed.
3.3 Insert 30 — first rotation (RR case → single left rotation)
After insertion (before rebalance):
10 (h=2, bf=-2) ← VIOLATION!
\
20 (h=1, bf=-1)
\
30 (h=0, bf=0)
Node 10 has balance factor -2. Its right child 20 has balance factor -1. This is the RR case (“right-right” — the imbalance is in 10’s right subtree’s right subtree). Resolution: single left rotation at 10.
20 (h=1, bf=0)
/ \
10 (0) 30 (0)
Single left rotation: pivot 20 up over 10. 20’s old left child (none here) becomes 10’s new right child. Tree height shrunk from 2 to 1; balance restored.
3.4 Insert 40
20 (h=2, bf=-1)
/ \
10 (0) 30 (h=1, bf=-1)
\
40 (0)
All balance factors are within {-1, 0, +1}. No rotation needed.
3.5 Insert 50 — second rotation (RR case again, deeper)
After insertion:
20 (h=3, bf=-2) ← VIOLATION!
/ \
10 (0) 30 (h=2, bf=-1)
\
40 (h=1, bf=-1)
\
50 (0)
Node 20 has balance factor -2. The imbalance is at 30 → 40 → 50 — a right-right chain. Single left rotation at 20:
30 (h=2, bf=0)
/ \
20 (1) 40 (h=1, bf=-1)
/ \
10 (0) 50 (0)
Wait, that’s not quite right. Let’s re-do carefully. The rotation is at the deepest unbalanced ancestor — node 20. After rotating:
30becomes the new root of this subtree.20becomes30’s left child.30’s old left subtree (none, since30only had a right child40) becomes20’s new right child (so20.right = null, since 30 had no left child).30’s right subtree (40 → 50) is unchanged.
Resulting tree:
30 (h=2, bf=0)
/ \
20 (h=1, bf=+1) 40 (h=1, bf=-1)
/ \
10 (h=0) 50 (h=0)
All balance factors in {-1, 0, +1}. ✓
3.6 Insert 25 — LR case (double rotation)
Insert 25 — it goes right of 20, left of 30:
30 (h=2, bf=+1)
/ \
20 (h=1, bf=0) 40 (h=1, bf=-1)
/ \ \
10 25 50
Wait — let me check balance factors. 20’s left subtree has height 0 (just 10), right subtree 0 (just 25). So bf(20) = 0. 30’s left subtree has height 1, right subtree 1. So bf(30) = 0. No violation. Hmm — that example didn’t trigger a double rotation.
Let me re-do with a clearer LR case. Reset and insert 30, 10, 20 into an initially empty tree:
After 30:
30
After 30, 10:
30 (h=1, bf=+1)
/
10 (0)
After 30, 10, 20:
30 (h=2, bf=+2) ← VIOLATION!
/
10 (h=1, bf=-1)
\
20 (0)
Balance factor of 30 is +2 (left-heavy by 2). Its left child 10 is right-heavy (bf -1). This is the LR case (“left-right” — imbalance is in 30’s left subtree’s right subtree). The LR case requires a double rotation: first a left rotation at 10 (bringing 20 up), then a right rotation at 30.
Step 1 — left rotation at 10:
30
/
20
/
10
Step 2 — right rotation at 30:
20 (h=1, bf=0)
/ \
10 30
Both balance factors are now 0. ✓ The double rotation took the “zigzag” 30 → 10 → 20 and straightened it into a balanced subtree rooted at 20.
The four rotation cases (with diagrams in §8) handle every possible imbalance after a single insert.
4. Algorithm — Rotations and the Four Cases
When an insertion (or deletion) walks back up to its grandparent (and further), at each ancestor we update the height and check the balance factor. If |bf(v)| > 1, exactly one rotation case applies based on v’s balance and its child’s balance.
4.1 The four rotation cases
Let v be the deepest ancestor of the inserted node with |bf(v)| > 1.
| Case | bf(v) | bf(child on heavier side) | Rotation |
|---|---|---|---|
| LL | +2 | left child has bf +1 (or 0 — see below) | Single right rotation at v |
| RR | -2 | right child has bf -1 (or 0) | Single left rotation at v |
| LR | +2 | left child has bf -1 | Double rotation: left at left-child, then right at v |
| RL | -2 | right child has bf +1 | Double rotation: right at right-child, then left at v |
The “or 0” cases occur during deletion (where balance factors can stay 0 after a rotation) but not during insertion — for insert, the heavier child always has the same sign as v’s balance factor (LL has bf +1 child, RR has bf -1 child).
4.2 Single rotations
A left rotation at node x (where x has a right child y):
Before: After:
x y
/ \ / \
α y x γ
/ \ / \
β γ α β
Pseudocode:
LeftRotate(x):
y := x.right
x.right := y.left
y.left := x
UpdateHeight(x)
UpdateHeight(y)
return y # new subtree root; caller relinks parent
Symmetric for right rotation. Each rotation is O(1) pointer/height work.
4.3 Double rotations
LR is “left rotation at the left child, then right rotation at v.” Equivalent to one combined operation that pivots three nodes simultaneously:
Before: After:
v y
/ \ / \
x δ x v
/ \ /\ /\
α y α β γ δ
/ \
β γ
Pseudocode:
LRRotate(v):
LeftRotate(v.left)
RightRotate(v)
Symmetric for RL.
4.4 Insert with rebalance
Insert(node, key):
if node is null:
return new Node(key, height=0)
if key < node.key:
node.left := Insert(node.left, key)
elif key > node.key:
node.right := Insert(node.right, key)
else:
return node # duplicate — no insert
UpdateHeight(node)
bf := BalanceFactor(node)
# Four cases:
if bf > 1 and key < node.left.key: # LL
return RightRotate(node)
if bf < -1 and key > node.right.key: # RR
return LeftRotate(node)
if bf > 1 and key > node.left.key: # LR
node.left := LeftRotate(node.left)
return RightRotate(node)
if bf < -1 and key < node.right.key: # RL
node.right := RightRotate(node.right)
return LeftRotate(node)
return node
Insertion does at most one rotation case (single or double) per insert — once balance is restored at the deepest unbalanced ancestor, all higher ancestors automatically have correct balance factors.
4.5 Delete with rebalance
Deletion is structurally the same as standard BST delete (find node; if 0/1 children, splice out; if 2 children, replace with in-order predecessor/successor and recurse), but on the way back up the height-update path, we may need rotations at multiple ancestors (unlike insert). At each ancestor:
- Update height.
- Check balance factor.
- If
|bf| > 1, apply the appropriate rotation case. - Continue up to the root.
The deletion’s rebalance can cascade up to O(log n) rotations total — but each is O(1), so the total cost is still O(log n).
5. Python Implementation
A complete AVL tree with insertion, height/balance maintenance, and the four rotation cases. Deletion is sketched in comments — the full implementation is mechanical but adds ~30 lines.
from dataclasses import dataclass
from typing import Optional
@dataclass
class AVLNode:
key: int
left: Optional["AVLNode"] = None
right: Optional["AVLNode"] = None
height: int = 0 # leaf has height 0; null has "height" -1 by convention
def height(node: Optional[AVLNode]) -> int:
return -1 if node is None else node.height
def update_height(node: AVLNode) -> None:
node.height = 1 + max(height(node.left), height(node.right))
def balance_factor(node: AVLNode) -> int:
return height(node.left) - height(node.right)
def rotate_right(y: AVLNode) -> AVLNode:
"""Right rotation: y's left child x becomes the new root of this subtree.
y x
/ \ / \
x T3 → T1 y
/ \ / \
T1 T2 T2 T3
"""
x = y.left
assert x is not None
T2 = x.right
x.right = y
y.left = T2
update_height(y)
update_height(x)
return x
def rotate_left(x: AVLNode) -> AVLNode:
"""Left rotation — symmetric to rotate_right."""
y = x.right
assert y is not None
T2 = y.left
y.left = x
x.right = T2
update_height(x)
update_height(y)
return y
def insert(node: Optional[AVLNode], key: int) -> AVLNode:
"""Insert `key` into the AVL tree rooted at `node`. Returns new root."""
if node is None:
return AVLNode(key=key, height=0)
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
else:
return node # duplicate — silently no-op
update_height(node)
bf = balance_factor(node)
# Case 1: LL — single right rotation
if bf > 1 and node.left is not None and key < node.left.key:
return rotate_right(node)
# Case 2: RR — single left rotation
if bf < -1 and node.right is not None and key > node.right.key:
return rotate_left(node)
# Case 3: LR — double rotation: left-rotate left child, then right-rotate self
if bf > 1 and node.left is not None and key > node.left.key:
node.left = rotate_left(node.left)
return rotate_right(node)
# Case 4: RL — double rotation: right-rotate right child, then left-rotate self
if bf < -1 and node.right is not None and key < node.right.key:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def in_order(node: Optional[AVLNode]) -> list[int]:
if node is None:
return []
return in_order(node.left) + [node.key] + in_order(node.right)
# Demo: the two worked examples from §3.
def show_height(root: Optional[AVLNode]) -> int:
return height(root)
# 30, 10, 20 → triggers LR case.
root = None
for k in [30, 10, 20]:
root = insert(root, k)
assert root is not None and root.key == 20
assert in_order(root) == [10, 20, 30]
assert show_height(root) == 1 # tree has 3 nodes in optimal balanced shape
# Sequential 1..15 — would be O(n) chain in a plain BST, but AVL keeps it O(log n).
root = None
for k in range(1, 16):
root = insert(root, k)
assert show_height(root) == 3 # height of 15-node AVL tree is exactly 3 (perfectly balanced)
assert in_order(root) == list(range(1, 16))The assert show_height(root) == 3 for n = 15 is a sanity check on the balance: a perfectly balanced binary tree with 15 nodes has height 3 (since 2^4 − 1 = 15). Inserting 1..15 into a plain BST produces a chain of height 14; AVL’s rotations keep it at 3, demonstrating the ~log₂ n height bound in action.
Deletion (sketch):
def delete(node: Optional[AVLNode], key: int) -> Optional[AVLNode]:
if node is None:
return None
if key < node.key:
node.left = delete(node.left, key)
elif key > node.key:
node.right = delete(node.right, key)
else:
# 0 or 1 child: splice out
if node.left is None or node.right is None:
return node.left if node.left is not None else node.right
# 2 children: replace with in-order successor and recurse
succ = node.right
while succ.left is not None:
succ = succ.left
node.key = succ.key
node.right = delete(node.right, succ.key)
update_height(node)
bf = balance_factor(node)
# The four cases here use balance_factor of the heavier child — see §4.5.
if bf > 1 and balance_factor(node.left) >= 0: # LL
return rotate_right(node)
if bf > 1 and balance_factor(node.left) < 0: # LR
node.left = rotate_left(node.left)
return rotate_right(node)
if bf < -1 and balance_factor(node.right) <= 0: # RR
return rotate_left(node)
if bf < -1 and balance_factor(node.right) > 0: # RL
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeThe delete rebalance differs from insert: it checks the child’s balance factor (not the inserted key’s relative position) because there’s no “newly inserted key” to compare against. The rotations may cascade up to the root — unlike insert, which terminates after one rotation case.
6. Complexity — The Logarithmic Height Proof
6.1 Per-operation costs
- Search: O(h) where h is the tree height. By §6.2, h = O(log n), so search is O(log n).
- Insert: O(log n) for the descent + O(log n) for the walk back up updating heights and applying at most one rotation case. O(log n) total.
- Delete: O(log n) for the descent + O(log n) for the walk back up updating heights and applying up to log n rotations. O(log n) total.
All bounds are worst case, not just amortized.
6.2 Height bound
Claim: an AVL tree with n nodes has height h ≤ ~1.44 · log₂(n + 2).
Proof: Let N(h) = the minimum number of nodes in an AVL tree of height h. (We want to show: if N(h) > n, then height-h tree of n nodes can’t exist.)
Base cases:
N(0) = 1— a single root with no children has height 0.N(1) = 2— root + one child has height 1.
Recurrence: a minimum-node AVL tree of height h consists of a root, a subtree of height h−1, and a subtree of height h−2 (one shorter, by exactly 1, to be minimum-node while still maintaining balance). Plus the root:
N(h) = 1 + N(h-1) + N(h-2)
This is the Fibonacci recurrence shifted by 1. Specifically, N(h) = F(h+3) − 1 where F is the standard Fibonacci sequence (F(1) = 1, F(2) = 1, F(3) = 2, ...).
Solving: Fibonacci grows as F(k) ≈ φ^k / √5 where φ = (1 + √5)/2 ≈ 1.618.
So N(h) ≈ φ^(h+3) / √5 − 1, which means n ≥ N(h) ≈ φ^h / c, giving:
h ≤ log_φ(n) + O(1) ≈ 1.4404 · log₂(n) + O(1)
The constant 1/log₂(φ) ≈ 1.4404 is the famous “AVL constant.” A perfectly balanced tree has height exactly log₂(n+1) − 1; AVL trees can be up to ~44% taller, but never more.
6.3 Comparison: how tight is AVL’s bound?
| Tree type | Worst-case height bound |
|---|---|
| Perfect binary tree | ⌊log₂(n+1)⌋ |
| AVL tree | ~1.44 · log₂(n+2) |
| Red-Black Tree | 2 · log₂(n+1) |
| Random BST | expected ~1.39 · log_e(n) ≈ 2.0 · log₂(n) |
| Worst-case BST | n − 1 |
AVL is the strictest commonly-used balance scheme (even more rigid than weight-balanced trees). Red-Black is looser (2 · log₂ n vs 1.44 · log₂ n) but does fewer rotations on insert/delete.
6.4 Rotation count
- Insert: at most 2 rotations (one rotation case, which is either single = 1 rotation or double = 2 rotations). After rebalance at the deepest unbalanced ancestor, all higher ancestors regain valid balance factors automatically.
- Delete: at most O(log n) rotations along the rebalance path (the rebalance can cascade up through every ancestor in the worst case).
These are the per-operation rotation counts. AVL is sometimes criticized for “more rotations than RB” — that’s specifically the delete cascade. Insert is the same constant in both.
6.5 Space
- Each node stores: key, two child pointers, and a height (typically
int8orint16sinceh ≤ ~64for n ≤ 2⁶⁴). - Some implementations store balance factor (a 2-bit value:
−1, 0, +1) instead of full height, saving ~6 bytes per node at the cost of slightly more bookkeeping. - Total: O(n) space.
7. Variants and Use Cases
7.1 Strictly balanced vs weight-balanced
AVL is height-balanced. Variants like weight-balanced trees (Adams 1992, used in OCaml’s Map) instead require the number of nodes in left and right subtrees to differ by at most a constant factor. Trade-offs are similar but the rotation conditions are different (more rotations on average; potentially better cache behavior because of subtree-size info kept anyway).
7.2 Augmented AVL: order statistics
Storing subtree_size at each node turns AVL into an order-statistic tree: select(k) returns the k-th smallest, rank(key) returns the key’s position. Each operation still O(log n). Used in interval trees, k-th element queries, and database indexes.
7.3 Threaded / parent-pointer AVL
Adding parent pointers makes traversal easier (in-order successor in O(1) amortized) at the cost of one pointer per node. Iterative insert/delete (no recursion stack) typically requires parent pointers.
7.4 Persistent AVL
Path-copying makes AVL persistent: each modification creates a new tree sharing structure with the old one, with O(log n) new nodes per operation. Used in functional languages (OCaml’s Map, Clojure’s sorted-map), version-controlled data structures.
7.5 Splay trees and treaps as alternatives
Splay trees (Sleator-Tarjan 1985) and treaps achieve amortized O(log n) without explicit balance information — splay trees use access-driven self-organization, treaps use random priorities. Simpler to implement than AVL but lose the worst-case guarantee.
8. Pitfalls
8.1 Forgetting to update heights on the way back up
The single most common AVL bug. After recursing into insert(node.left, key), you must update node.height before checking its balance factor. Skipping this causes the next insertion to read stale heights and conclude the tree is balanced when it isn’t.
8.2 Wrong case detection for double rotations
The four cases (LL/RR/LR/RL) are determined by comparing the inserted key (or, in delete, the heavier child’s balance factor) to the unbalanced node’s child key. A common mistake is to use node.key instead of node.left.key or node.right.key in the comparison — silently produces wrong rotations on certain key sequences.
8.3 Returning the wrong subtree root after rotation
rotate_right(y) returns the new subtree root x. The caller must reassign: parent.left = rotate_right(y). Forgetting this leaves the parent pointing at the old root — the rotated subtree becomes orphaned, the BST becomes corrupt, and the bug only surfaces on a later traversal.
8.4 Not handling null height correctly
height(null) = -1 (or 0 in the alternate convention) must be defined and used consistently. Reading node.height when node is None crashes with a NullPointerException; using 0 instead of -1 shifts every height by 1 and makes the recurrence inconsistent.
8.5 Insert vs delete rotation conditions are subtly different
For insert: case detection looks at the inserted key relative to the unbalanced node’s child (LL means “key < node.left.key”). For delete: case detection looks at the child’s balance factor (LL means “left child has bf ≥ 0”). Mixing the two recipes silently mis-rotates on delete.
8.6 Recursive stack overflow on deep trees
A recursive AVL implementation in Python uses one Python frame per tree level. AVL height is ~1.44 log₂ n, so for n = 10⁶ the recursion is ~28 deep — fine. For n = 10⁹ it’s ~44 deep — also fine. But Python’s default recursion limit is 1000; if your AVL is corrupted (and shaped like a chain), you’ll hit that limit. Iterative implementations avoid the issue.
8.7 Using AVL when a Hash Table suffices
If you don’t need ordered traversal (in-order, range query, k-th element, predecessor/successor), a Hash Table is faster (O(1) average vs O(log n)) and simpler. AVL’s win is order-aware operations: range queries, sorted iteration, predecessor/successor lookups. Reaching for AVL when a hash table fits the requirements is over-engineering.
8.8 Comparing AVL to Red-Black inappropriately
“AVL is faster than RB” or “RB is faster than AVL” — both are wrong without a workload qualifier. Empirically:
- Read-heavy: AVL wins by ~5–10% (shorter trees, fewer comparisons).
- Write-heavy with frequent deletes: RB wins by ~5–10% (fewer rebalance rotations on delete).
- Mixed workloads: roughly even.
The tree algorithms libraries pick one and live with it; the choice is rarely the bottleneck.
9. Diagrams — The Four Rotation Cases
9.1 LL case — single right rotation
Before (node z is unbalanced, bf=+2): After right rotation at z:
z y
/ \ / \
y T4 x z
/ \ / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
What this diagram shows. An AVL violation arises when an insertion into the left subtree’s left subtree of z makes z left-heavy by 2. The fix: y (the left child) pivots up to take z’s place; z becomes y’s right child; y’s old right subtree T3 becomes z’s new left subtree. The in-order traversal is preserved (T1, x, T2, y, T3, z, T4). Heights are recomputed for z and y (in that order, since y now depends on the updated z). The pivot is O(1) — just three pointer reassignments.
9.2 RR case — single left rotation
Symmetric mirror of LL. Pivots z’s right child up; z becomes its left child.
9.3 LR case — double rotation (left-then-right)
Step 1 — left rotation at y (z's left child):
z z
/ \ / \
y T4 x T4
/ \ → / \
T1 x y T3
/ \ / \
T2 T3 T1 T2
Step 2 — right rotation at z:
z x
/ \ / \
x T4 y z
/ \ → / \ / \
y T3 T1 T2 T3 T4
/ \
T1 T2
What this diagram shows. When the imbalance is zigzag (left-right or right-left), a single rotation alone can’t fix it — it would just produce a mirror-image violation. The double rotation first straightens the zigzag (step 1) into a straight line, then resolves the (now LL-shaped) imbalance with a single rotation (step 2). The end result rebalances three nodes (y, x, z) symmetrically and preserves the in-order traversal T1, y, T2, x, T3, z, T4.
9.4 RL case — double rotation (right-then-left)
Symmetric mirror of LR.
9.5 Insertion sequence triggering all four cases
The four cases all arise on the right inputs. A short stress-test sequence: insert 50, 30, 70, 20, 40, 60, 80 (all balanced, no rotations). Then insert 10 — LL case. Insert 25 after that — LR case. Insert 90 — RR. Insert 75 — RL. Each rotation case is exercised exactly once.
10. Common Interview Problems
| LC# / Source | Problem | Use of AVL |
|---|---|---|
| LC 110 | Balanced Binary Tree | Check whether a binary tree is height-balanced (AVL property). Direct application. |
| LC 1382 | Balance a Binary Search Tree | Convert any BST to a balanced one — typically via in-order + rebuild, but AVL insertion works. |
| LC 220 | Contains Duplicate III | Sliding-window + sorted set queries — AVL/RB is the canonical implementation in C++. |
| LC 729 | My Calendar I | Interval-set membership: AVL or RB tree of intervals. |
| LC 218 | The Skyline Problem | Sweep line + sorted multiset of heights — needs a balanced BST. |
| LC 315 | Count of Smaller Numbers After Self | Indexed AVL (with subtree-size) or BIT. |
| LC 327 | Count of Range Sum | AVL of prefix sums for range queries. |
| Codeforces 1093E | Intersection of Permutations | Order-statistic tree (AVL with subtree size). |
For interviews, knowing AVL exists, what its invariant is, and that all operations are O(log n) is usually sufficient. Implementing rotations live is a higher bar — typically only asked at companies with a “build a TreeMap” tradition. Even then, knowing the case structure (LL/LR/RR/RL) earns most of the points without writing the full code.
11. Open Questions
- Why exactly does AVL’s stricter balance not always translate to faster real-world lookups? Cache-friendliness of larger nodes (RB stores 1 bit per node; AVL stores 2-byte heights or 2-bit balance factors) can dominate for in-memory workloads.
- Is the
~1.44 · log₂ nAVL bound tight in the average case, or only worst case? Average-case AVL height under random insertion is empirically~1.01 · log₂ n(essentially balanced) — but I haven’t seen a clean theoretical analysis. - How does AVL compare to WAVL trees (Haeupler-Sen-Tarjan 2015), a relaxed AVL variant that bounds rotations on delete?
Resolved — the precise bound. The “1.44” is exactly c := 1/log₂(φ) ≈ 1.4404 where φ = (1+√5)/2 is the golden ratio. Wikipedia’s AVL tree article states the bound precisely as
h < c · log₂(n + 2) + b
with c = 1/log₂(φ) ≈ 1.4404 and b = (c/2)·log₂(5) − 2 ≈ −0.328, and the lower bound log₂(n+1) ≤ h. The Fibonacci recurrence N(h) = 1 + N(h-1) + N(h-2) (so N(h) = F_{h+3} − 1, equivalently “an AVL tree of height h has ≥ F_{h+2} − 1 nodes” in Wikipedia’s normalization) is the source of the φ constant: Fibonacci’s closed form F_k ≈ φ^k / √5 inverts to give h ≤ log_φ n + O(1) = (1/log₂ φ) · log₂ n + O(1). So the colloquial ”≤ 44% taller than a perfect binary tree” is mathematically tight, not a hand-wave.
12. See Also
- Binary Search Tree — the unbalanced ancestor; AVL extends BST with rotations
- Red-Black Tree — the looser-balance sibling; same O(log n) bounds, different constants
- Tree Traversals — in-order traversal of any AVL is sorted
- Binary Tree
- B-Tree — generalization to k-ary balance, used in disk-resident indexes
- Hash Table — alternative when ordering isn’t needed
- Skip List — randomized alternative with similar bounds, simpler to implement
- Big-O Notation
- SWE Interview Preparation MOC