DSA course menu
Balanced Binary Search Trees: AVL Trees and Rotations
Learn how self-balancing BSTs stay fast: balance factors, left and right rotations, the four AVL imbalance cases, a working AVL insert in Python, and how red-black trees compare.
On this page
A binary search tree is O(log n) only while it is short. Insert sorted data and it degenerates into a list. A self-balancing BST fixes this automatically: after each insert or delete, it restructures itself so the height stays O(log n) whatever the input order.
The first such tree, and the easiest to understand, is the AVL tree (named after its inventors, Adelson-Velsky and Landis).
The balance factor#
Every node stores its height. Its balance factor is:
balance = height(left subtree) − height(right subtree)An AVL tree keeps every balance factor at −1, 0 or +1. When an insert makes some node reach +2 or −2, the tree performs rotations at that node to restore balance.
Rotations#
A rotation is a small, local rearrangement of three nodes that keeps the BST order but changes the shape. A right rotation at y lifts its left child x up:
y x
/ \ / \
x C ──▶ A y
/ \ / \
A B B CIn order, both shapes read A x B y C, so the BST property is preserved. A left rotation is the mirror image.
The four cases#
When a node is unbalanced, look at where the new value went:
A working AVL insert#
class Node:
def __init__(self, value):
self.value = value
self.left = self.right = None
self.height = 0
def h(node):
return node.height if node else -1
def update(node):
node.height = 1 + max(h(node.left), h(node.right))
def balance(node):
return h(node.left) - h(node.right)
def rotate_right(y):
x = y.left
y.left = x.right
x.right = y
update(y)
update(x)
return x
def rotate_left(x):
y = x.right
x.right = y.left
y.left = x
update(x)
update(y)
return y
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
update(node)
b = balance(node)
if b > 1 and value < node.left.value: # Left-Left
return rotate_right(node)
if b < -1 and value >= node.right.value: # Right-Right
return rotate_left(node)
if b > 1: # Left-Right
node.left = rotate_left(node.left)
return rotate_right(node)
if b < -1: # Right-Left
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def inorder(node):
return inorder(node.left) + [node.value] + inorder(node.right) if node else []
def show(node):
return "." if node is None else f"({show(node.left)} {node.value} {show(node.right)})"
root = None
for v in [10, 20, 30]: # sorted input: Right-Right case at 10
root = insert(root, v)
print(show(root))
root = None
for v in [30, 10, 20]: # Left-Right case at 30
root = insert(root, v)
print(show(root))((. 10 .) 20 (. 30 .))
((. 10 .) 20 (. 30 .))Both insert orders that would have made a plain BST into a chain end up as a perfectly balanced tree with 20 at the root.
Height stays logarithmic#
Inserting 1 to 1,000 in sorted order (the worst case for a plain BST):
import math
class Node:
def __init__(self, value):
self.value, self.left, self.right, self.height = value, None, None, 0
def h(n): return n.height if n else -1
def update(n): n.height = 1 + max(h(n.left), h(n.right))
def rotate_right(y):
x = y.left; y.left = x.right; x.right = y
update(y); update(x); return x
def rotate_left(x):
y = x.right; x.right = y.left; y.left = x
update(x); update(y); return y
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
update(node)
b = h(node.left) - h(node.right)
if b > 1:
if value >= node.left.value:
node.left = rotate_left(node.left)
return rotate_right(node)
if b < -1:
if value < node.right.value:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def is_balanced(node):
if node is None:
return True
return abs(h(node.left) - h(node.right)) <= 1 and is_balanced(node.left) and is_balanced(node.right)
root = None
for v in range(1, 1001):
root = insert(root, v)
print("height:", root.height, "| log2(1000) =", round(math.log2(1000), 2))
print("every node balanced:", is_balanced(root))height: 9 | log2(1000) = 9.97
every node balanced: TrueA plain BST would have height 999 here. AVL trees guarantee a height below about 1.44 log₂ n, so search, insert and delete are all O(log n) in the worst case.
Other balanced trees#
- Red-black trees colour each node red or black and allow a little more imbalance, so they need fewer rotations on insert and delete. Java's
TreeMapand C++'sstd::mapuse them. - B-trees have many keys per node and are very short and wide; databases and file systems use them so that each node fits one disk page. Database indexes are usually B-trees.
Python has no built-in balanced BST. In practice you use a dict for lookups, sorted() or bisect for ordered data, or a third-party package such as sortedcontainers.
Common mistakes#
Practice#
Practice exercise
Write sorted_to_bst(values) that builds a height-balanced BST directly from an already sorted list, without any rotations. Check that the result's height is minimal.
Show hint
The middle value becomes the root; the left half builds the left subtree and the right half the right subtree, recursively.
Show solution
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sorted_to_bst(values):
if not values:
return None
mid = len(values) // 2
return Node(values[mid], sorted_to_bst(values[:mid]), sorted_to_bst(values[mid + 1:]))
def height(node):
return -1 if node is None else 1 + max(height(node.left), height(node.right))
def inorder(node):
return inorder(node.left) + [node.value] + inorder(node.right) if node else []
root = sorted_to_bst(list(range(1, 16)))
print(root.value, height(root), inorder(root) == list(range(1, 16)))8 3 True15 values fit in a perfect tree of height 3 (1 + 2 + 4 + 8 nodes), which is the minimum possible.
Key takeaway#
Next: a different kind of tree, built for "give me the smallest", in Heaps and Priority Queues.
Finished this lesson?