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

1 package weiss.nonstandard;
2
3 // SplayTree class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // void insert( x ) --> Insert x
9 // void remove( x ) --> Remove x
10 // Comparable find( x ) --> Return item that matches x
11 // boolean isEmpty( ) --> Return true if empty; else false
12 // void makeEmpty( ) --> Remove all items
13 // ******************ERRORS********************************
14 // Exceptions are thrown by insert and remove if warranted
15
16 public class SplayTree<AnyType extends Comparable<AnyType>>
17 {
18 public SplayTree( )
19 { /* Figure 22.14 */ }
20
21 public void insert( AnyType x )
22 { /* Figure 22.15 */ }
23 public void remove( AnyType x )
24 { /* Figure 22.16 */ }
25 public AnyType find( AnyType x )
26 { /* Figure 22.18 */ }
27
28 public void makeEmpty( )
29 { root = nullNode; }
30 public boolean isEmpty( )
31 { return root == nullNode; }
32
33 private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
34 { /* Figure 22.17 */ }
35
36 private BinaryNode<AnyType> root;
37 private BinaryNode<AnyType> nullNode;
38 }
figure 22.13
The top-down SplayTree class skeleton
we maintain a nullNode sentinel. We allocate and initialize the sentinel in
the constructor, as shown in Figure 22.14.
Figure 22.15 shows the method for insertion of an item x . A new node
( newNode ) is allocated, and if the tree is empty, a one-node tree is created. Oth-
erwise, we splay around x . If the data in the tree's new root equal x , we have a
duplicate. In this case, we do not want to insert x ; we throw an exception
instead at line 39. We use an instance variable so that the next call to insert