Balanced Trees & AVL: Keeping Search Trees Fast
A balanced tree is a binary search tree that actively keeps its height near log n so operations stay O(log n). The AVL tree was the first self-balancing BST: after every insert or delete it checks each node’s balance factor and performs rotations to restore balance. This page explains why balance matters and how rotations work, conceptually and in code.
We build on BST operations.
Why balance matters
A plain BST is only fast when it’s bushy. Insert values in sorted order — 1, 2, 3, 4, 5 — and you get a degenerate tree that’s really a linked list:
(1)
\
(2)
\
(3)
\
(4)Now search, insert, and delete are O(n), not O(log n). Self-balancing trees prevent this by reshaping themselves so the height stays O(log n) regardless of insertion order.
The balance factor
An AVL node is balanced when the heights of its left and right subtrees differ by at most 1. We define:
balanceFactor(node) = height(node.left) - height(node.right)An AVL tree keeps every node’s balance factor in {-1, 0, +1}. If an insert/delete pushes a factor to +2 or -2, a rotation fixes it.
Rotations: the core operation
A rotation locally restructures three nodes to reduce height while preserving the BST ordering. There are two primitives — right rotation and left rotation — and the two double rotations are just combinations.
A right rotation around y (heavy on the left) promotes its left child x:
y x
/ \ / \
x T3 ---> T1 y
/ \ / \
T1 T2 T2 T3Notice the ordering still holds: T1 < x < T2 < y < T3 before and after.
// Assume each TreeNode also stores an int height, default 1.
int height(TreeNode* n) { return n ? n->height : 0; }
void update(TreeNode* n) {
n->height = 1 + std::max(height(n->left), height(n->right));
}
TreeNode* rotateRight(TreeNode* y) {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
update(y);
update(x);
return x; // new subtree root
}// Assume each TreeNode also stores an int height, default 1.
int height(TreeNode n) { return n == null ? 0 : n.height; }
void update(TreeNode n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}
TreeNode rotateRight(TreeNode y) {
TreeNode x = y.left;
TreeNode T2 = x.right;
x.right = y;
y.left = T2;
update(y);
update(x);
return x; // new subtree root
}// Assume each TreeNode also stores a height field, default 1.
const height = n => (n ? n.height : 0);
const update = n => { n.height = 1 + Math.max(height(n.left), height(n.right)); };
function rotateRight(y) {
const x = y.left;
const T2 = x.right;
x.right = y;
y.left = T2;
update(y);
update(x);
return x; // new subtree root
}# Assume each TreeNode also stores a height attribute, default 1.
def height(n):
return n.height if n else 0
def update(n):
n.height = 1 + max(height(n.left), height(n.right))
def rotate_right(y):
x = y.left
t2 = x.right
x.right = y
y.left = t2
update(y)
update(x)
return x # new subtree rootA left rotation is the mirror image (swap every left/right).
The four imbalance cases
After inserting into the subtree of an unbalanced node, identify the shape and apply the matching fix:
- Left-Left: rotate right.
- Right-Right: rotate left.
- Left-Right: rotate the left child left, then rotate right.
- Right-Left: rotate the right child right, then rotate left.
Here is the rebalance decision sketch that ties it together:
int balanceFactor(TreeNode* n) { return n ? height(n->left) - height(n->right) : 0; }
TreeNode* rebalance(TreeNode* node) {
update(node);
int bf = balanceFactor(node);
if (bf > 1) { // left heavy
if (balanceFactor(node->left) < 0) // Left-Right
node->left = rotateLeft(node->left);
return rotateRight(node); // Left-Left
}
if (bf < -1) { // right heavy
if (balanceFactor(node->right) > 0) // Right-Left
node->right = rotateRight(node->right);
return rotateLeft(node); // Right-Right
}
return node; // already balanced
}int balanceFactor(TreeNode n) { return n == null ? 0 : height(n.left) - height(n.right); }
TreeNode rebalance(TreeNode node) {
update(node);
int bf = balanceFactor(node);
if (bf > 1) { // left heavy
if (balanceFactor(node.left) < 0) // Left-Right
node.left = rotateLeft(node.left);
return rotateRight(node); // Left-Left
}
if (bf < -1) { // right heavy
if (balanceFactor(node.right) > 0) // Right-Left
node.right = rotateRight(node.right);
return rotateLeft(node); // Right-Right
}
return node; // already balanced
}const balanceFactor = n => (n ? height(n.left) - height(n.right) : 0);
function rebalance(node) {
update(node);
const bf = balanceFactor(node);
if (bf > 1) { // left heavy
if (balanceFactor(node.left) < 0) // Left-Right
node.left = rotateLeft(node.left);
return rotateRight(node); // Left-Left
}
if (bf < -1) { // right heavy
if (balanceFactor(node.right) > 0) // Right-Left
node.right = rotateRight(node.right);
return rotateLeft(node); // Right-Right
}
return node; // already balanced
}def balance_factor(n):
return height(n.left) - height(n.right) if n else 0
def rebalance(node):
update(node)
bf = balance_factor(node)
if bf > 1: # left heavy
if balance_factor(node.left) < 0: # Left-Right
node.left = rotate_left(node.left)
return rotate_right(node) # Left-Left
if bf < -1: # right heavy
if balance_factor(node.right) > 0: # Right-Left
node.right = rotate_right(node.right)
return rotate_left(node) # Right-Right
return node # already balancedYou call rebalance on the way back up after a recursive insert or delete.
For beginners: A rotation never breaks the BST ordering — it only changes who is the parent. Each rotation is O(1), and at most a couple are needed per update.
Complexity
| Operation | AVL tree | Plain BST (worst) |
|---|---|---|
| Search / insert / delete | O(log n) | O(n) |
| Rotation | O(1) | — |
Rotations add a constant factor to each update in exchange for a guaranteed O(log n) height.
Going deeper: Red-black trees balance more loosely (fewer rotations on updates) and back
std::map, Java’sTreeMap, and many language libraries. See the self-balancing BSTs overview.
Next steps
Measure tree shape with tree height & depth, or test your understanding on the tree exercises.