AVL Tree
This note is complete, reviewed, and considered stable.
An AVL Tree (Adelson-Velsky and Landis 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.
AVL Trees automatically perform rotations after insertions and deletions to maintain balance, ensuring that search, insertion, and deletion operations remain efficient.
Why Do We Need AVL Trees?
A regular BST can become skewed depending on the insertion order.
Example
Insert:
10, 20, 30, 40, 50
Resulting BST:
The tree behaves like a linked list.
Height = O(n)
Search = O(n)
Insert = O(n)
Delete = O(n)
AVL Trees prevent this degeneration by maintaining balance.
Balanced AVL Tree:
Height ≈ O(log n)
AVL Tree Properties
Every AVL Tree must satisfy:
Binary Search Tree Property
For every node:
Left Subtree < Node < Right Subtree
Example:
Balance Property
For every node:
|Height(Left Subtree) - Height(Right Subtree)| ≤ 1
Height of a Node
The height of a node is the number of edges in the longest path from that node to a leaf.
Example:
Heights:
10 → 0
20 → 1
40 → 0
30 → 2
Balance Factor
The balance factor determines whether a node is balanced.
Formula
Balance Factor = Height(Left Subtree) - Height(Right Subtree)
Possible balanced values:
-1, 0, +1
Unbalanced:
<-1 or >+1
Example
BF(30) = 0
BF(30) = +1
BF(30) = -1
BF(30) = +2
Node 30 is unbalanced.
Rotations
AVL Trees use rotations to restore balance.
There are four possible imbalance cases:
- Left-Left (LL)
- Right-Right (RR)
- Left-Right (LR)
- Right-Left (RL)
Left-Left (LL) Case
Occurs when:
Node becomes left-heavy
Insertion occurs in left subtree of left child
Example:
Insert:
30, 20, 10
Before balancing:
Balance Factor:
BF(30) = +2
Perform a Right Rotation.
After balancing:
Right Rotation
Before:
After:
Right-Right (RR) Case
Occurs when:
Node becomes right-heavy
Insertion occurs in right subtree of right child
Example:
Insert:
10, 20, 30
Before balancing:
Balance Factor:
BF(10) = -2
Perform a Left Rotation.
After balancing:
Left Rotation
Before:
After:
Left-Right (LR) Case
Occurs when:
Node becomes left-heavy
Insertion occurs in right subtree of left child
Insert:
30, 10, 20
Before balancing:
Step 1: Left Rotation on 10
Step 2: Right Rotation on 30
Right-Left (RL) Case
Occurs when:
Node becomes right-heavy
Insertion occurs in left subtree of right child
Insert:
10, 30, 20
Before balancing:
Step 1: Right Rotation on 30
Step 2: Left Rotation on 10
Summary of Rotations
| Case | Condition | Fix |
|---|---|---|
| LL | Left of Left | Right Rotation |
| RR | Right of Right | Left Rotation |
| LR | Right of Left | Left Rotation + Right Rotation |
| RL | Left of Right | Right Rotation + Left Rotation |
AVL Tree Insertion
Step 1
Insert the node exactly as in a BST.
Example:
Step 2
Move upward from the inserted node toward the root.
Update:
Height
Balance Factor
Step 3
Check for imbalance.
Balance Factor > 1
Balance Factor < -1
Step 4
Apply the appropriate rotation.
LL → Right Rotation
RR → Left Rotation
LR → Left Rotation + Right Rotation
RL → Right Rotation + Left Rotation
AVL Tree Deletion
Deletion follows normal BST deletion first.
BST Deletion Cases
Leaf Node
Delete:
20
One Child
Delete:
20
Promote 10.
Two Children
Replace the node with:
Inorder Successor
or
Inorder Predecessor
Then delete the replacement node.
Rebalancing After Deletion
Unlike insertion, deletion may cause multiple ancestors to become unbalanced.
Therefore:
Delete Node
Update Heights
Update Balance Factors
Rotate If Needed
Continue Toward Root
AVL Height Analysis
AVL Trees guarantee logarithmic height.
Minimum number of nodes required for a given height follows:
N(h) = 1 + N(h-1) + N(h-2)
This recurrence is similar to Fibonacci numbers.
Therefore:
Height = O(log n)
More precisely:
Height ≤ 1.44 log₂(n + 2)
Time Complexity
| Operation | Complexity |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
| Find Minimum | O(log n) |
| Find Maximum | O(log n) |
Space Complexity
Tree Storage:
O(n)
Extra per node:
Value
Left Pointer
Right Pointer
Height
AVL Node Structure
Node
├── value
├── left
├── right
└ ── height
Example:
AVL Tree vs BST
| Feature | BST | AVL |
|---|---|---|
| Self Balancing | No | Yes |
| Worst Height | O(n) | O(log n) |
| Search | O(n) | O(log n) |
| Insert | O(n) | O(log n) |
| Delete | O(n) | O(log n) |
| Extra Memory | No | Height Field |
AVL Tree vs Red-Black Tree
| Feature | AVL | Red-Black |
|---|---|---|
| Balancing | Strict | Relaxed |
| Search Speed | Faster | Slightly Slower |
| Rotations | More | Fewer |
| Insert/Delete | Slower | Faster |
| Use Case | Read-Heavy Systems | General-Purpose Systems |
Advantages
- Guaranteed O(log n) search.
- Prevents skewed trees.
- Faster lookups than Red-Black Trees.
- Strict balancing.
- Predictable performance.
Disadvantages
- More complex implementation.
- Additional memory for height.
- More rotations during updates.
- Insertions and deletions can be slower than Red-Black Trees.
Key Takeaways
- AVL Tree is a self-balancing Binary Search Tree.
- Every node maintains a balance factor.
- Balance Factor = Height(Left) − Height(Right).
- Allowed balance factors are -1, 0, and +1.
- Rotations restore balance after insertions and deletions.
- Four rotation cases exist: LL, RR, LR, and RL.
- AVL Trees guarantee O(log n) height.
- Search, insertion, and deletion all run in O(log n) time.