AVL Rotation Lab
Start with an LL, RR, LR, or RL example, or generate a larger AVL tree. Step through search, insertion, or deletion; inspect balance factors bottom-up and watch each single rotation preserve the inorder sequence. Double rotations take two separate steps.
Begin prepares an operation. Step advances a comparison, structural update, balance check, or rotation. Reset replays the same operation. Build AVL and Generate random AVL create complete starting trees.
Current action
Inorder sequence
AVL tree
Height of an empty subtree is −1; height of a leaf is 0 (height counts edges). BF = height(left) − height(right). Heights and balance factors are recomputed for each displayed state, including temporary imbalance.
Rotation reference
| Imbalance | Condition at z | Repair |
|---|---|---|
| LL | BF(z) > 1; BF(left) ≥ 0 | Right rotation at z |
| RR | BF(z) < −1; BF(right) ≤ 0 | Left rotation at z |
| LR | BF(z) > 1; BF(left) < 0 | Left at left child, then right at z |
| RL | BF(z) < −1; BF(right) > 0 | Right at right child, then left at z |
Repair the lowest unbalanced node first. A zero child balance factor can occur during deletion and uses a single rotation. Deletion may require repairs at several ancestors. Duplicate keys are excluded in this lab.