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

Thus it contains the root of the left tree at the end of the top-down search.
Similarly, the header's left link eventually contains the root of the right tree.
The header variable is not local because we want to allocate it only once over
the entire sequence of splays.
Before the reassembly at the end of the splay, header.left and header.right
reference R and L, respectively (this is not a typo—follow the links). Note that we
are using the simplified top-down splay. The find method, shown in Figure 22.18,
completes the implementation of the splay tree.

comparison of the splay tree
with other search trees

22.7

The implementation just presented suggests that splay trees are not as compli-
cated as red-black trees and almost as simple as AA-trees. Are they worth
using? The answer has yet to be resolved completely, but if the access patterns
are nonrandom, splay trees seem to perform well in practice. Some properties
relating to their performances also can be proved analytically. Nonrandom
accesses include those that follow the 90-10 rule, as well as several special
cases such as sequential access, double-ended access, and apparently access
patterns that are typical of priority queues during some types of event simula-
tions. In the exercises you are asked to examine this question in more detail.
Splay trees are not perfect. One problem with them is that the find opera-
tion is expensive because of the splay. Hence when access sequences are ran-
dom and uniform, splay trees do not perform as well as other balanced trees.

1 /**
2 * Find an item in the tree.
3 * @param x the item to search for.
4 * @return the matching item or null if not found.
5 */
6 public AnyType find( AnyType x )
7 {
8 root = splay( x, root );
9
10 if( isEmpty( ) || root.element.compareTo( x ) != 0 )
11 return null;
12
13 return root.element;
14 }

figure 22.18
The find routine, for
top-down splay trees