AVL vs Red-Black tree, side by side

AVL vs Red-Black

Both are binary search trees that rebalance themselves, so every search, insert and delete takes O(log n) time, whatever order the keys arrive in. This page inserts the same keys into an AVL tree (top) and a red-black tree (bottom) at the same time, one key per round, and then can delete half of them the same way. Both trees are built exactly as on their own pages, so the three pages always agree.

Two ways to stay balanced

• AVL (Adelson-Velsky and Landis, 1962) keeps a strict rule: at every node, the heights of the two subtrees differ by at most 1. Each node stores its height, and after an insert or delete the heights are fixed on the way back up. Any node whose sides differ by 2 is repaired with a single or double rotation.
• Red-black (Bayer 1972; Guibas and Sedgewick 1978) keeps a looser rule. Every node is red or black, the root is black, no red node has a red child, and every path from a node down to a missing child passes the same number of black nodes. Most repairs are recolourings; rotations are needed only in a few cases.

How tall can they get?

With n keys, an AVL tree is at most about 1.44 log₂ n levels tall; the tallest possible AVL trees are the "Fibonacci trees". A red-black tree is at most 2 log₂(n + 1) levels tall: a path can alternate red and black, so it can be twice as long as the all-black path. The stats line above each tree shows its height next to its limit.

The limits only matter for unlucky inputs. On random keys the two trees end up almost the same height. Sorted keys, which are very common in practice (IDs, timestamps), are where the difference shows. Measured with this page's own code:

                              height (levels)     average search (nodes)
                              AVL    red-black      AVL     red-black
40 random keys                6.4      6.7          4.63      4.68
40 ascending keys             6        8            4.57      4.72
1,000 ascending keys          10       17           8.99      9.41
100,000 ascending keys        17       31           15.69     16.10

Look at the last column. Even when the red-black tree is almost twice as tall, an average search visits only 3–5% more nodes. Most nodes sit in the full lower levels of both trees; only a few long paths make the red-black tree taller.

Rotations: averages vs worst cases

                                          AVL       red-black
inserts that rotate (random keys)         48%       41%
rotations per delete (random, average)    0.37      0.36
most rotations in ONE delete, 40 keys     4         3
                          1,000 keys      6         3
                        100,000 keys      8         3

On insert both trees rotate at most twice (one double rotation), and on average AVL rotates a little more often, because its stricter rule is broken more often. On delete the averages are almost equal. The difference is the worst case. A red-black delete never needs more than 3 rotations; an AVL delete can rotate at every level on the way up, so its worst case grows with the tree. For code that must bound the work of every single operation, such as an operating-system kernel, that guarantee matters more than the average.

Both also do bookkeeping that is not a rotation. AVL rewrites stored heights along the path; red-black recolours nodes. The stats lines count both.

Where each is used

• Red-black: the Linux kernel (the CFS process scheduler, memory maps, timers), Java's TreeMap and TreeSet (and the bins of a crowded HashMap), C++'s std::map and std::set. General-purpose libraries pick it for the bounded work per update.
• AVL: in-memory databases and indexes that are searched far more often than they are changed, where a slightly shorter tree pays off on every lookup.
• Neither, on disk: databases and file systems use B-trees and B+ trees, with hundreds of keys per node, so a lookup reads only 3 or 4 disk pages.

What to try

• Ascending keys, 40: the red-black tree grows 2 levels taller while AVL stays at the minimum. Watch the red-black tree recolour its way up the right spine.
• Random keys: two trees of nearly the same shape, reached in different ways.
• Delete Half: compare "most in one op" on the two stats lines.
• Type a key and press Insert or Delete to see a single case step by step.

Common mistakes

• "Red-black trees are faster" (or "AVL trees are faster"). On average they are nearly the same. They differ in worst cases, and in whether reads or writes dominate.
• Counting only rotations. AVL also updates stored heights on every insert and delete; red-black recolours. Both are work.
• Reading the height bounds as typical heights. 2 log₂ n is what a red-black tree may reach, not what it usually does.

References

AVL tree: comparison to other structures (Wikipedia)

Red-black trees in the Linux kernel