AVL Trees

A binary search tree is fast only while it stays balanced. If the keys arrive in sorted order, every new key goes to the same side and the tree turns into a linked list with search time O(n). An AVL tree (Adelson-Velsky and Landis, 1962) is a BST that repairs itself after every insert with rotations, so its height always stays O(log n).

The problem: a degenerate BST

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.h = 1

def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    else:
        root.right = bst_insert(root.right, key)
    return root

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = None
for key in range(1, 8):
    root = bst_insert(root, key)
print("height of the BST for 1..7:", height(root))

height of the BST for 1..7: 7

Seven keys give height 7 instead of the possible 3. For a million sorted keys a plain BST needs a million steps for a search.

The balance factor

Every node stores the height of its subtree. The balance factor is h(left) - h(right). The AVL invariant: in every node it is -1, 0 or 1. Such a tree with n nodes has height at most about 1.44 · log2(n).

Rotations

A rotation re-hangs a few pointers in O(1) and keeps the in-order sequence of keys, so the tree stays a valid BST. rotate_right(y) lifts the left child x; rotate_left is its mirror.