Last modified: March 25, 1997
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.
Every node is colored either "red" or "black".
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.
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:
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.
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. |
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.
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]. |
---|---|
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]. |
[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.