Data Structures · Algorithms
Learn With Examples
A regular binary search tree can degrade into a linked list — making every search O(n) instead of O(log n). AVL trees fix this with automatic rotations that keep the tree perfectly balanced after every insert and delete. This guide walks you through the balance factor, all four rotation types, and lets you build and balance an AVL tree interactively in real time.
Contents
- The problem with unbalanced BSTs
- What is an AVL tree?
- The balance factor — the key metric
- The four rotations — how AVL rebalances
- Interactive rotation visualiser
- Live AVL tree builder
- Insertion algorithm — step by step
- Time and space complexity
- AVL vs Red-Black trees vs BST
- Real-world uses of AVL trees
- Python implementation
- Knowledge quiz
Section 01
The Problem with Unbalanced BSTs
A Binary Search Tree (BST) is a beautiful data structure: every node’s left child is smaller, every right child is larger. Searching is O(log n) — you eliminate half the tree at each step. In theory.
In practice, the order you insert values determines the shape of the tree. Insert values in sorted order — 1, 2, 3, 4, 5 — and you get this:
That is not a tree — it is a linked list. Searching for 5 now requires visiting every single node. Your O(log n) search has degraded to O(n). The whole advantage of a BST is gone.
⚠️ The Real-World Risk
Any application that inserts data in sorted or near-sorted order — timestamps, auto-incrementing IDs, alphabetical names — is at risk of BST degeneration. This is why production databases and language runtimes use self-balancing trees, not plain BSTs.
Section 02
What is an AVL Tree?
An AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It maintains all the BST properties — left child smaller, right child larger — but adds one additional constraint:
After every insertion or deletion, the AVL tree checks this constraint at every affected node. If any node becomes unbalanced, it performs one or two rotations — local restructuring operations — to restore balance. The tree never needs to be rebuilt from scratch.
Height of a Node
The number of edges on the longest path from that node to a leaf. A leaf node has height 0. A null pointer has height −1.
Balance Factor
BF = height(left) − height(right). In a valid AVL tree, every node’s BF is −1, 0, or +1. Any other value triggers a rotation.
Rotations
Local restructuring of 2–3 nodes that restores balance without violating the BST property. There are four types: LL, RR, LR, RL.
Guaranteed Height
An AVL tree with n nodes has height at most 1.44 × log₂(n). A degenerate BST has height n. This gap is enormous for large n.
Section 03
The Balance Factor — The Key Metric
Every node in an AVL tree stores a balance factor (BF) — the difference between the height of its left subtree and the height of its right subtree.
| Balance Factor | Meaning | AVL Valid? | Action |
|---|---|---|---|
| BF = −2 | Right subtree is 2 taller | Invalid | Rotate left (RR or RL) |
| BF = −1 | Right subtree is 1 taller | Valid | No action needed |
| BF = 0 | Both subtrees equal height | Valid — perfect | No action needed |
| BF = +1 | Left subtree is 1 taller | Valid | No action needed |
| BF = +2 | Left subtree is 2 taller | Invalid | Rotate right (LL or LR) |
📌 Stored or Computed?
In most implementations the balance factor (or simply the height) is stored at each node and updated during insertions and deletions. This makes it O(1) to check — no need to traverse the subtree to measure height every time.
class AVLNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 # new node starts at height 1 def get_height(node): return node.height if node else 0 def get_balance(node): return get_height(node.left) - get_height(node.right) if node else 0 def update_height(node): node.height = 1 + max(get_height(node.left), get_height(node.right))
Section 04
The Four Rotations — How AVL Rebalances
When the balance factor at a node becomes ±2, the AVL tree performs a rotation. There are four types, each handling a different pattern of imbalance. They all share one beautiful property: they restore balance while preserving the BST ordering property.
| Case | When it happens | BF of unbalanced node | BF of child | Fix |
|---|---|---|---|---|
| LL (Left-Left) | Insertion in left subtree of left child | +2 | ≥ 0 | Single right rotation |
| RR (Right-Right) | Insertion in right subtree of right child | −2 | ≤ 0 | Single left rotation |
| LR (Left-Right) | Insertion in right subtree of left child | +2 | < 0 | Left rotate child, then right rotate node |
| RL (Right-Left) | Insertion in left subtree of right child | −2 | > 0 | Right rotate child, then left rotate node |
Right Rotation (LL case)
The unbalanced node z has BF = +2. Its left child y is taller. We rotate right around z — y takes z’s position, z becomes y’s right child.
def rotate_right(z): y = z.left # y is the left child of z T3 = y.right # T3 is the right subtree of y # Perform rotation y.right = z # z becomes the right child of y z.left = T3 # T3 moves to z's left (BST property preserved) # Update heights (z first, then y since y is now higher) update_height(z) update_height(y) return y # y is the new root of this subtree
Left Rotation (RR case)
def rotate_left(z): y = z.right # y is the right child of z T2 = y.left # T2 is the left subtree of y # Perform rotation y.left = z # z becomes the left child of y z.right = T2 # T2 moves to z's right update_height(z) update_height(y) return y # y is the new root
🔄 Double Rotations
LR and RL cases require two rotations. For LR: first rotate the left child leftward (turning LR into LL), then rotate the unbalanced node rightward. For RL: first rotate the right child rightward (turning RL into RR), then rotate the unbalanced node leftward. After a double rotation the tree is always balanced.
Section 05
Interactive Rotation Visualiser
Click any rotation to see the before and after states side by side. Notice how the BST ordering property is preserved — an in-order traversal of both trees gives the same sequence.
Section 06
Live AVL Tree Builder
Insert and delete values to build your own AVL tree. The tree rebalances automatically after every operation. Balance factors are shown inside each node — green means balanced, red means a rotation just happened.
Section 07
Insertion Algorithm — Step by Step
AVL insertion combines standard BST insertion with a recursive rebalancing pass back up to the root.
Insert like a normal BST
Recursively traverse the tree comparing the new key with each node. Go left if smaller, right if larger. Insert at the correct null position.
Update heights on the way back up
As the recursion unwinds, update the height of each ancestor node: height = 1 + max(height(left), height(right)).
Check balance factor at each ancestor
Compute BF = height(left) − height(right) at each node. If |BF| ≤ 1, the node is balanced. Continue up the tree.
Identify the case and rotate if BF = ±2
Determine which of the four cases applies (LL, RR, LR, RL) by checking the balance factor of the child. Perform the appropriate single or double rotation.
Continue checking upward
After a rotation, continue checking balance factors up to the root. In practice at most one rotation is needed per insertion (but deletion may need O(log n) rotations).
def insert(node, key): # Step 1: Standard BST insertion if not node: return AVLNode(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) else: return node # duplicate key — ignore # Step 2: Update height update_height(node) # Step 3: Get balance factor bf = get_balance(node) # Step 4: Determine case and rotate # LL Case if bf > 1 and key < node.left.key: return rotate_right(node) # RR Case if bf < -1 and key > node.right.key: return rotate_left(node) # LR Case if bf > 1 and key > node.left.key: node.left = rotate_left(node.left) return rotate_right(node) # RL Case if bf < -1 and key < node.right.key: node.right = rotate_right(node.right) return rotate_left(node) return node # node is balanced — no rotation needed
Section 08
Time and Space Complexity
| Operation | Average | Worst Case | Why |
|---|---|---|---|
| Search | O(log n) | O(log n) | Height is always ≤ 1.44 log₂(n) — guaranteed |
| Insert | O(log n) | O(log n) | BST insert + at most 2 rotations + height updates up to root |
| Delete | O(log n) | O(log n) | BST delete + up to O(log n) rotations on the path back to root |
| Space | O(n) | O(n) | One node per element; each stores key, left, right, height |
✅ The Guarantee that Matters
The key advantage of AVL trees over plain BSTs is that all operations are O(log n) in the worst case — guaranteed, regardless of insertion order. A plain BST can degrade to O(n). The cost is slightly higher constant factors due to rotation bookkeeping.
Section 09
AVL vs Red-Black Trees vs Plain BST
| Property | Plain BST | AVL Tree | Red-Black Tree |
|---|---|---|---|
| Search worst case | O(n) | O(log n) | O(log n) |
| Insert worst case | O(n) | O(log n) | O(log n) |
| Rotations per insert | 0 | At most 2 | At most 2 |
| Rotations per delete | 0 | O(log n) | At most 3 |
| Balance strictness | None | Strict (BF ≤ 1) | Loose (height ≤ 2 log n) |
| Search speed | Varies | Faster (shorter tree) | Slightly slower |
| Insert/Delete speed | Varies | Slightly slower | Faster |
| Best use case | Static data | Read-heavy workloads | Write-heavy workloads |
| Used in | Simple lookups | Databases, compilers | Linux kernel, Java TreeMap |
💡 Which to Choose?
Choose AVL trees when your workload is read-heavy — the stricter balance means a shorter tree and faster lookups. Choose Red-Black trees when your workload is write-heavy — fewer rotations on deletion makes writes cheaper. In practice, most language standard libraries use Red-Black trees (Java’s TreeMap, C++ std::map) for their balanced write performance.
Section 10
Real-World Uses of AVL Trees
| Application | How AVL trees help |
|---|---|
| Database indexes | Many database engines use AVL or similar balanced trees for in-memory indexes where read performance is critical. Guaranteed O(log n) lookup regardless of data insertion order. |
| Compilers (symbol tables) | Compilers store identifiers (variable names, functions) in AVL trees for fast O(log n) lookup during compilation. GCC historically used AVL trees. |
| Memory allocators | Some memory allocators track free memory blocks in AVL trees, enabling fast O(log n) search for a block of the right size. |
| Geometry / computational geometry | Sweep-line algorithms for intersections, polygon clipping, and spatial queries use balanced BSTs (including AVL) to maintain the event queue. |
| Network routing tables | Fast prefix lookups for IP routing can be implemented with AVL trees in software routers, giving guaranteed lookup time per packet. |
| Python’s sortedcontainers library | The SortedList, SortedDict, and SortedSet in Python’s popular sortedcontainers library use B-tree variants inspired by AVL balancing. |
Section 11
Complete Python Implementation
class AVLNode: def __init__(self, key): self.key = key; self.left = self.right = None; self.height = 1 class AVLTree: def _h(self, n): return n.height if n else 0 def _bf(self, n): return self._h(n.left) - self._h(n.right) if n else 0 def _upd(self, n): n.height = 1 + max(self._h(n.left), self._h(n.right)) def _rr(self, z): # right rotation y = z.left; z.left = y.right; y.right = z self._upd(z); self._upd(y); return y def _lr(self, z): # left rotation y = z.right; z.right = y.left; y.left = z self._upd(z); self._upd(y); return y def _balance(self, node, key): self._upd(node) bf = self._bf(node) if bf > 1: if key > node.left.key: node.left = self._lr(node.left) # LR return self._rr(node) # LL if bf < -1: if key < node.right.key: node.right = self._rr(node.right) # RL return self._lr(node) # RR return node def insert(self, root, key): if not root: return AVLNode(key) if key < root.key: root.left = self.insert(root.left, key) elif key > root.key: root.right = self.insert(root.right, key) else: return root return self._balance(root, key) def _min_node(self, n): while n.left: n = n.left return n def delete(self, root, key): if not root: return root if key < root.key: root.left = self.delete(root.left, key) elif key > root.key: root.right = self.delete(root.right, key) else: if not root.left: return root.right if not root.right: return root.left temp = self._min_node(root.right) root.key = temp.key root.right = self.delete(root.right, temp.key) return self._balance(root, root.key) def inorder(self, root): return (self.inorder(root.left) + [root.key] + self.inorder(root.right)) if root else [] # Usage tree = AVLTree() root = None for v in [10, 20, 30, 40, 50, 25]: # sorted order — would break plain BST root = tree.insert(root, v) print("Inorder:", tree.inorder(root)) # → [10, 20, 25, 30, 40, 50] print("Height:", root.height) # → 3 (not 6 as it would be unbalanced) root = tree.delete(root, 20) print("After delete:", tree.inorder(root)) # → [10, 25, 30, 40, 50]
Section 12
Knowledge Quiz
Six questions to test your AVL tree understanding.
