An AVL tree (Adelson-Velsky & Landis, 1962 — the original self-balancing BST) keeps every node's subtree heights within 1 of each other. It is more rigidly balanced than a red-black tree, giving slightly faster lookups but slightly slower inserts/deletes.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(log n) |
Θ(log n) |
Θ(log n) |
Θ(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Each node tracks its height. After a normal BST insert/delete, walk back up updating heights; at any node where balance factor (left height − right height) is −2 or +2, perform one of four rotations: LL, RR, LR, RL. Rebalancing fixes the imbalance in O(1), and at most O(log n) rotations happen per operation.
class Node:
__slots__ = ("key", "left", "right", "h")
def __init__(self, key):
self.key, self.left, self.right, self.h = key, None, None, 1
def _h(n): return n.h if n else 0
def _bf(n): return _h(n.left) - _h(n.right) if n else 0
def _upd(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
_upd(y); _upd(x); return x
def _rotate_left(x):
y = x.right; x.right = y.left; y.left = x
_upd(x); _upd(y); return y
def insert(node, key):
if node is None: return Node(key)
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
else:
return node
_upd(node)
bf = _bf(node)
if bf > 1 and key < node.left.key: return _rotate_right(node) # LL
if bf < -1 and key > node.right.key: return _rotate_left(node) # RR
if bf > 1 and key > node.left.key: # LR
node.left = _rotate_left(node.left); return _rotate_right(node)
if bf < -1 and key < node.right.key: # RL
node.right = _rotate_right(node.right); return _rotate_left(node)
return node
root = None
for k in [10, 20, 30, 40, 50, 25]:
root = insert(root, k)
print(root.key) # 30 (well-balanced root)Running the code above inserts 10, 20, 30, 40 and 50. Inserting 30 after 10 and 20 creates a right-right chain, so the tree rotates left at 10 and 20 becomes the root; inserting 50 triggers the same fix lower down, making 40 the parent of 30 and 50. The final insert of 25 descends 20, 40, 30 and attaches as the left child of 30. Walking back up, node 40 has balance factor +1 (fine), but node 20 now has a left subtree of height 1 and a right subtree of height 3, a balance factor of -2. Because 25 is smaller than 40, the path is right then left, the RL case: first rotate 40's subtree right so 30 rises, then rotate 20 left. Node 30 becomes the root and every node is back within the AVL invariant.
The balance factor of a node is the height of its left subtree minus the height of its right subtree. AVL trees require it to stay in {-1, 0, +1} for every node. A single insertion can push it to +2 or -2 at nodes on the path from the new leaf to the root. A rotation is a local pointer rewrite of three nodes that preserves the in-order key sequence (so the tree is still a valid binary search tree) while shifting height from one side to the other. On insertion, one single or double rotation at the lowest unbalanced node restores balance for the whole tree; deletion may need rotations at several ancestors, up to O(log n).
The strict invariant bounds the height to roughly 1.44 log2(n + 2), compared with about 2 log2(n + 1) for red-black trees, which is why AVL lookups touch fewer nodes on average. The price is more frequent rebalancing on writes.
def contains(node, key):
while node:
if key == node.key:
return True
node = node.left if key < node.key else node.right
return False
def inorder(node):
if node:
yield from inorder(node.left)
yield node.key
yield from inorder(node.right)
print(contains(root, 25), contains(root, 99)) # True False
print(list(inorder(root))) # [10, 20, 25, 30, 40, 50]
print(root.h) # 3Lookup is the plain BST search and needs no balance logic; the balancing work is entirely in the write path. An in-order traversal yields the keys sorted, which makes AVL trees suitable for ordered maps, range scans and rank queries (with an extra subtree-size field).
| Structure | Lookup | Insert/delete | Notes |
|---|---|---|---|
| AVL tree | O(log n), shallowest | O(log n), more rotations | read-heavy ordered maps |
| Red-black tree | O(log n) | O(log n), fewer rotations | std::map, Java TreeMap |
| Skip list | O(log n) expected | O(log n) expected | simpler concurrency |
| Hash table | O(1) average | O(1) average | no ordering or range queries |
| B-tree | O(log n), few disk reads | O(log n) | on-disk indexes |
Pick an AVL tree when you need ordered keys in memory and reads clearly dominate writes. For mixed workloads most standard libraries choose red-black trees, and for data on disk B-trees win because they minimise page reads.