Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About An AVL tree is a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis
An AVL tree is a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis.
It enforces the invariant that for every node, the heights of its left and right subtrees differ by at most 1 (the balance factor ∈ {-1, 0, 1}).
This guarantees the tree height stays O(log n), so all BST operations run in O(log n).
How It Works
After every insertion or deletion, the algorithm walks back up the path to the root and recomputes balance factors.
If any node becomes unbalanced (factor +2 or -2), a rotation fixes it: left-left → right rotation, right-right → left rotation, left-right → left-right double rotation, right-left → right-left double rotation.
A single rotation is O(1) and a fix-up visits O(log n) ancestors, keeping insertion/deletion at O(log n).
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Search | O(log n) | O(1) |
| Insert | O(log n) | O(log n) recursion |
| Delete | O(log n) | O(log n) recursion |
| Rotation (rebalance) | O(1) | O(1) |
| Height bound | 1.44 · log₂(n+2) | — |
Best Use Cases
- In-memory sorted dictionaries where worst-case O(log n) is required (no skip-list slack)
- Database and filesystem indexes that need strict height guarantees
- Scenarios with far more lookups than insertions
- Range queries with guaranteed balanced structure
Worked Example
Insert [50, 30, 70, 20, 40, 10, 25] and watch the rebalancing
Input: insert in order: 50, 30, 70, 20, 40, 10, 25; then search 25- 1 Insert 50, 30, 70, 20, 40 — the tree is balanced so far.
- 2 Insert 10: it becomes the left child of 20, making node 30 unbalanced (left-left case).
- 3 A right rotation at 30 restores balance: 20 moves up, 30 moves right.
- 4 Insert 25: it lands as the right child of 20, creating a left-right imbalance at 50.
- 5 A double rotation (left on 20, then right on 50) fixes it — 25 ends up as the new root.
- 6 Every node now has a balance factor in {-1, 0, 1}. Search for 25 walks the tree to the root.
Pseudocode
function insert(node, value):
if node is null: return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
updateHeight(node)
balance = height(node.left) - height(node.right)
if balance > 1: # left heavy
if value < node.left.value: return rotateRight(node)
else: node.left = rotateLeft(node.left); return rotateRight(node)
if balance < -1: # right heavy
if value > node.right.value: return rotateLeft(node)
else: node.right = rotateRight(node.right); return rotateLeft(node)
return node function rotateRight(y):
x = y.left
y.left = x.right
x.right = y
updateHeight(y); updateHeight(x)
return x
function rotateLeft(x):
y = x.right
x.right = y.left
y.left = x
updateHeight(x); updateHeight(y)
return y Insert Sequence
Watch inserts trigger rotations that keep every node's balance factor within -1..1.