Splay trees - Data Structures and Problem Solving Using Java - page 863

can avoid calling new , in the case that the insert fails because of a duplicate
item. (Normally, we would not be so concerned with this exceptional case;
however, a reasonable alternative is to use a Boolean return value rather than
using exceptions.)
If the new root contains a value larger than x , the new root and its right
subtree become a right subtree of newNode , and the root's left subtree becomes
a left subtree of newNode . Similar logic applies if the new root contains a value
smaller than x . In either case, newNode is assigned to root to indicate that it is
the new root. Then we make newNode null at line 41 so that the next call to
insert will call new .
Figure 22.16 shows the deletion routine for splay trees. A deletion proce-
dure rarely is shorter than the corresponding insertion procedure. Next, is the
top-down splaying routine.
Our implementation, shown in Figure 22.17, uses a header with left and
right links to contain eventually the roots of the left and right trees. These
trees are initially empty; a header is used to correspond to the min or max
node of the right or left tree, respectively, in this initial state. In this way we
can avoid checking for empty trees. The first time the left tree becomes non-
empty, the header's right link is initialized and does not change in the future.

1 /**
2 * Remove from the tree.
3 * @param x the item to remove.
4 * @throws ItemNotFoundException if x is not found.
5 */
6 public void remove( AnyType x )
7 {
8 BinaryNode<AnyType> newTree;
9
10 // If x is found, it will be at the root
11 root = splay( x, root );
12 if( root.element.compareTo( x ) != 0 )
13 throw new ItemNotFoundException( x.toString( ) );
14
15 if( root.left == nullNode )
16 newTree = root.right;
17 else
18 {
19 // Find the maximum in the left subtree
20 // Splay it to the root; and then attach right child
21 newTree = root.left;
22 newTree = splay( x, newTree );
23 newTree.right = root.right;
24 }
25 root = newTree;
26 }

figure 22.16
The top-down
SplayTree class
deletion routine