Advanced·2 min read
AVL Trees
Self-balancing BSTs with guaranteed O(log n) operations through rotations.
AVL Trees
An AVL tree is a self-balancing BST where the balance factor (height difference of subtrees) of every node is -1, 0, or 1.
Why AVL?
A regular BST can degrade to O(n) when sorted input is inserted:
``
Insert 1,2,3,4,5 → becomes a linked list
1
\
2
\
3 ← Height = 4, effectively a linked list
\
4
\
5
`
AVL fixes this with rotations to keep height at O(log n).
Balance Factor
BF(node) = height(left) - height(right)
Must be {-1, 0, 1} for every node.
Four Rotation Cases
Header Case Imbalance Fix
Header Left-Left (LL) Left child is left-heavy Right rotation Right-Right (RR) Right child is right-heavy Left rotation Left-Right (LR) Left child is right-heavy Left rotate child, then right rotate Right-Left (RL) Right child is left-heavy Right rotate child, then left rotate
Right Rotation (LL case)
`
y x
/ \ / \
x C → A y
/ \ / \
A B B C
``
Insertion
Insert like a normal BST, then walk back up checking balance factors. Apply the appropriate rotation when balance is violated.
All operations guaranteed O(log n).Code Example
python
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVLTree:
def height(self, node):
return node.height if node else 0
def balance_factor(self, node):
return self.height(node.left) - self.height(node.right)
def update_height(self, node):
node.height = 1 + max(self.height(node.left), self.height(node.right))
def rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
self.update_height(y)
self.update_height(x)
return x
def rotate_left(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
self.update_height(x)
self.update_height(y)
return y
def insert(self, node, val):
if not node:
return AVLNode(val)
if val < node.val:
node.left = self.insert(node.left, val)
elif val > node.val:
node.right = self.insert(node.right, val)
else:
return node
self.update_height(node)
bf = self.balance_factor(node)
if bf > 1 and val < node.left.val:
return self.rotate_right(node)
if bf < -1 and val > node.right.val:
return self.rotate_left(node)
if bf > 1 and val > node.left.val:
node.left = self.rotate_left(node.left)
return self.rotate_right(node)
if bf < -1 and val < node.right.val:
node.right = self.rotate_right(node.right)
return self.rotate_left(node)
return node
def inorder(self, node, result):
if node:
self.inorder(node.left, result)
result.append(node.val)
self.inorder(node.right, result)
avl = AVLTree()
root = None
for v in [10, 20, 30, 40, 50, 25]:
root = avl.insert(root, v)
result = []
avl.inorder(root, result)
print("AVL In-order:", result)
print(f"Tree height: {avl.height(root)} (vs 5 for unbalanced)")Practice Problems
- 01Implement AVL tree deletion with all rotation cases
- 02Check if a given binary tree is balanced
- 03Find the diameter of a binary tree