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

1 /**
2 * Construct the tree.
3 */
4 public SplayTree( )
5 {
6 nullNode = new BinaryNode<AnyType>( null );
7 nullNode.left = nullNode.right = nullNode;
8 root = nullNode;
9 }

figure 22.14
The SplayTree class
constructor

1 // Used between different inserts
2 private BinaryNode<AnyType> newNode = null;
3
4 /**
5 * Insert into the tree.
6 * @param x the item to insert.
7 * @throws DuplicateItemException if x is already present.
8 */
9 public void insert( AnyType x )
10 {
11 if( newNode == null )
12 newNode = new BinaryNode<AnyType>( null );
13 newNode.element = x;
14
15 if( root == nullNode )
16 {
17 newNode.left = newNode.right = nullNode;
18 root = newNode;
19 }
20 else
21 {
22 root = splay( x, root );
23 if( x.compareTo( root.element ) < 0 )
24 {
25 newNode.left = root.left;
26 newNode.right = root;
27 root.left = nullNode;
28 root = newNode;
29 }
30 else
31 if( x.compareTo( root.element ) > 0 )
32 {
33 newNode.right = root.right;
34 newNode.left = root;
35 root.right = nullNode;
36 root = newNode;
37 }
38 else
39 throw new DuplicateItemException( x.toString( ) );
40 }
41 newNode = null; // So next insert will call new
42 }

figure 22.15
The top-down
SplayTree class
insertion routine