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

1. T has two black children: Flip colors (Figure 19.50).

2. T has an outer red child: Perform a single rotation (Figure 19.51).

3. T has an inner red child: Perform a double rotation (Figure 19.52).

Examination of the rotations shows that if T has two red children, either a
single rotation or double rotation will work (so it makes sense to do the single
rotation). Note that, if X is a leaf, its two children are black, so we can always
apply one of these three mechanisms to make X red.
Second, suppose that one of X 's children is red. Because the rotations in
the first main case always color X red, if X has a red child, consecutive red
nodes would be introduced. Thus we need an alternative solution. In this case,
we fall through to the next level, obtaining a new X, T, and P . If we are lucky,
we will fall onto a red node (we have at least a 50 percent chance that this will

figure 19.50
X has two black
children, and both of
its sibling's children
are black; do a color
flip.

P P

X T X T

figure 19.51
X has two black
children, and the outer
child of its sibling is
red; do a single
rotation.

P T

X T P R

R X

figure 19.52
X has two black
children, and the inner
child of its sibling is
red; do a double
rotation.

P R

X T P T

R X