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

pair. The skew at 70 removes the left horizontal link at the top level but cre-
ates consecutive right horizontal nodes, as shown in Figure 19.61. When the
final split is applied, the consecutive horizontal nodes are removed and 50
becomes the new root of the tree. The result is shown in Figure 19.62.

19.6.2 deletion

For general binary search trees, the remove algorithm is broken into three
cases: The item to be removed is a leaf, has one child, or has two children.
For AA-trees, we treat the one-child case the same way as the two-child
case because the one-child case can occur only at level 1. Moreover, the
two-child case is also easy because the node used as the replacement value
is guaranteed to be at level 1 and at worst has only a right horizontal link.
Thus everything boils down to being able to remove a level-1 node. Clearly,
this action might affect the balance (consider, for instance, the removal of
20 in Figure 19.62).
We let T be the current node and use recursion. If the deletion has altered
one of T 's children to two less than T 's level, T 's level needs to be lowered
also (only the child entered by the recursive call could actually be affected,
but for simplicity we do not keep track of it). Furthermore, if T has a horizontal
right link, its right child's level must also be lowered. At this point, we could
have six nodes on the same level: T, T 's horizontal right child R, R 's two

Deletion is made
easier because the
one-child case
can occur only at
level 1 and we are
willing to use
recursion.

figure 19.61
After skew at 70;
consecutive horizontal
links are introduced,
starting at 30.

30 50 70

15 40 60 85

5 10 20 35 45 55 65 80 90

figure 19.62
After split at 30; the
insertion is complete.

50

30 70

15 40 60 85

5 10 20 35 45 55 65 80 90