AVL Tree

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.

Complexity

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)`

How it works

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.

Python implementation

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)

Trade-offs

Strictly balanced — slightly faster lookups than red-black trees.
Slightly more rotations on insert/delete; a worse choice if writes dominate reads.
Worst-case O(log n) on every operation.
Common in databases and routing tables where reads outnumber writes.

← Back to Algorithms