AVL Tree vs Red-Black Tree, step by step.

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 tree vs red-black tree: what differs

The same six keys, two trees

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?

AVL tree: insert 60 after 10 to 50

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.
  3. The node with key 20 is unbalanced. To restore balance, a single left rotation is required.
  4. An arrow is now displayed above the node around which the rotation will occur.
  5. The node with key 20 is rotated downwards and to the left. The node with key 40 becomes the new root.
  6. Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.
AVL Tree vs Red-Black Tree — AVL tree: insert 60 after 10 to 50. Last step: Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.

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.

Red-black tree: the same 60

All steps as text
  1. The highlighted node shows where the new key will go. Step forward to insert it.
  2. When adding a new node to the red-black tree, it is initially colored red and becomes either the left or right child of an existing node, based on key comparisons within the tree.
  3. A violation of the red-black tree property has occurred: the current node, marked C, is red and has a red parent, which is not allowed. Adjustments are required to restore the tree's balance.
  4. To rebalance the tree, the relationships between the current node, its parent, uncle, and grandparent are considered. These nodes are marked for clarity: P for the parent, G for the grandparent, and U for the uncle.
  5. In this case, the current node's uncle U is red.
  6. The parent P and uncle U nodes are recolored to black, and the grandparent G to red.
  7. Move up to the grandparent, now the new current node, and repeat the rebalancing process if its parent is red.
  8. If the parent of the current red node is black, the rebalancing process is considered complete.
  9. As can be seen now, the tree is balanced and all its red-black properties are fulfilled.
AVL Tree vs Red-Black Tree — Red-black tree: insert 60 after 10 to 50. Last step: As can be seen now, the tree is balanced and all its red-black properties are fulfilled.

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.

How tall each tree can grow

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.

Rotations: what the red-black tree saves

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 vs red-black tree at a glance

AVL treeRed-black tree
Balance ruleAt every node, the two subtrees differ in height by at most oneNo red node has a red child; every path down passes the same number of black nodes
Height with n keysBelow about 1.44 log2 nAt most 2 log2(n + 1)
A million keys, worst case28 levels37 levels
Search, insertion, deletionO(log n)O(log n)
Rotations per insertionAt most 2At most 2
Rotations per deletionUp to one single or double rotation per levelAt most 3
Kept in each nodeIts height or its balance factorOne bit: its color
The six keys here3 levels, 3 rotations4 levels, 2 rotations
Typical usesData that is searched far more often than it changesOrdered maps and sets in standard libraries, the Linux kernel

When to use an AVL tree and when a red-black tree

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.

Common mix-ups

  • A red-black tree is not really balanced. It is, only less strictly: its height stays below 2 log2(n + 1), so search, insertion and deletion stay O(log n).
  • An AVL tree rotates on every insertion. Only when some node's two sides end up two levels apart: 3 of the 6 keys here, and a little under half of random keys.

AVL tree vs red-black tree interview questions

Which is faster, an AVL tree or a red-black tree?

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.

Why do standard libraries use red-black trees?

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.

Is every AVL tree a red-black tree?

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.

Comic: The Perfectionist An AVL tree measures and rotates; a red-black tree relaxes.

Six keys here.
Both trees 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.

Your own trees

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.

Every repair, step by step

Step forward and back through each AVL rotation, and through each red-black recoloring and rotation with the C, P, G and U markers.

Deletion in both

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.

Theory with examples

The balance factor and the four rotations; the red-black rules, NIL leaves and black height; each with examples to step through.

Python, Java and C++

A complete implementation of each tree in all three languages, explained part by part.

Two quizzes

Ten questions on each tree, with an explanation for every option.

Strict or relaxed,
on the same keys.

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