McGill University:
School of Computer Science
Winter 1997 Class Notes for 308-251B

DATA STRUCTURES AND ALGORITHMS

Topic #18: RED-BLACK TREES

Last modified: March 25, 1997


Table of Contents


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.


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:

Property 2: A node of rank r has >= 2^r external nodes in its subtree.

Proof (by induction):

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

Proof:


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.

Case 2a: p[x] is red and u[x] is red.

Case 2b: p[x] is 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


Java applet for red-black trees


Link to red-black tree applet.


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

CS660: RedBlack, B-Trees

[Roger Whitney, San Diego State University].


MIT Scheme Reference

[Tim Singletary (tsingletsingle@sunland.gsfc.nasa.gov)]


The (Combinatorial) Object Server

[This page maintained by Barney Fife].


Vlad Web Space

[Vladimir Forfuldinov, Windsor University].


Red-Black Trees

[David Lewis, Swarthmore education].


Red-Black Tree Animation

[Doug Ierardi and Ta-Wei Li, Developed with the assistance of C Aydin, S Deng, C Kawahara, S Kolim and J Tsou].


Red/Black Tree Demonstration

[John Franco, University of Cincinnati].


Red Black Tree Simulation

[Eli Hadad, Tel Aviv University].


The Red Black Tree Song

[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++",
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

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

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

  • Mansour-Mohammad Esmaeil mrmdessi@cs.mcgill.ca
  • (Java Applet and Html)

  • Marco Raimo chewy@cs.mcgill.ca

  • Copyright ©1997,by Cheryl Tom, James Leung, Mansour-Mohammad Esmaeil and Marco Raimo . All rights reserved. Reproduction of all or part of this work is permitted for educational research use provided that this copyright notice is included in any copy. Disclaimer: this collection o notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.