Self-balancing trees: AVL and red-black trees

In short: Search trees that rebuild themselves after insertion and deletion so that they do not degenerate into a long chain and operations stay fast.

In more detail: A binary search tree finds values in O(log n) if it is balanced. But if you insert sorted data (1, 2, 3, 4, …), a long “chain” with O(n) effort results. Self-balancing trees detect such imbalance and restore the balance with rotations.

In Depth

Rotation

A rotation rearranges a few nodes without violating the ordering. In a right rotation the left child becomes the new root of this subtree and the old node becomes its right child. It takes only constant time but reduces the height of a lopsided subtree.

AVL tree

Named after Adelson-Velsky and Landis (1962). Rule: for every node the heights of the left and right subtrees differ by at most 1 (balance factor −1, 0 or 1). If the rule is violated after insertion or deletion, single or double rotations correct the tree. AVL trees are very strictly balanced, search is particularly fast, insertion and deletion need somewhat more rebuilding.

Red-black tree

Every node is red or black. Rules: the root is black; a red node has only black children; every path from a node to the leaves contains the same number of black nodes. It follows that the longest path is at most twice as long as the shortest. It is less strict than AVL but needs fewer rebuilds on average. Many standard libraries use it, for example TreeMap and TreeSet in Java and std::map in C++.

When to use which

Both guarantee O(log n) for search, insertion and deletion. AVL suits many reads, red-black many modifications. In databases and file systems, where data lives on disks, one uses B-trees instead, which store several keys per node and need fewer accesses.

See also: Tree data structure, B-tree and B+ tree, Big O notation, Binary search