7 Red-Black Trees: Dictionary Data Type, Which Requires Support For

7 Red-Black Trees
Binary search trees are an elegant implementation of the

dictionary data type, which requires support for
item SEARCH (item),
void INSERT (item),
void DELETE (item),
and possible additional operations. Their main disadvan-
tage is the worst case time (n) for a single operation.
The reasons are insertions and deletions that tend to get
the tree unbalanced. It is possible to counteract this ten-
dency with occasional local restructuring operations and
to guarantee logarithmic time per operation.
2-3-4 trees. A special type of balanced tree is the 2-3-4
tree. Each internal node stores one, two, or three items
and has two, three, or four children. Each leaf has the
same depth. As shown in Figure 15, the items in the in-
ternal nodes separate the items stored in the subtrees and
thus facilitate fast searching. In the smallest 2-3-4 tree of
7 15
25 20 4 17 9 2
Figure 15: A 2-3-4 tree of height two. All items are stored in
internal nodes.
height h, every internal node has exactly two children, so
we have 2
h
leaves and 2
h
1 internal nodes. In the largest
2-3-4 tree of height h, every internal node has four chil-
dren, so we have 4
h
leaves and (4
h
1)/3 internal nodes.
We can store a 2-3-4 tree in a binary tree by expanding a
node with i > 1 items and i +1 children into i nodes each
with one item, as shown in Figure 16.
Red-black trees. Suppose we color each edge of a bi-
nary search tree either red or black. The color is conve-
niently stored in the lower node of the edge. Such a edge-
colored tree is a red-black tree if
(1) there are no two consecutive red edges on any de-
scending path and every maximal such path ends with
a black edge;
(2) all maximal descending paths have the same number
of black edges.
b a c
or
a b
b
a
c a
a b
b
Figure 16: Transforming a 2-3-4 tree into a binary tree. Bold
edges are called red and the others are called black.
The number of black edges on a maximal descending path
is the black height, denoted as bh(). When we transform
a 2-3-4 tree into a binary tree as in Figure 16, we get a red-
black tree. The result of transforming the tree in Figure 15
17
20
15
25
2
9
7
4
Figure 17: A red-black tree obtained from the 2-3-4 tree in Fig-
ure 15.
is shown in Figure 17.
HEIGHT LEMMA. A red-black tree with n internal nodes
has height at most 2 log
2
(n + 1).
PROOF. The number of leaves is n + 1. Contract each
red edge to get a 2-3-4 tree with n + 1 leaves. Its height
is h log
2
(n + 1). We have bh() = h, and by Rule
(1) the height of the red-black tree is at most 2bh()
2 log
2
(n + 1).
Rotations. Restructuring a red-black tree can be done
with only one operation (and its symmetric version): a ro-
tation that moves a subtree from one side to another, as
shown in Figure 18. The ordered sequence of nodes in the
left tree of Figure 18 is
. . . , order(A), , order(B), , order(C), . . . ,
and this is also the ordered sequence of nodes in the right
tree. In other words, a rotation maintains the ordering.
Function ZIG below implements the right rotation:
22
C B
A
B A
C
right rotation
left rotation
Zig
Zag
Figure 18: From left to right a right rotation and from right to
left a left rotation.
Node ZIG(Node )
assert = NULL and = = NULL;
= r; r = ; return .
Function ZAG is symmetric and performs a left rotation.
Occasionally, it is necessary to perform two rotations in
sequence, and it is convenient to combine them into a sin-
gle operation referred to as a double rotation, as shown
in Figure 19. We use a function ZIGZAG to implement a
A
right rotation
ZigZag
double

C B
A
D
B C D
Figure 19: The double right rotation at is the concatenation of
a single left rotation at and a single right rotation at .
double right rotation and the symmetric function ZAGZIG
to implement a double left rotation.
Node ZIGZAG(Node )
= ZAG( ); return ZIG().
The double right rotation is the composition of two single
rotations: ZIGZAG() = ZIG() ZAG(). Remember
that the composition of functions is written from right to
left, so the single left rotation of precedes the single right
rotation of . Single rotations preserve the ordering of
nodes and so do double rotations.
Insertion. Before studying the details of the restructur-
ing algorithms for red-black trees, we look at the trees that
arise in a short insertion sequence, as shown in Figure 20.
After adding 10, 7, 13, 4, we have two red edges in se-
quence and repair this by promoting 10 (A). After adding
2, we repair the two red edges in sequence by a single ro-
tation of 7 (B). After adding 5, we promote 4 (C), and after
adding 6, we do a double rotation of 7 (D).
5
4 13
2
4
5
2 7
10
6
5
13
7
2 7
6
10
4
A
7
D
C
B
13
4
2
10
13
4
10 10
13 7
Figure 20: Sequence of red-black trees generated by inserting
the items 10, 7, 13, 4, 2, 5, 6 in this sequence.
An item x is added by substituting a new internal node
for a leaf at the appropriate position. To satisfy Rule (2)
of the red-black tree denition, color the incoming edge
of the new node red, as shown in Figure 21. Start the

