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

19.5.1 bottom-up insertion

Recall that a new item is always inserted as a leaf in the tree. If we color a new
item black, we violate property 4 because we create a longer path of black
nodes. Thus a new item must be colored red. If the parent is black, we are
done; thus the insertion of 25 into the tree shown in Figure 19.34 is trivial. If
the parent is already red, we violate property 3 by having consecutive red
nodes. In this case, we have to adjust the tree to ensure that property 3 is
enforced and do so without introducing a violation of property 4. The basic
operations used are color changes and tree rotations.

We have to consider several cases (each with mirror-image symmetry)
if the parent is red. First, suppose that the sibling of the parent is black
(we adopt the convention that null nodes are black), which would apply
for the insertions of 3 or 8 but not for the insertion of 99. Let X be the
newly added leaf, P be its parent, S be the sibling of the parent (if it
exists), and G be the grandparent. Only X and P are red in this case; G is
black because otherwise there would be two consecutive red nodes prior to
the insertion—a violation of property 3. Adopting the AVL tree terminology,
we say that relative to G, X can be either an outside or inside node. 2 If X is
an outside grandchild, a single rotation of its parent and grandparent along
with some color changes will restore property 3. If X is an inside grand-
child, a double rotation along with some color changes are needed. The
single rotation is shown in Figure 19.35, and the double rotation is shown
in Figure 19.36. Even though X is a leaf, we have drawn a more general
case that allows X to be in the middle of the tree. We use this more general
rotation later in the algorithm.
Before continuing, consider why these rotations are correct. We need to
be sure that there are never two consecutive red nodes. As shown in
Figure 19.36, for instance, the only possible instances of consecutive red

New items must be
colored red. If the
parent is already
red, we must
recolor and/or
rotate to remove
consecutive red
nodes.

If the parent's sib-
ling is black, a
single or double
rotation fixes things,
as in an AVL tree.

figure 19.35
If S is black, a single
rotation between
parent and
grandparent, with
appropriate color
changes, restores
property 3 if X is an
outside grandchild.

G P

P S X G

C

X D E A B C S

A

B DE

(a) Before rotation (b) After rotation

2. See Section 19.4.1, page 707.