Introduction
An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree that guarantees O(log n) height regardless of insertion order. It achieves this by enforcing a balance invariant at every node: the balance factor, defined as height(left subtree) minus height(right subtree), must always be -1, 0, or 1. Whenever an insertion or deletion causes a node's balance factor to fall outside this range, the tree performs one or more rotations to restore balance. AVL trees are more rigidly balanced than red-black trees, which makes lookups faster but rotations somewhat more frequent — a good fit for read-heavy workloads.
Cricket analogy: An AVL tree is like a team management policy that never lets the batting order tilt too heavily toward all-rounders or specialists — the moment the balance factor drifts past 1, the selectors 'rotate' the order back, keeping the lineup efficient no matter what order players were picked in.
Structure/Syntax
class AVLNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1 # height of subtree rooted here
def get_height(node):
return node.height if node else 0
def balance_factor(node):
return get_height(node.left) - get_height(node.right) if node else 0
def right_rotate(y):
x = y.left
t2 = x.right
x.right = y
y.left = t2
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x # new subtree root
def left_rotate(x):
y = x.right
t2 = y.left
y.left = x
x.right = t2
x.height = 1 + max(get_height(x.left), get_height(x.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y # new subtree rootExplanation
After every insertion, the tree walks back up from the new node to the root, updating each ancestor's height and checking its balance factor. There are four rebalancing cases: Left-Left (LL, balance factor > 1 and new value went into the left child's left subtree) is fixed with a single right rotation; Right-Right (RR, balance factor < -1, new value into right child's right subtree) is fixed with a single left rotation; Left-Right (LR, balance factor > 1, new value into left child's right subtree) is fixed by first left-rotating the left child, then right-rotating the node; Right-Left (RL, balance factor < -1, new value into right child's left subtree) is fixed by first right-rotating the right child, then left-rotating the node.
Cricket analogy: The LL rotation case is like correcting a top-heavy batting order stacked with too many openers by promoting the vice-captain up one slot (a single rotation), while the LR case is like first repositioning a middle-order player before then promoting them — a two-step fix.
Example
def insert(node, value):
if node is None:
return AVLNode(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node # no duplicates
node.height = 1 + max(get_height(node.left), get_height(node.right))
bf = balance_factor(node)
if bf > 1 and value < node.left.value: # LL case
return right_rotate(node)
if bf < -1 and value > node.right.value: # RR case
return left_rotate(node)
if bf > 1 and value > node.left.value: # LR case
node.left = left_rotate(node.left)
return right_rotate(node)
if bf < -1 and value < node.right.value: # RL case
node.right = right_rotate(node.right)
return left_rotate(node)
return node
root = None
for v in [10, 20, 30]: # triggers an RR case -> left rotation
root = insert(root, v)
print(root.value, root.left.value, root.right.value) # 20 10 30Complexity
Because the AVL balance invariant guarantees the height is always O(log n) (proven via Fibonacci-like minimum node-count bounds), search, insertion, and deletion all run in O(log n) time in every case, not just on average. Each insertion or deletion performs at most O(log n) rotations while walking back to the root, but at most a constant number of rotations (one single or one double rotation) is needed to restore balance after a single insertion; deletions may require rebalancing at multiple ancestors on the way up, still bounded by O(log n).
Cricket analogy: Because the AVL invariant guarantees O(log n) depth in the batting order hierarchy, finding, adding, or dropping a player always takes proportionally few comparisons, and after each squad change only one or two rotations are needed to restore balance, even across a full tournament of roster shuffles.
Key Takeaways
- Balance factor = height(left) - height(right); must stay in {-1, 0, 1} at every node.
- LL case fixed by a single right rotation; RR case fixed by a single left rotation.
- LR case fixed by a left rotation on the left child, then a right rotation on the node.
- RL case fixed by a right rotation on the right child, then a left rotation on the node.
- AVL trees guarantee O(log n) height, giving O(log n) worst-case search/insert/delete.
Practice what you learned
1. In an AVL tree, what is the valid range for a node's balance factor?
2. Which rotation fixes a Left-Right (LR) imbalance in an AVL tree?
3. What is the worst-case time complexity of searching in an AVL tree with n nodes?
4. Which single rotation fixes a Right-Right (RR) imbalance case?
Was this page helpful?
You May Also Like
Binary Search Trees
A binary tree variant that maintains an ordering invariant, enabling fast search, insert, and delete operations.
Binary Trees
A hierarchical data structure where each node has at most two children, forming the foundation for many advanced tree structures.
Choosing the Right Data Structure
A practical decision framework for picking between arrays, linked lists, hash tables, trees, graphs, and heaps.