An AVL tree and a red-black tree are self-balancing binary search trees: search, insertion and deletion take O(log n). The AVL tree balances more strictly, the two sides of every node within one level of each other, so it stays lower. The red-black tree lets one path grow up to twice as long as another, so it rotates less: less often on insertion, at most three times per deletion. Use an AVL tree for lookups, a red-black tree for frequent updates.
Below, both get the same six sorted keys, and the sixth, 60, sets them apart: the AVL tree rotates, the red-black tree only recolors and grows a level.
// avl vs red-black
Insert 10, 20, 30, 40, 50 and 60, in that order, into an AVL tree and into a red-black tree. Sorted keys are the input that turns a plain binary search tree into a chain, each node under the last. Both trees here stay balanced, each by its own rule.
After 50 the two have the same shape: 20 at the root, 10 on its left, 40 on its right with 30 and 50 below it. Only the colors differ: in the red-black tree 30 and 50 are red. The sixth key, 60, goes below 50 in both trees. Do they repair it the same way?
In the AVL tree, the −2 over 20 is its balance factor: its left side is one level deep, its right side three, and an AVL tree allows a difference of at most one. After the rotation the tree is still three levels tall.
In the red-black tree, the new node's uncle, 30, is red, so recoloring alone repairs it (case 1), and no node moves. The tree grows to four levels.
Before 60 the two trees rotate at the same keys, 30 and 50, and the red-black tree also recolors nodes along the way. With 60 the AVL tree rotates a third time, and the red-black tree only recolors.
To see both shapes for yourself, press Clear in the AVL tree visualizer and in the red-black tree visualizer and insert the same keys.
The AVL rule. At every node, the heights of the two subtrees differ by at most one. That keeps an AVL tree of n keys below about 1.44 log2 n levels: a million keys take at most 28.
The red-black rules. Among them: a red node has no red child, and every path from a node down to an empty child, a NIL leaf, passes the same number of black nodes. So the longest path is at most twice the shortest, and a red-black tree of n keys has at most 2 log2(n + 1) levels. For a million keys that formula gives 39, and the tallest possible tree has 37.
After 60 the red-black tree's longest path is already twice its shortest, the most its rules allow. The shortest, 20 and 10, has two nodes, both black; the longest, 20, 40, 50 and 60, has four, black and red in turn. An AVL tree could never take this shape, as its root's two sides would differ by two levels.
Sorted keys keep pushing a red-black tree to its limit: with 100,000 keys inserted in ascending order, an AVL tree ends with 17 levels and a red-black tree with 31, the most any red-black tree of 100,000 keys can have. In random order the two come out about equally tall, 20 or 21 levels. A search compares at most one key per level, so the AVL tree's longest search is the shorter one; an average search differs far less, 15.7 comparisons against 16.1 on the sorted keys.
An insertion needs at most two rotations in both trees: one single or one double rotation in an AVL tree, a case 2 rotation and then a case 3 rotation in a red-black tree. The red-black tree more often gets by with recoloring alone, as with 60 here. With 100,000 random keys, the AVL tree rotated on about 46% of the insertions, the red-black tree on about 39%. A recoloring only changes the color bit of a few nodes and moves none of them.
On deletion the difference lies in the worst case. An AVL tree may have to rotate at every level up to the root, while a red-black tree never rotates more than three times; in exchange its repair may recolor nodes all the way up to the root, which is cheap.
| AVL tree | Red-black tree | |
|---|---|---|
| Balance rule | At every node, the two subtrees differ in height by at most one | No red node has a red child; every path down passes the same number of black nodes |
| Height with n keys | Below about 1.44 log2 n | At most 2 log2(n + 1) |
| A million keys, worst case | 28 levels | 37 levels |
| Search, insertion, deletion | O(log n) | O(log n) |
| Rotations per insertion | At most 2 | At most 2 |
| Rotations per deletion | Up to one single or double rotation per level | At most 3 |
| Kept in each node | Its height or its balance factor | One bit: its color |
| The six keys here | 3 levels, 3 rotations | 4 levels, 2 rotations |
| Typical uses | Data that is searched far more often than it changes | Ordered maps and sets in standard libraries, the Linux kernel |
Use an AVL tree when lookups far outnumber insertions and deletions: its lower height means fewer comparisons per search, if only slightly on average.
Use a red-black tree when keys are inserted and deleted often: it rotates less often on insertion and at most three times per deletion. That is why general-purpose ordered maps such as C++ std::map and Java's TreeMap are usually red-black trees.
For data on disk, both lose to a B-tree, whose wide nodes need far fewer reads. A red-black tree is in fact a B-tree of maximum degree 4 drawn as a binary tree: each black node and its red children make one B-tree node.
O(log n).For lookups, usually the AVL tree, which is lower, though an average search differs only slightly. For insertions and deletions, usually the red-black tree, which rotates less often on insertion and never more than three times per deletion, where an AVL tree may rotate at every level. All three operations are O(log n) in both.
A general-purpose ordered map has to serve any mix of lookups, insertions and deletions. A red-black tree keeps all three O(log n), changes its shape less on each update, and needs only one bit per node for its color.
Yes: every AVL tree can be colored so that it meets the red-black rules. The reverse is not true. The red-black tree built here from 10 to 60 is not an AVL tree, as the two sides of its root differ by two levels.
// in the app
In VisiGrab, the AVL tree and the red-black tree each have a topic where you build your own tree, insert and delete keys, and step through every repair.
In both, insert any key with “+”, tap a node to delete it, or start from a random tree. Every insert and delete is kept in a list.
Step forward and back through each AVL rotation, and through each red-black recoloring and rotation with the C, P, G and U markers.
AVL rotations after a deletion, where the repair can climb to the root, and the red-black tree's double black with its four cases.
The balance factor and the four rotations; the red-black rules, NIL leaves and black height; each with examples to step through.
A complete implementation of each tree in all three languages, explained part by part.
Ten questions on each tree, with an explanation for every option.
// build your own
Download VisiGrab to build both trees from your own keys, delete any key, and step through every rotation and recoloring.
The AVL tree and the red-black tree each have a topic among 30+. See them all