x
Figure 21: The incoming edge of a newly added node is always
red.
adjustment of color and structure at the parent of the new
node. We state the properties maintained by the insertion
algorithmas invariants that apply to a node traced by the
algorithm.
INVARIANT I. The only possible violation of the red-
black tree properties is that of Rule (1) at the node
, and if has a red incoming edge then it has ex-
actly one red outgoing edge.
Observe that Invariant I holds right after adding x. We
continue with the analysis of all the cases that may arise.
The local adjustment operations depend on the neighbor-
hood of .
Case 1. The incoming edge of is black. Done.
23
Case 2. The incoming edge of is red. Let be the
parent of and assume is left child of .
Case 2.1. Both outgoing edges of are red, as
in Figure 22. Promote . Let be the parent of
and recurse.
Figure 22: Promotion of . (The colors of the outgoing edges of

may be the other way round).
Case 2.2. Only one outgoing edge of is red,
namely the one from to .
Case 2.2.1. The left outgoing edge of is
red, as in Figure 23 to the left. Right rotate
. Done.
Figure 23: Right rotation of to the left and double right rotation
of to the right.
Case 2.2.2. The right outgoing edge of
is red, as in Figure 23 to the right. Double
right rotate . Done.
Case 2 has a symmetric case where left and right are in-
terchanged. An insertion may cause logarithmically many
promotions but at most two rotations.
Deletion. First nd the node that is to be removed. If
necessary, we substitute the inorder successor for so we
can assume that both children of are leaves. If is last
in inorder we substitute symmetrically. Replace by a
leaf , as shown in Figure 24. If the incoming edge of is
red then change it to black. Otherwise, remember the in-
coming edge of as double-black, which counts as two
black edges. Similar to insertions, it helps to understand
the deletion algorithm in terms of a property it maintains.
INVARIANT D. The only possible violation of the red-
black tree properties is a double-black incoming edge
of .

Figure 24: Deletion of node . The dashed edge counts as two
black edges when we compute the black depth.
Note that Invariant D holds right after we remove . We
now present the analysis of all the possible cases. The ad-
justment operation is chosen depending on the local neigh-
borhood of .
Case 1. The incoming edge of is black. Done.
Case 2. The incoming edge of is double-black. Let
be the parent and the sibling of . Assume is
left child of and note that is internal.
Case 2.1. The edge from to is black.
Case 2.1.1. Both outgoing edges of are
black, as in Figure 25. Demote . Recurse
for = .
Figure 25: Demotion of .

is red, as in Figure 26 to the left. Change
the color of that edge to black and left ro-
tate . Done.

Figure 26: Left rotation of to the left and double left rotation
of to the right.
is black, as in Figure 26 to the right.
Change the color of the left outgoing edge
to black and double left rotate . Done.
Case 2.2. The edge from to is red, as in Fig-
ure 27. Left rotate . Recurse for .
24
Figure 27: Left rotation of .

Case 2 has a symmetric case in which is the right child of
. Case 2.2 seems problematic because it recurses without
moving any closer to the root. However, the congura-
tion excludes the possibility of Case 2.2 occurring again.
If we enter Cases 2.1.2 or 2.1.3 then the termination is im-
mediate. If we enter Case 2.1.1 then the termination fol-
lows because the incoming edge of is red. The deletion
may cause logarithmically many demotions but at most
three rotations.
Summary. The red-black tree is an implementation
of the dictionary data type and supports the operations
search, insert, delete in logarithmic time each. An inser-
tion or deletion requires the equivalent of at most three
single rotations. The red-black tree also supports nding
the minimum, maximumand the inorder successor, prede-
cessor of a given node in logarithmic time each.
25

7 Red-Black Trees: Dictionary Data Type, Which Requires Support For

Uploaded by

Copyright:

Available Formats

7 Red-Black Trees: Dictionary Data Type, Which Requires Support For

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

7 Red-Black Trees: Dictionary Data Type, Which Requires Support For

Uploaded by

Copyright:

Available Formats

7 Red-Black Trees

Binary search trees are an elegant implementation of the

Figure 22: Promotion of . (The colors of the outgoing edges of

Figure 25: Demotion of .

Figure 27: Left rotation of .

You might also like