What is an AVL Tree?
Named after its Soviet inventors Georgy Adelson-Velsky and Evgenii Landis, an AVL Tree is a self-balancing binary search tree (BST). It rigorously maintains balance by ensuring that for every single node, the difference between the heights of its left and right subtrees (known as the balance factor) is never more than 1. This self-balancing property guarantees that search, insertion, and deletion operations maintain a worst-case time complexity of O(log n), preventing the tree from degenerating into a linear linked list.
How the AVL Tree Balancing Algorithm Works
Every time a node is inserted or deleted, the AVL tree algorithm traces back up to the root, checking the balance factor (BF) of each ancestor node. The balance factor is calculated as:
If the balance factor of any node becomes greater than 1 or less than -1, the subtree rooted at that node is considered unbalanced. The algorithm immediately performs specific AVL tree rotations to restore balance.
The Four Types of AVL Tree Rotations
Depending on where the imbalance is located, there are four distinct structural rotations used to rebalance the tree:
1. Single Right Rotation (LL Rotation)
Applied when an insertion occurs in the left subtree of the left child of an unbalanced node. Rotating the node to the right restores balance.
2. Single Left Rotation (RR Rotation)
Applied when an insertion occurs in the right subtree of the right child of an unbalanced node. Rotating the node to the left restores balance.
3. Double Left-Right Rotation (LR Rotation)
Applied when an insertion occurs in the right subtree of the left child. It requires a preliminary left rotation on the left child, followed by a right rotation on the unbalanced parent node.
4. Double Right-Left Rotation (RL Rotation)
Applied when an insertion occurs in the left subtree of the right child. It requires a preliminary right rotation on the right child, followed by a left rotation on the unbalanced parent node.
Step-by-Step AVL Tree Insertion and Balancing
During an AVL tree insertion:
- The algorithm inserts the new key exactly like a standard binary search tree.
- It updates the height value of the newly inserted node and traverses back up to the root.
- For each ancestor, it recalculates the Balance Factor.
- If a node's Balance Factor is violated ($|BF| > 1$), it identifies the rotation type (LL, RR, LR, or RL) and shifts the subtrees to restore stable height-balance.
AVL Tree vs. Red-Black Tree: Key Differences
Both AVL Trees and Red-Black Trees are popular self-balancing binary search trees, but they offer distinct trade-offs:
| Feature | AVL Tree | Red-Black Tree |
|---|---|---|
| Balancing Strictness | Strict height balance ($|BF| \le 1$) | Relaxed coloring balance |
| Search Performance | Faster (Strict balance yields shorter paths) | Slightly slower search lookups |
| Insert / Delete Speed | Slower (requires more rotations to balance) | Faster (requires fewer rotations on average) |
| Memory Overhead | Higher (stores node height values as integers) | Lower (stores a single color bit per node) |
| Best Suited For | Read-heavy applications (e.g., lookups) | Write-heavy applications (frequent updates) |