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

19.5.2 top-down red-black trees

To avoid the possibility of having to rotate up the tree, we apply a top-down
procedure as we are searching for the insertion point. Specifically, we guaran-
tee that, when we arrive at a leaf and insert a node, S is not red. Then we can
just add a red leaf and if necessary use one rotation (either single or double).
The procedure is conceptually easy.
On the way down, when we see a node X that has two red children, we
make X red and its two children black. Figure 19.38 shows this color flip. (If X
is the root, it will be made red by this process. We could then recolor it back to
black, without violating any red-black tree properties.) The number of black
nodes on paths below X remains unchanged. However, if X 's parent is red, we
would introduce two consecutive red nodes. But in this case, we can apply
either the single rotation in Figure 19.35 or the double rotation in
Figure 19.36. But what if X 's parent's sibling is also red? This situation can-
not happen. If on the way down the tree, we see a node Y that has two red chil-
dren, we know that Y 's grandchildren must be black. And as Y 's children are
also made black via the color flip—even after the rotation that may occur—
we would not see another red node for two levels. Thus when we see X, if X 's
parent is red, X 's parent's sibling cannot also be red.
For example, suppose that we want to insert 45 in the tree shown in
Figure 19.34. On the way down the tree we see node 50, which has two red
children. Thus we perform a color flip, making 50 red and 40 and 55 black.
The result is shown in Figure 19.39. However, now 50 and 60 are both red.

To avoid iterating
back up the tree,
we ensure as we
descend the tree
that the sibling's
parent is not red.
We can do so with
color flips and/or
rotations.

figure 19.38
Color flip: Only if X 's
parent is red do we
continue with a
rotation.

X X

C1 C2 C1 C2

(a) Before color flip (b) After color flip

figure 19.39
A color flip at 50
induces a violation;
because the violation
is outside, a single
rotation fixes it.

30

15 70

10 20 60 85

5 50 65 80 90

40 55