Last modified: March 25, 1997

• Introduction to red-black trees
• Definition
• Properties of red-black trees
• Insertion
• Java applet for red-black trees
• Links to related material
• References

Red-black trees are binary search trees with worst-case height no more than 2 log_2 n. Standard dictionary operations (insert, delete, search, minimum, maximum, successor, predecessor) take O (log n) time. In contrast, standard binary search trees have Omega (n) height in the worst-case and O (log n) height on the average. They are, however, easier to implement.

Red-black trees have all the characteristics of binary search trees. In addition, red-black trees have the following characteristics.

• Each node of the tree contains the fields color, key, left, right, parent and an optional field rank.

• The rank in a tree goes from zero up to the maximum rank which occurs at the root. The rank roughly corresponds to the height of a node. The rank of two consecutive nodes differs by at most one. All the external nodes are black and have a rank zero.

If a black node has rank "r", then its parent has rank "r+1".

If a red node has rank "r", then its parent will have rank "r" as well.

• Consecutive red nodes are disallowed. This means every red node is followed by a black node, on the other hand a black node may followed by a black or red node. This implies that at most 50% of the nodes on any path from external node to root are red.

• Every path from the root to a leaf contains the same number of black nodes. This number called black-height of the tree.

In this section, we give an example of red-black tree with five levels. We set the ranks starting at the bottom and show some sample ranks. Note that there is some freedom in assigning ranks to nodes.

h is the height of a tree and r is the rank of the root.

Property 1: h/2 <= r <= h.

Proof:

The rank of the root "r" is greater than or equal to "h/2", since there are at least 50% black nodes on any path from external node to root. "r" is also less than or equal to the height of the tree "h".

i) Base case: Let r = 1 then root 1 has 2^1 external nodes.
ii) Assumption: Assume true up to but not including r.
iii) Verification: Verify the claim for r.


Since the number of external nodes in the subtrees >= 2^(r-1) + 2^(r-1) = 2^r, then 2^r <= n + 1 external nodes as required.

If r were > log_2 (n + 1), then it would have (by property 2) > 2^(log_2 (n + 1)) = n + 1 external nodes in its subtree, but this is impossible as there are only n + 1 external nodes in the tree. Thus, h <= 2r (property 1) <= 2 log_2 (n + 1) (as shown above ex absurdo).

Insertion

Phase I, Standard insert.
Phase II, Fix red-black tree property.

Phase I is as for the standard binary search tree. The tree is traversed and, when an external node is encountered, it is replaced with the new node. The new node must be colored red in order to preserve the characteristics of the red-black tree.

However, if the newly inserted node's parent is red we will have two consecutive red nodes in a path, which is not allowed. So, we have to fix the tree.

   While x is in case 2a and x is not root and p[x] is not root do:
   	Increase rank of p[p[x]] by one 
   	(this makes p[x] and u[x] black and p[p[x]] red).
   	x <- p[p[x]].
  If x is in case 1 or x is root or p[x] is root then stop.
  else [x is not root and p[x] is not root and x is in case 2b]
    Perform rotation as shown below and stop.

Insert node x is red and its parent p[x] is black then we can terminate the insertion.

x, p[x] and u[x] are all red, then we can recolor u[x] and p[x] to black and move x toward the root of the tree to recheck. There are four symmetric cases to case 2a, and the graph below show only one of the cases.

x and p[x] are red and u[x] is black.

The keys of the nodes fall naturally into place.

In above picture the tree above and subtree below this portion of tree are consider as outside world. In order to preserve the red-black tree properties, one must perform a little changing (local surgery). Outside world must not see this change after surgery.

Analysis of the algorithm for insertion

Every insertion consists of a standard insert (at O (log n) cost, as h <= 2 log_2 (n + 1)), followed by a number of rank changes (corresponding to case 2a: there are at most log_2 (n + 1) of these), and finally at most one rotation (case 2b). It is one of the few balanced binary search trees that requires only one rotation in the worst case per insertion.

The time for Phase I in insertion takes O (lg n).
The time for Phase II in insertion takes O (lg n) for changing the rank and O (1) for rotation.

Java applet for red-black trees

Topic18 Note

Red-black tree were invented by R.Bayer[1] under the same name "symmetric binary B-trees." Guibas and Sedgewick[2] studied their properties at length and introduced the red/black color convention.

Links to related material

[3] Nicholas Wilt, "Classical Algorithms in C++",
Published by John Wiley & Sons, Inc. (1995), 209-229.

[4] Mark Allen Weiss, "Algorithms, Data Structures, and Problem Solving with C++",
Published by Addison-Wesley Company, Inc. (1996), 572-594.

Web page creators