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

it simplifies the remove algorithm by removing an annoying case. That is, if an
internal node has only one child, the child must be a red right child because
red left children are now illegal, whereas a single black child would violate
property 4 for red-black trees. Thus we can always replace an internal node
with the smallest node in its right subtree. That smallest node is either a leaf
or has a red child and can be easily bypassed and removed.

To simplify the implementation further, we represent balance information
in a more direct way. Instead of storing a color with each node, we store the
node's level. The level of a node represents the number of left links on the
path to the nullNode sentinel and is

The level of a node
in an AA-tree rep-
resents the num-
ber of left links on
the path to the
nullNode sentinel.

Level 1, if the node is a leaf

n

The level of its parent, if the node is red

n

One less than the level of its parent, if the node is black

n

The result is an AA-tree. If we translate the structure requirement from
colors to levels, we know that the left child must be one level lower than its
parent and that the right child may be zero or one level lower than its parent
(but not more). A horizontal link is a connection between a node and a child
of equal levels. The coloring properties imply

A horizontal link in
an AA-tree is a
connection
between a node
and a child of equal
levels. A horizontal
link should go only
to the right, and
there should not be
two consecutive
horizontal links.

1. Horizontal links are right links (because only right children may be

red)

2. There may not be two consecutive horizontal links (because there

cannot be consecutive red nodes)

3. Nodes at level 2 or higher must have two children

4. If a node does not have a right horizontal link, its two children are at

the same level

Figure 19.54 shows a sample AA-tree. The root of this tree is the node
with key 30. Searching is done with the usual algorithm. And as usual, insert
and remove are more difficult because the natural binary search tree algorithms
may induce a violation of the horizontal link properties. Not surprisingly, tree
rotations can fix all the problems encountered.

figure 19.54
AA-tree resulting from
the insertion of 10,
85, 15, 70, 20, 60, 30,
50, 65, 80, 90, 40, 5,
55, and 35

30

70

15 50 60 85

5 10 20 35 40 55 65 80 90