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

private BinaryNode<AnyType> header = new BinaryNode<AnyType>( null );

1

2
3 /**
4 * Internal method to perform a top-down splay.
5 * The last accessed node becomes the new root.
6 * @param x the target item to splay around.
7 * @param t the root of the subtree to splay.
8 * @return the subtree after the splay.
9 */
10 private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
11 {
12 BinaryNode<AnyType> leftTreeMax, rightTreeMin;
13
14 header.left = header.right = nullNode;
15 leftTreeMax = rightTreeMin = header;
16
17 nullNode.element = x; // Guarantee a match
18
19 for( ; ; )
20 if( x.compareTo( t.element ) < 0 )
21 {
22 if( x.compareTo( t.left.element ) < 0 )
23 t = Rotations.rotateWithLeftChild( t );
24 if( t.left == nullNode )
25 break;
26 // Link Right
27 rightTreeMin.left = t;
28 rightTreeMin = t;
29 t = t.left;
30 }
31 else if( x.compareTo( t.element ) > 0 )
32 {
33 if( x.compareTo( t.right.element ) > 0 )
34 t = Rotations.rotateWithRightChild( t );
35 if( t.right == nullNode )
36 break;
37 // Link Left
38 leftTreeMax.right = t;
39 leftTreeMax = t;
40 t = t.right;
41 }
42 else
43 break;
44
45 leftTreeMax.right = t.left;
46 rightTreeMin.left = t.right;
47 t.left = header.right;
48 t.right = header.left;
49 return t;
50 }

figure 22.17
A top-down splay algorithm