AVL Trees — Rotations Restore Balance Factor

AVL nodes track balance factor ∈ {{-1,0,1}}; insert/delete may trigger rotations to restore it.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def rotate_right(y: TreeNode) -> TreeNode:
    """Classic right rotation (promote y.left)."""
    x = y.left  # type: ignore
    t2 = x.right  # type: ignore
    x.right = y
    y.left = t2
    return x

# toy skew left then fix
root = TreeNode(3, TreeNode(2, TreeNode(1)))
root = rotate_right(root)
print(root.val, root.right.val if root.right else None)

Key takeaways

• Know single vs double rotation cases (LL, RR, LR, RL) on paper before coding full insert.
• AVL height ≤ ~1.44 log2(n+2)—tighter than many BSTs.
• Practice tracing heights after each rotation.