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

1 /**
2 * Internal routine that performs a single or double rotation.
3 * Because the result is attached to the parent, there are 4 cases.
4 * Called by handleReorient.
5 * @param item the item in handleReorient.
6 * @param parent the parent of the root of the rotated subtree.
7 * @return the root of the rotated subtree.
8 */
9 private RedBlackNode<AnyType>
10 rotate( AnyType item, RedBlackNode<AnyType> parent )
11 {
12 if( compare( item, parent ) < 0 )
13 return parent.left = compare( item, parent.left ) < 0 ?
14 rotateWithLeftChild( parent.left ) : // LL
15 rotateWithRightChild( parent.left ) ; // LR
16 else
17 return parent.right = compare( item, parent.right ) < 0 ?
18 rotateWithLeftChild( parent.right ) : // RL
19 rotateWithRightChild( parent.right ); // RR
20 }

figure 19.49
A routine for performing an appropriate rotation

19.5.4 top-down deletion

Deletion in red-black trees can also be performed top-down. Needless to say,
an actual implementation is fairly complicated because the remove algorithm
for unbalanced search trees is nontrivial in the first place. The normal binary
search tree deletion algorithm removes nodes that are leaves or have one
child. Recall that nodes with two children are never removed; their contents
are simply replaced.

If the node to be deleted is red, there is no problem. However, if the node
to be deleted is black, its removal will violate property 4. The solution to the
problem is to ensure that any node we are about to delete is red.
Throughout this discussion, we let X be the current node, T be its sibling,
and P be their parent. We begin by coloring the sentinel root red. As we
traverse down the tree, we attempt to ensure that X is red. When we arrive at a
new node, we are certain that P is red (inductively, by the invariant that we are
trying to maintain) and that X and T are black (because we cannot have two
consecutive red nodes). There are two main cases, along with the usual sym-
metric variants (which are omitted).
First, suppose that X has two black children. There are three subcases,
which depend on T 's children.

Deletion is fairly
complex. The basic
idea is to ensure
that the deleted
node is red.