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

To show the algorithm in action, we insert 45 in the AA-tree shown in
Figure 19.54. In Figure 19.57, when 45 is added at the bottom level, consec-
utive horizontal links form. Then skew / split pairs are applied as necessary
from the bottom up toward the root. Thus, at node 35 a split is needed
because of the consecutive horizontal right links. The result of the split is
shown in Figure 19.58. When the recursion backs up to node 50, we encounter
a horizontal left link. Thus we perform a skew at 50 to remove the horizontal
left link (the result is shown in Figure 19.59) and then a split at 40 to remove
the consecutive horizontal right links. The result after the split is shown in
Figure 19.60. The result of the split is that 50 is on level 3 and is a left
horizontal child of 70. Therefore we need to perform another skew / split

This is a rare algo-
rithm in that it is
harder to simulate
on paper than
implement on a
computer.

figure 19.57
After insertion of 45
in the sample tree;
consecutive horizontal
links are introduced,
starting at 35.

30

70

15 50 60 85

5 10 20 35 40 45 55 65 80 90

figure 19.58
After split at 35; a
left horizontal link at
50 is introduced.

30 70

15 40 50 60 85

5 10 20 35 45 55 65 80 90

figure 19.59
After skew at 50;
consecutive horizontal
nodes are introduced
starting at 40.

30 70

15 40 50 60 85

5 10 20 35 45 55 65 80 90

figure 19.60
After split at 40; 50
is now on the same
level as 70, inducing
an illegal left
horizontal link.

30 70

50

15 40 60 85

5 10 20 35 45 55 65 80 90