|
The red-black algorithm, a twist on the classic binary search tree, uses an efficient mechanism for balancing trees.
April 01, 1992
URL:http://www.drdobbs.com/database/red-black-trees/184408744
Copyright © 1992, Dr. Dobb's Journal
Copyright © 1992, Dr. Dobb's Journal
Bruce has an MS in Computer Science and has worked in cryptography and data security for a number of public and private concerns. He can be reached at 730 Fair Oaks Ave., Oak Park, IL 60302.
Red-black trees are a variation of classic binary search trees that use an efficient mechanism for keeping the tree in balance. This article describes the basic concepts of red-black trees and presents the pseudocode for the insert and delete operations.
Binary search trees have traditionally been a useful way to store dynamic data. If the tree is balanced, you can do searches, insertions, and deletions much faster than if the data were in a linked list. If the tree is large and ugly, however, its performance may be only marginally better than that of a linked list; see Figure 1.
The operations to balance a binary tree are relatively easy to implement, but can consume much execution time. If there are a lot of insertions into and deletions from the binary tree, the performance advantage over a linked list may not amount to much. Recently, a number of tricks have appeared in academic literature. These are intended to make sure a binary tree stays balanced without the grief of standard balancing operations.
A red-black tree is a form of binary tree in which each node is assigned a color: either red or black. By constraining the particular coloring of the nodes during inserts and deletes, you can make sure the binary tree stays mostly balanced. Search operations are completed faster than with linked lists, and all of those extra tree pointers don't go to waste. This technique was first invented by R. Bayer, and then studied and embellished by L.J. Guibas and R. Sedgewick.
In this article, I'm assuming you know what a binary search tree is. I also assume you know how to insert nodes into and delete nodes from a binary search tree. For a refresher course on binary search trees, see section 6.2.2 of Knuth's The Art of Computer Programming, vol 3: Searching and Sorting Algorithms.
The data structure for a red-black tree is just like a normal binary search tree except that each node has one extra bit of storage, which contains the node's color.
There are five rules for building a red-black tree:
The usual algorithms for insertion into and deletion from a binary tree can break the red-black rules, so new methods are necessary. Examples 1 and 2 present the pseudocode for insertion into and deletion from a red-black tree.
RedBlackInsert (T,x)
{
TreeInsert (T,x)
color (x) <- Red
while x != root (T) and color (p(x))==Red
if p(x)==left(p(p(x)))
y <- right(p(p(x)))
if color(y)==Red
color(p(x)) <- Black
color(y) <- Black
color(p(p(x))) <- Red
x <- p(p(x))
else
if x==right(p(x))
x <- p(x)
RotateLeft(T,x)
color(p(x)) <- Black
color(p(p(x))) <- Red
RotateRight(T, p(p(x)))
else
/* this is the same as the "then" clause,
* with "right" and "left" interchanged */
color(root(T)) <- Black
}
RedBlackDelete(T,z)
{
if left(z)==nil(T) or right(z)==nil(T)
y <-- z
else
y <-- TreeSuccessor(z)
if left(y) != nil(T)
x <-- left(y)
else
x <-- right(y)
p(x) <-- p(y)
if p(y) == nil(T)
root(T) <-- x
else
if y==left(p(y))
left(p(x)) <-- x
else
right(p(y)) <-- x
if y != z
key(z) <-- key(y)
/* if y has other fields, copy them too */
if color(y)==Black
then RBDeleteFixup(T,x)
}
RBDeleteFixup(T,x)
{
while x != root(T) and color(x)==Black
if x==left(p(x))
w <-- right(p(x))
if color(w) <-- Black
color(p(x)) <-- Red
RotateLeft(T,p(x))
w <-- right(p(x))
if color(left(w)) == Black and color (right(w))==Black
color(w) <-- Red
x <-- parent(x)
else
if color(right(w)) == Black
color(left(w)) <-- Black
color(w) <-- Red
RotateRight(T,w)
w <-- right(p(x))
color(w) <-- color(p(x))
color(p(x)) <-- Black
color (right(w)) <-- Black
RotateLeft(T,p(x))
x <-- root(T)
else
/* this is same as "then" clause,
* except that right and left are exchanged */
color(x) <--Black
}
In the pseudocode, the variables node. llink and node.rlink are pointers to the left and right children of the node; the variable node.parent is a pointer to the parent of the node. (Technically, you can save pointers as you traverse the tree and do without a parent pointer, but having a parent pointer makes the pseudocode a lot easier.)
The pseudocode assumes you know how to insert a node into a binary tree, find the successor of a node in a binary tree, and also how to rotate a binary tree to the left and right at a node. If you don't, reread the appropriate section in Knuth.
The algorithm for red-black insert (Example 1) can be stated concisely: First, do a normal binary tree insert and force the color of the new node to be red; then, mess with the ordering and the coloring of the nodes to preserve the red-black rules of the tree.
When a red node is inserted into a red-black tree, the only rule that might be violated is rule 4--and only if the new node's parent is also red. The while loop in the algorithm has the job of moving the rule 4 violation up the tree without violating rule 5. There are three cases to consider. (Actually there are six, but three are symmetrical with each other, depending on whether the new node's parent is a left child or a right child.) The principal cases are:
Case 1: If the new node's parent and uncle (parent's parent's other child) are both red, then the color of the parent and the uncle are changed to black, and the color of the grandparent is set to red. This moves the problem up two levels, so the while loop repeats with the grandparent of the node.
Case 2: If the new node's parent is red and uncle is black, there are two similar possibilities. If the new node is a left child of its parent, then the color of the parent is changed to black, the color of the grandparent is changed to red, and the tree is rotated right about the node's parent. This solves everything and the algorithm terminates.
Case 3: If the new node is a right child of its parent, then a left rotation about the parent is performed, and then everything proceeds as in case 2.
The algorithm for the delete operation (shown in Example 2) is more complicated, at least some of the time. If the deleted node is red, all of the rules still hold and everything is fine. If the node is black, there is a mound of code designed to keep the tree somewhat balanced. As with red-black insert, there are many different cases to consider and different things to do in each case. It all works out for the best in the end, though.
Red-black trees are not suitable for every tree application. If the data is mostly static, it might be quicker to let the nodes fall where they may and not bother with balancing operations. For data that is completely static, such as a dictionary that comes with a spelling checker, it is probably better to completely optimize the tree beforehand, or use a heap or a perfect hasher.
For data where certain nodes are accessed far more frequently than most of the others, a self-adjusting binary tree (see "Self-Adjusting Data Structures" by Andrew Liao, DDJ, February 1990) is probably a better choice. But for data that is uniformly accessed and frequently updated, a red-black tree is probably the way to go.
For a detailed discussion of these algorithms, I enthusiastically recommend the book Introduction to Algorithms, by Cormen, Leiserson, and Rivest. First published in 1990, the book is already in its third printing and is probably the best book on algorithms since Knuth. It belongs on every serious programmer's shelf.
Bayer, R. "Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms." Acta Informatica 1, 1972.
Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. Cambridge, Mass.: MIT Press/McGraw-Hill, 1991.
Guibas, L.J. and R. Sedgewick. "A Diochromatic Framework for Balanced Trees." Proceedings of the 19th Annual Symposium on Foundations of Computer Science (1978).
Sedgewick, R. Algorithms. Reading, Mass.: Addison-Wesley, 1983.
_RED-BLACK TRESS_
by Bruce Schneier
[Example 1: Insert operation, in pseudocode]
RedBlackInsert(T,x)
{
TreeInsert(T,x)
color(x) <-- Red
while x != root(T) and color(p(x))==Red
if p(x)==left(p(p(x)))
y <-- right(p(p(x)))
if color(y)==Red
color(p(x)) <-- Black
color(y) <-- Black
color(p(p(x))) <-- Red
x <-- p(p(x))
else
if x==right(p(x))
x <-- p(x)
RotateLeft(T,x)
color(p(x)) <-- Black
color(p(p(x))) <-- Red
RotateRight(T, p(p(x)))
else
/* this is the same as the "then" clause,
* with "right" and "left" interchanged */
color(root(T)) <-- Black
}
[Example 2: Delete operation, in pseudocode]
RedBlackDelete(T,z)
{
if left(z)==nil(T) or right(z)==nil(T)
y <-- z
else
y <-- TreeSuccessor(z)
if left(y) != nil(T)
x <-- left(y)
else
x <-- right(y)
p(x) <-- p(y)
if p(y) == nil(T)
root(T) <-- x
else
if y==left(p(y))
left(p(x)) <-- x
else
right(p(y)) <-- x
if y != z
key(z) <-- key(y)
/* if y has other fields, copy them too */
if color(y)==Black
then RBDeleteFixup(T,x)
}
RBDeleteFixup(T,x)
{
while x != root(T) and color(x)==Black
if x==left(p(x))
w <-- right(p(x))
if color(w) <-- Black
color(p(x)) <-- Red
RotateLeft(T,p(x))
w <-- right(p(x))
if color(left(w)) == Black and color(right(w))==Black
color(w) <-- Red
x <-- parent(x)
else
if color(right(w)) == Black
color(left(w)) <-- Black
color(w) <-- Red
RotateRight(T,w)
w <-- right(p(x))
color(w) <-- color(p(x))
color(p(x)) <-- Black
color(right(w)) <-- Black
RotateLeft(T,p(x))
x <-- root(T)
else
/* this is same as "then" clause,
* except that right and left are exchanged */
color(x) <--Black
}
Copyright © 1992, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.