AVL Tree (Balanced BST)
DSA · Trees
Theory
An AVL tree is a self-balancing BST in which the heights of each node's left and right subtrees differ by at most one. After every insert or delete it checks the balance factor and fixes violations with rotations: a single left or right rotation, or a double rotation (left-right or right-left). This guarantees a height of O(log n), so search, insert and delete are always O(log n).
Why we use it
Balancing prevents the O(n) worst case of a plain BST when data arrives in sorted order.
When to use it
Use self-balancing trees when you need guaranteed O(log n) operations on ordered data; in practice you use library versions (red-black trees, B-trees) rather than writing your own.
How it works
- Insert like a BST
- Update heights on the way up
- |height(left) - height(right)| > 1? Yes: Rotate (LL, RR, LR, RL). No: Continue up.
- Tree stays balanced: O(log n)
Syntax
balance = height(left) - height(right)
balance > 1 and new key < left.val -> right rotate
balance < -1 and new key > right.val -> left rotate
LR / RL cases -> double rotation
All operations: O(log n)Example
class Node:
def __init__(self, val):
self.val, self.left, self.right, self.h = val, None, None, 1
def h(n): return n.h if n else 0
def fix(n): n.h = 1 + max(h(n.left), h(n.right))
def rotate_right(y):
x = y.left; y.left = x.right; x.right = y
fix(y); fix(x); return x
def rotate_left(x):
y = x.right; x.right = y.left; y.left = x
fix(x); fix(y); return y
def insert(n, val):
if not n: return Node(val)
if val < n.val: n.left = insert(n.left, val)
else: n.right = insert(n.right, val)
fix(n)
bal = h(n.left) - h(n.right)
if bal > 1 and val < n.left.val: return rotate_right(n)
if bal < -1 and val > n.right.val: return rotate_left(n)
if bal > 1: n.left = rotate_left(n.left); return rotate_right(n)
if bal < -1: n.right = rotate_right(n.right); return rotate_left(n)
return n
root = None
for v in range(1, 8): # sorted input would make a plain BST a chain
root = insert(root, v)
print("Root:", root.val, "| Height:", root.h, "(a plain BST would have height 7)")Key points
- Balance factor stays in -1, 0, 1
- Rotations restore balance
- Guaranteed O(log n) height
- Red-black and B-trees are related balanced trees