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

X P T

X T P C

B C B C X ′ B

figure 19.53
X is black, and at least one child is red; if we fall through to the next level and land on a red child, fine;
if not, we rotate a sibling and parent.

happen), thereby making the new current node red. Otherwise, we have the
situation shown in Figure 19.53. That is, the current X is black, the current T
is red, and the current P is black. We can then rotate T and P, thereby making
X 's new parent red; X and its new grandparent are black. Now X is not yet red,
but we are back to the starting point (although one level deeper). This out-
come is good enough because it shows that we can iteratively descend the
tree. Thus, so long as we eventually either reach a node that has two black
children or land on a red node, we are okay. This result is guaranteed for the
deletion algorithm because the two eventual states are

X is a leaf, which is always handled by the main case since X has two
black children.

n

X has only one child, for which the main case applies if the child is
black, and if it is red, we can delete X, if necessary, and make the
child black.

n

Lazy deletion, in which items are marked as deleted but not actually
deleted, is sometimes used. However, lazy deletion wastes space and compli-
cates other routines (see Exercise 19.23).

Lazy deletion is the
marking of items as
deleted.

aa-trees

19.6

Because of many possible rotations, the red-black tree is fairly tricky to code.
In particular, the remove operation is quite challenging. In this section we
describe a simple but competitive balanced search tree known as an AA-tree .
The AA-tree is the method of choice when a balanced tree is needed, a casual
implementation is acceptable, and deletions are needed. The AA-tree adds
one extra condition to the red-black tree: Left children may not be red.
This simple restriction greatly simplifies the red-black tree algorithms for
two reasons: First, it eliminates about half of the restructuring cases; second,

The AA-tree is the
method of choice
when a balanced
tree is needed, a
casual implementa-
tion is acceptable,
and deletions are
needed.