Balanced Search Trees - Data Structures and Abstractions with Java - page 715

Now suppose that the red-black tree had two nodes before we added the new entry e .
Figure 27-31a shows this original tree when it consists of a root x and right child y . Also pictured is
the 2-4 tree that is equivalent to the original red-black tree. The rest of the figure shows the possible
outcomes of the addition, depending on how e compares with x and y . In Part b , e is the left child of
the root, and we are done. In Part c , a red node has a red child. These two consecutive red nodes are
illegal in a red-black tree (properties 2 and 3). To understand what further action is necessary, con-
sider the equivalent 2-4 tree. The original 2-node red-black tree is equivalent to the 2-4 tree that
contains the one node < x y > (Figure 27-31a). If we add an entry e that is larger than y , the 2-4 tree
becomes the single node < x y e > (Figure 27-31c). Notice the red-black tree that is equivalent to this
3-node. This tree is the one we need as the result of adding e . We can get it from the first red-black
tree shown in Part c by first performing a single left rotation about the node containing y . You have
seen this rotation before in Figures 27-5b and 27-5c when we talked about AVL trees. After the
rotation, we need to reverse the colors of the nodes containing x and y —that is, the original parent
and grandparent of the new node. We call this step a color flip .

FIGURE 27-31

The possible results of adding a new entry e to a two-node
red-black tree

Red-black tree

Equivalent 2-4 tree

(a) Before addition

x x y

y

Action after addition
to transform
column 1 into column 3

After adding e to
the red-black tree

After adding e to
the 2-4 tree

Red-black equivalent
of the 2-4 tree

None

(b) Case 1:
The tree is balanced

x e x y

x

e y e y

(c) Case 2:
A red node has a
red right child

Single left rotation
and color flip

x

x y e y

y

x e

e

(d) Case 3:
A red node has a
red left child

Right-left double
rotation and color flip

x x e y

e

y

x y

e

Figure 27-31d shows the last possible result of adding e to the two-node red-black tree. Here, a
right-left double rotation followed by a color flip of the new node and its original grandparent are
necessary to avoid two consecutive red nodes. Figures 27-7b, 27-7c, and 27-7d show the rotation in
general in the context of an AVL tree.
Figure 27-32 shows mirror images of the cases in Figure 27-31.