AVL Trees
Master self-balancing binary search trees
⚖️ What are AVL Trees?
AVL Trees are self-balancing binary search trees where the height difference between left and right subtrees is at most 1 for every node. Named after Adelson-Velsky and Landis, they guarantee O(log n) performance for all operations.
# AVL Tree maintains balance factor
# Balance Factor = height(left) - height(right)
# Must be -1, 0, or 1 for all nodes
class AVLNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1 # Height of node
O(log n)
Guaranteed
±1
Balance Factor
Auto
Balancing
AVL Tree Properties
Height Balanced
Balance factor ∈ {-1, 0, 1}
Self-balancing
Height tracking
Rotations
Automatic rebalancing operations
Left rotation
Right rotation
BST Property
Maintains search tree ordering
Left < Root < Right
Sorted traversal
Guaranteed Performance
O(log n) worst-case operations
Search
Insert/Delete
Lesson 1: Understanding AVL Tree Structure
Let's start with the basic AVL tree node and helper functions:
AVL Tree Example (Balanced)
10 (h=3, bf=0)
/ \
5 15 (h=2, bf=1)
/ \ /
3 7 12 (h=1, bf=0)
/ / \
1 6 8
h = height, bf = balance factor
AVL Tree Node Structure
class AVLNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def get_height(self, node):
return 0 if node is None else node.height
def get_balance_factor(self, node):
if node is None:
return 0
return self.get_height(node.left) - self.get_height(node.right)
# Quick test
avl = AVLTree()
root = AVLNode(10)
print(f"Height: {avl.get_height(root)}") # Output: 1
print(f"Balance: {avl.get_balance_factor(root)}") # Output: 0
Lesson 2: AVL Tree Rotations
Four rotation types maintain balance:
Right Rotation (LL Case)
def right_rotate(self, y):
"""Right rotation: y becomes right child of x"""
x = y.left
y.left = x.right
x.right = y
# Update heights
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
return x # New root
def left_rotate(self, x):
"""Left rotation: x becomes left child of y"""
y = x.right
x.right = y.left
y.left = x
# Update heights
x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
return y # New root
Lesson 3: AVL Tree Insertion
Insert and rebalance automatically:
AVL Insertion
def insert(self, data):
self.root = self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
# Step 1: Normal BST insertion
if node is None:
return AVLNode(data)
if data < node.data:
node.left = self._insert_recursive(node.left, data)
elif data > node.data:
node.right = self._insert_recursive(node.right, data)
else:
return node # No duplicates
# Step 2: Update height and balance
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
balance = self.get_balance_factor(node)
# Step 3: Perform rotations if needed
# LL Case
if balance > 1 and data < node.left.data:
return self.right_rotate(node)
# RR Case
if balance < -1 and data > node.right.data:
return self.left_rotate(node)
# LR Case
if balance > 1 and data > node.left.data:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
# RL Case
if balance < -1 and data < node.right.data:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
# Test insertion
avl = AVLTree()
for val in [10, 20, 30, 40, 50, 25]:
avl.insert(val)
print("AVL tree created with automatic balancing!")
Lesson 4: AVL Tree Deletion
Delete and maintain balance:
AVL Deletion
def delete(self, data):
self.root = self._delete_recursive(self.root, data)
def _delete_recursive(self, node, data):
# Step 1: Normal BST deletion
if node is None:
return node
if data < node.data:
node.left = self._delete_recursive(node.left, data)
elif data > node.data:
node.right = self._delete_recursive(node.right, data)
else:
# Node to delete found
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
# Two children: get successor
successor = self._find_min(node.right)
node.data = successor.data
node.right = self._delete_recursive(node.right, successor.data)
# Step 2: Update height and rebalance
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
balance = self.get_balance_factor(node)
# Rebalance if needed (same rotation logic as insertion)
if balance > 1:
if self.get_balance_factor(node.left) >= 0:
return self.right_rotate(node)
else:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
if balance < -1:
if self.get_balance_factor(node.right) <= 0:
return self.left_rotate(node)
else:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
AVL Trees vs Regular BST
Time Complexity
- AVL: O(log n) guaranteed
- BST: O(n) worst case
- Space: O(n) both
Use Cases
- Frequent searches
- Database indexing
- Memory-constrained systems
- Predictable performance
Advantages
- Guaranteed O(log n)
- Self-balancing
- Better than Red-Black for lookups
- Height-balanced
Disadvantages
- More rotations than Red-Black
- Extra height storage
- Complex implementation
- Slower insertions/deletions