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

19.6.1 insertion

Insertion of a new item is always done at the bottom level. As usual, that may
create problems. In the tree shown in Figure 19.54, insertion of 2 would create
a horizontal left link, whereas insertion of 45 would generate consecutive
right links. Consequently, after a node has been added at the bottom level, we
may need to perform some rotations to restore the horizontal link properties.

Insertion is done by
using the usual
recursive algorithm
and two method
calls.

In both cases, a single rotation fixes the problem. We remove left horizon-
tal links by rotating between the node and its left child, a procedure called
skew . We fix consecutive right horizontal links by rotating between the first
and second (of the three) nodes joined by the two links, a procedure called
split .
The skew procedure is illustrated in Figure 19.55, and the split procedure
is illustrated in Figure 19.56. Although a skew removes a left horizontal link, it
might create consecutive right horizontal links because X 's right child might
also be horizontal. Thus we would process a skew first and then a split . After a
split , the middle node increases in level. That may cause problems for the
original parent of X by creating either a left horizontal link or consecutive right
horizontal links: Both problems can be fixed by applying the skew / split strat-
egy on the path up toward the root. It can be done automatically if we use
recursion, and a recursive implementation of insert is only two method calls
longer than the corresponding unbalanced search tree routine.

Left horizontal links
are removed by a
skew (rotation
between a node
and its left child).
Consecutive right
horizontal links are
fixed by a split
(rotation between a
node and its right
child). A skew pre-
cedes a split .

figure 19.55
The skew procedure is
a simple rotation
between X and P .

P X P X

A B C A B C

figure 19.56
The split procedure
is a simple rotation
between X and R ;
note that R 's level
increases.

R

X R G X G

A B A B