Next Chapter Return to Table of Contents Previous Chapter

SECTION U: RED-BLACK TREES

A 3-ode or a 4-ode can be modeled with a binary subtree, bound together with links that are called red links to distinguish them from the links of the 2-3-4 tree in which they occur, called black links. With the use of dashed lines to represent red links, the tree is shown in Figure U.1 . In a tree represented this way, 4-nodes are characterized by having a subtree root with red links to both children.

The depth of an RBT (Red-Black Tree) binary tree may be twice that of the corresponding 2-3-4 tree, but it is still proportional to the log of the number of keys in it. The links of an RBT need to be flagged with their color; and, if the nodes are entirely supported in arrays, the sign bit of the pointer index may be used. An alternate scheme, used here, is to flag a node with the color of the link that leads to it from its parent. It is convenient to include a field in the node that contains a pointer Up to the parent of the node.

The creation operation becomes:

procedure Create(rbt,LeftChild,RightChild)

NEW(rbt)

rbt  .Up  rbt

rbt  .Left  LeftChild

rbt  .Right  RightChild

rbt  .Red  FALSE

end {Create

Figure U.1

The search operation, likely to be used more than any other, is then:

procedure RBSearch(rbt,SearchKey,Node,Found)

Node  rbt

Parent  rbt

while Node  u do                 {u is the universal tail.

if SearchKey = Node  .Key

then Found  TRUE

return

endif

Parent  Node

if  SearchKey < Node  .Key

then Node  Node  .Left

else Node  Node  .Right

endif

endwhile

Found  FALSE

Node  Parent

end {RBSearch

Insertion includes a similar traverse that splits 4-nodes as they are encountered. The splitting operation is applied to the root node, or to a 4-node reached from a 2-node (a 2-4 subtree) or a 4-node reached from a 3-node (a 3-4 subtree).

The root-node split is shown schematically in Figure U.2 . The split simply changes two red links to black links. No key value is actually shifted.

Figure U.2

The 2-4 subtree split schematically changes the (2-node to 4-node subtree) to a (3-node to two 2-nodes) subtree, shown in Figure U.3.

Figure U.3

Once again, no information is altered except the color of the links.

In the case of a 3-4 subtree, the 3-node may have either binary node as the subtree root. For example, Figure U.4 may be represented in either of the ways shown in Figure U.5 .

Figure U.4

Figure U.5

Similarly, the 3-4 subtree of Figure U.6 has two representations, shown in Figure U.7, both having a red grandparent-parent link relative to the 4-node.

Figure U.6

Figure U.7

When the grandparent-parent link of a 4-node is red, a simple color-shift applied during splitting of the node produces two red links in sequence, as Figure U.8 illustrates for case (2) (from Figure U.5).

Figure U.8

This is prevented for the case of Figure U.4 by a rotation, in which the lexicographic order of the keys is unchanged, but the relative levels of two nodes are switched. A rotation switches the binary-tree levels of the two keys in a 3-node and shifts links to their parent and children to match. A rotation of keys x and y is considered to be the rotation of the child and grandchild of the node n, as depicted in Figure U.9. After this rotation, splitting the right child of gc does not produce two red links in succession.

Figure U.9

If a 4-node is the middle child of a 3-node, it remains a middle child after rotation and retains a red grandparent-parent link, as shown in Figure U.10. One approach to resolving this problem is a prior rotation involving the root of the 4-node itself, shown in Figure U.11. Figure U.12 shows the result when this rotation is followed by a rotation at the (original) great-grandparent of node.

Figure U.10

Figure U.11

Figure U.12

With color changes at z and f, this double rotation has the effect in the RBT shown in Figure U.13. None of these rotations change the number of levels in the 2-3-4 tree.

Figure U.13

It is convenient to design a generic rotation that internally traces the path from node to grandchild in order to detect left and right branches:

procedure Rotate(SKey,n)

if SKey > n  .Key

then c  n  .Right

else c  n  .Left

endif

if SKey > c  .Key

then gc  c  .Right

ggc  gc  .Left

c  .Right  ggc

gc  .Left  c

else gc  c  .Left

ggc  gc  .Right

c  .Left  ggc

gc  .Right  c

endif

if SKey > n  .Key

then n  .Right  gc

else n  .Left  gc

endif

gc  .Up  n

c  .Up  gc

ggc  .Up  c

Color  gc  .Red

gc  .Red  c  .Red

c  .Red  Color

end {Rotate

The middle-child case is characterized by the alteration in direction of grandparent-parent and parent-node links and requires a rotation to change it into the other case. The splitting operation thus becomes:

procedure RBSplit(SKey,Node)

p  Node  .Up

if p  .Red

then gp  p  .Up

ggp  gp  .Up

if SKey < gp  .Key  SKey < p  .Key

then Rotate(SKey,gp)

if SKey < p  .Key

then p  .Right  .Red  TRUE

Node  .Left  .Red  FALSE

else p  .Left  .Red  TRUE

Node  .Left  .Red  FALSE

endif

endif

Rotate(SKey,ggp)

endif

if Node  rbt then Node  .Red  TRUE endif

Node  .Left  .Red  FALSE

Node  .Right  .Red  FALSE

end {RBSplit

The insertion procedure repeats the search process explicitly, except that it also splits 4-nodes during the traverse. The use of a universal tail node u allows the new node to be treated as the root of a 4-node subtree and immediately split upon entry to properly adjust its relationship to its parent:

procedure RedBlackIn(rbt,NewKey,NewValue)

if rbt = u

then Create(rbt,u,u)

rbt  .Value  NewValue

rbt  .Key  NewKey

return

endif

Node  rbt

while Node  u do

if NewKey = Node  .Key

then return               {or otherwise deal with

endif                     {a duplicate key.

Parent  Node

if Node  .Left  .Red AND Node  .Right  .Red

then RBSplit(NewKey,Node)

else if NewKey < Node  .Key

then Node  Node  .Left

else Node  Node  .Right

endif

endif

endwhile

Create(Node,u,u)

with Node do

Up  Parent

Value  NewValue

Key  NewKey

Red  FALSE

endwith

if NewKey < Parent  .Key

then Parent  .Left  Node

else Parent  .Right  Node

endif

RBSplit(NewKey,Node)

end {RedBlackIn

Problem

Program

Problem

Problem not immediate, but requiring no major extensions of text

PU.1 Draw the sequence of Red-Black trees that would be created by entering the months in calendar order if they are to be kept in alphabetical order.

Program

Program for trying it yourself

PGU.1 Write a program that will accept strings and place them in a Red-Black tree ordered lexicographically. The program should display the tree after entries. Test it with the months of the year, entered in reverse calendar order.

Go to Section V Return to Table of Contents