AVL Trees — Self-Balancing BST Visualized
Learn AVL trees — balance factor, rotations (LL/RR/LR/RL), guaranteed O(log n) search, interactive visualizer and database index examples.
Introduction
AVL trees are self-balancing BSTs — after every insert or delete, rotations restore balance so height stays O(log n). Guaranteed fast search, unlike plain BSTs that can degenerate.
Quick index
1. Balance factor
balanceFactor(node) = height(left) − height(right)AVL invariant: balance factor is always −1, 0, or 1 for every node. If |bf| > 1 → rotate.
2. Interactive visualizer
AVL Trees — Self-Balancing BST
Automatically rotate on insert/delete to keep height O(log n) — guaranteed fast search.
Balance factor = height(left) − height(right). |bf| > 1 → rotate.
Balance factor
function balanceFactor(node) {
return height(node.left) - height(node.right)
}
// |balanceFactor| > 1 → tree is unbalancedNode 3 has bf=+2 (left-heavy) — needs rotation.
Balance
|bf| ≤ 1
Search
O(log n)
Rotations
4 cases
3. Full implementation
class AVLNode {
constructor(value) {
this.value = value
this.left = null
this.right = null
this.height = 1
}
}
function nodeHeight(n) {
return n ? n.height : 0
}
function balanceFactor(n) {
return n ? nodeHeight(n.left) - nodeHeight(n.right) : 0
}
function updateHeight(n) {
n.height = 1 + Math.max(nodeHeight(n.left), nodeHeight(n.right))
}
function rotateRight(y) {
const x = y.left
y.left = x.right
x.right = y
updateHeight(y)
updateHeight(x)
return x
}
function rotateLeft(x) {
const y = x.right
x.right = y.left
y.left = x
updateHeight(x)
updateHeight(y)
return y
}
function avlInsert(node, value) {
if (!node) return new AVLNode(value)
if (value < node.value) node.left = avlInsert(node.left, value)
else if (value > node.value) node.right = avlInsert(node.right, value)
else return node
updateHeight(node)
const bf = balanceFactor(node)
// LL
if (bf > 1 && value < node.left.value) return rotateRight(node)
// RR
if (bf < -1 && value > node.right.value) return rotateLeft(node)
// LR
if (bf > 1 && value > node.left.value) {
node.left = rotateLeft(node.left)
return rotateRight(node)
}
// RL
if (bf < -1 && value < node.right.value) {
node.right = rotateRight(node.right)
return rotateLeft(node)
}
return node
}Function calls with output
// ── Demo calls — output shown on the right ──
let root = null
root = avlInsert(root, 1) // → root: 1
root = avlInsert(root, 2) // → root: 1, right: 2
root = avlInsert(root, 3) // → LL rotation! root: 2, left: 1, right: 3
balanceFactor(root) // → 0
nodeHeight(root) // → 24. Complexity
| Operation | BST (worst) | AVL (guaranteed) |
|---|---|---|
| Search | O(n) | O(log n) |
| Insert | O(n) | O(log n) |
| Delete | O(n) | O(log n) |
5. Real-life examples
| Scenario | AVL role |
|---|---|
| Database B-tree indexes | Balanced tree for O(log n) row lookup |
| In-memory sorted maps | C++ std::map (Red-Black variant) |
| File system indexing | Balanced directory entry lookup |
| Network routing tables | Longest-prefix match trees |
Database index (balanced)
AVL/Red-Black trees in PostgreSQL indexes — guaranteed O(log n) lookups.
1M rows indexed
AVL height ≈ 20
Lookup: ~20 comparisons
Balanced tree keeps height logarithmic — not 1M comparisons.
Real-world implementation
// Database B-tree / AVL index (conceptual)
function indexLookup(indexRoot, key) {
let node = indexRoot
while (node) {
if (key === node.key) return node.rowId
node = key < node.key ? node.left : node.right
}
return null
}Full working code for the scenario above.
Function calls with output
| // ── Function calls with output ── | |
| indexLookup(root, 482910) | → rowId 9182 |
Side output shows return value after each call — step through to trace execution.
Summary
AVL trees guarantee O(log n) via automatic rotations — the fix for BST's worst-case chain problem.
Next reads: Binary Search Trees · Tree Array Implementation
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime