## McGill University:School of Computer Science Winter 1997 Class Notes for 308-251B DATA STRUCTURES AND ALGORITHMS Topic #18: RED-BLACK TREES

### Introduction to red-black trees

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.

### Definition

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.

Every node is colored either "red" or "black".

• 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.

### An example

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.

### Properties of red-black trees

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".
Property 2: A node of rank r has >= 2^r external nodes in its subtree.

Proof (by induction):
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.

Main property: The height of a red-black tree with n internal nodes is at most 2 log_2 (n + 1).

Proof:
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

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.

Phase II

 ``` 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. ```

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

Case 2a: p[x] is red and u[x] is red.
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.

Case 2b: p[x] is red and u[x] is black.
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.

### 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.

 CS660: RedBlack, B-Trees [Roger Whitney, San Diego State University]. [Tim Singletary (tsingletsingle@sunland.gsfc.nasa.gov)] [This page maintained by Barney Fife]. [Vladimir Forfuldinov, Windsor University]. [David Lewis, Swarthmore education]. [Doug Ierardi and Ta-Wei Li, Developed with the assistance of C Aydin, S Deng, C Kawahara, S Kolim and J Tsou]. [John Franco, University of Cincinnati]. [Eli Hadad, Tel Aviv University]. [Sean D. Sandys, University of Washington]. Here is a song about red-black trees.

### References

[1] R.Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms.
Acta Informatica 1:290-306, 1972.

[2] Leo J. Guibas and Robert Sedgewick. A diochromatic framework for balanced trees.
In Proceedings of the 19th Annual Symposium on Foundations of Computer Science,
pages 8-21. IEEE Computer Society, 1978.

[3] Nicholas Wilt, "Classical Algorithms in C++",

[4] Mark Allen Weiss, "Algorithms, Data Structures, and Problem Solving with C++",

### Web page creators

• Cheryl Tom morphis@cs.mcgill.ca
• (Java Applet)

• James Leung jleung@cs.mcgill.ca
• (Html, reference, graphics and researching sites)