Binary search trees - Data Structures and Problem Solving Using Java - page 717

figure 19.36
If S is black, a double
rotation involving X ,
the parent, and the
grandparent, with
appropriate color
changes, restores
property 3 if X is an
inside grandchild.

G X

P S P G

A X D E A B C S

BC DE

(a) Before rotation (b) After rotation

nodes would be between P and one of its children or between G and C . But
the roots of A, B, and C must be black; otherwise, there would have been addi-
tional property 3 violations in the original tree. In the original tree, there is
one black node on the path from the subtree root to A, B, and C and two black
nodes on the paths to D and E . We can verify that this pattern holds after rota-
tion and recoloring.

So far so good. But what happens if S is red, as when we attempt to insert
79 in the tree shown in Figure 19.34? Then neither the single nor the double
rotation works because both result in consecutive red nodes. In fact, in this
case three nodes must be on the path to D and E and only one can be black.
Hence both S and the subtree's new root must be colored red. For instance, the
single rotation case that occurs when X is an outside grandchild is shown in
Figure 19.37. Although this rotation seems to work, there is a problem: What
happens if the parent of the subtree root (i.e., X 's original great grandparent)
is also red? We could percolate this procedure up toward the root until we no
longer have two consecutive red nodes or we reach the root (which would be
recolored black). But then we would be back to making a pass up the tree, as
in the AVL tree.

If the parent's sib-
ling is red, then
after we fix things,
we induce consec-
utive red nodes at a
higher level. We
need to iterate up
the tree to fix
things.

figure 19.37
If S is red, a single
rotation between
parent and
grandparent, with
appropriate color
changes, restores
property 3 between X
and P .

G P

P S X G

X C D E A B C S

AB DE

(a) Before rotation (b) After rotation