AVL Tree
Introduction
An AVL Tree is a self-balancing Binary Search Tree (BST) in which the height difference between the left and right subtrees of every node is at most 1. If the balance factor becomes greater than 1 or less than –1 after an insertion or deletion, the tree performs rotations to restore balance.
The AVL Tree was introduced by Adelson-Velsky and Evgenii Landis in 1962. It is one of the earliest self-balancing binary search trees and provides efficient searching, insertion and deletion operations.
Why Do We Need an AVL Tree?
A normal Binary Search Tree may become skewed after inserting sorted data, causing search operations to require O(n) time. AVL Trees automatically rebalance themselves after every insertion and deletion, ensuring efficient operations.
| Binary Search Tree | AVL Tree |
|---|---|
| May become skewed. | Always height balanced. |
| Worst Case : O(n) | Worst Case : O(log n) |
| No balancing. | Automatic balancing using rotations. |
Balance Factor
The Balance Factor (BF) of a node is calculated as:
Balance Factor = Height of Left Subtree − Height of Right Subtree
| Balance Factor | Status |
|---|---|
| -1 | Balanced |
| 0 | Balanced |
| +1 | Balanced |
| Less than -1 or Greater than +1 | Unbalanced |
Types of Rotations
| Rotation | Condition |
|---|---|
| LL Rotation | Insertion in Left subtree of Left child. |
| RR Rotation | Insertion in Right subtree of Right child. |
| LR Rotation | Insertion in Right subtree of Left child. |
| RL Rotation | Insertion in Left subtree of Right child. |
Example Tree
Solved Example
Insert the values: 30, 20, 10
| Step | Operation |
|---|---|
| 1 | Insert 30 as Root. |
| 2 | Insert 20 in the Left subtree. |
| 3 | Insert 10 in the Left subtree of 20. |
| 4 | Balance Factor of 30 becomes +2. |
| 5 | Perform LL Rotation. |
Tree After Rotation
Working Principle
After every insertion or deletion, the AVL Tree computes the balance factor of all affected nodes. If any node becomes unbalanced, the appropriate rotation (LL, RR, LR or RL) is applied to restore the balance while preserving the Binary Search Tree property.
AVL Tree Insertion Algorithm
Insert(Node)
Step 1 : Insert the new node as in a Binary Search Tree.
Step 2 : Update the height of every ancestor node.
Step 3 : Calculate the Balance Factor.
Step 4 : If Balance Factor is between -1 and +1,
The tree is balanced.
Step 5 : Otherwise determine the type of imbalance.
Step 6 : Perform the required rotation.
LL Rotation
RR Rotation
LR Rotation
RL Rotation
Step 7 : Update the heights after rotation.
Step 8 : AVL Tree becomes balanced.
LL (Left-Left) Rotation
LL Rotation is required when a node is inserted into the left subtree of the left child.
| Before Rotation | After Rotation |
|---|---|
30
/
20
/
10
|
20
/ \
10 30
|
RR (Right-Right) Rotation
RR Rotation is required when a node is inserted into the right subtree of the right child.
| Before Rotation | After Rotation |
|---|---|
10
\
20
\
30
|
20
/ \
10 30
|
LR (Left-Right) Rotation
LR Rotation is required when insertion occurs in the right subtree of the left child. It is performed using two rotations.
| Step 1 | Step 2 |
|---|---|
| Left Rotation on Left Child | Right Rotation on Root |
RL (Right-Left) Rotation
RL Rotation is required when insertion occurs in the left subtree of the right child. It also requires two rotations.
| Step 1 | Step 2 |
|---|---|
| Right Rotation on Right Child | Left Rotation on Root |
Complexity Analysis
| Operation | Time Complexity | Explanation |
|---|---|---|
| Searching | O(log n) | Balanced tree height. |
| Insertion | O(log n) | May require one or two rotations. |
| Deletion | O(log n) | Tree is rebalanced after deletion. |
| Traversal | O(n) | Visits every node. |
| Space Complexity | O(n) | Storage for all nodes. |
Advantages of AVL Tree
- Maintains strict height balance.
- Provides fast searching operations.
- Guaranteed O(log n) insertion and deletion.
- Suitable for search-intensive applications.
- Reduces tree height significantly.
Limitations of AVL Tree
- Requires additional storage for the balance factor.
- Insertion and deletion are more complex.
- More rotations than Red-Black Trees.
- Not ideal for applications with frequent updates.
Applications of AVL Tree
| Application | Description |
|---|---|
| Database Indexing | Fast record searching. |
| Dictionary Applications | Efficient word searching. |
| Memory Management | Balanced allocation structures. |
| Compiler Design | Symbol tables. |
| File Systems | Efficient indexing structures. |
AVL Tree vs Red-Black Tree
| AVL Tree | Red-Black Tree |
|---|---|
| Strictly balanced. | Approximately balanced. |
| Faster searching. | Faster insertion and deletion. |
| More rotations. | Fewer rotations. |
| Uses Balance Factor. | Uses Node Colours. |
| Suitable for search-heavy systems. | Suitable for update-heavy systems. |
AVL Tree vs Binary Search Tree
| AVL Tree | Binary Search Tree |
|---|---|
| Self-balancing. | May become skewed. |
| Worst Case O(log n). | Worst Case O(n). |
| Uses rotations. | No balancing. |
| Maintains minimum height. | Height depends upon insertion order. |
Summary
An AVL Tree is a self-balancing Binary Search Tree that maintains a height difference of at most one between the left and right subtrees of every node. Whenever an imbalance occurs, one of the four rotations (LL, RR, LR or RL) is performed to restore balance. This ensures that searching, insertion and deletion operations are completed efficiently in O(log n) time.
