An AVL tree is a self-balancing Binary Search Tree. To keep it balanced, it uses a mathematical formula called the Balance Factor (BF) for every node.
-
Formula:
Balance Factor = Height of Left Subtree - Height of Right Subtree -
For an AVL tree to be perfectly balanced, the BF of every single node must be exactly -1, 0, or +1.
Whenever a new node is inserted or an old node is deleted, the tree's structure changes. If the Balance Factor of any node becomes 2 or -2, the tree is considered "unbalanced". To fix this imbalance and restore the tree to its valid state, we perform special structural shifts called Rotations.
2. What is the difference between Single and Double Rotations?
To fix an unbalanced AVL tree, we use either Single Rotations or Double Rotations depending on how the new node was inserted. Here is the exact difference:
| Feature | Single Rotations | Double Rotations |
| When is it used? | Used when the unbalanced nodes form a Straight Line (Linear structure). | Used when the unbalanced nodes form a Zig-Zag shape (Bent structure). |
| Number of Steps | Requires only 1 step (one movement) to balance the tree. | Requires 2 steps (two movements) to balance the tree. |
| Types |
1. LL Rotation (Left-Left) 2. RR Rotation (Right-Right) |
1. LR Rotation (Left-Right) 2. RL Rotation (Right-Left) |
| How it works? | The middle node is simply pulled up to become the new root. | First, a bottom rotation converts the zig-zag into a straight line. Then, a top rotation balances the tree. |