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

basic splay tree operations

22.3

As mentioned earlier, a splay operation is performed after each access. When
an insertion is performed, we perform a splay. As a result, the newly inserted
item becomes the root of the tree. Otherwise, we could spend quadratic time
constructing an N item tree.

After an item has
been inserted as a
leaf, it is splayed to
the root.

For the find , we splay at the last node accessed during the search. If the
search is successful, the node found is splayed and becomes the new root. If
the search is unsuccessful, the last node accessed prior to reaching the null
reference is splayed and becomes the new root. This behavior is necessary
because, otherwise, we could repeatedly perform a find for 0 in the initial tree
in Figure 22.7 and use linear time per operation. Likewise, operations such as
findMin and findMax perform a splay after the access.
The interesting operations are the deletions. Recall that the deleteMin and
deleteMax are important priority queue operations. With splay trees, these
operations become simple. We can implement deleteMin as follows. First, we
perform a findMin . This brings the minimum item to the root, and by the
binary search tree property, there is no left child. We can use the right child as
the new root. Similarly, deleteMax can be implemented by calling findMax and
setting the root to the post-splay root's left child.

All searching oper-
ations incorporate a
splay.

Even the remove operation is simple. To perform deletion, we access the
node to be deleted, which puts the node at the root. If it is deleted, we get two
subtrees, L and R (left and right). If we find the largest element in L, using a
findMax operation, its largest element is rotated to L 's root and L 's root has no
right child. We finish the remove operation by making R the right child of L 's
root. An example of the remove operation is shown in Figure 22.8.
The cost of the remove operation is two splays. All other operations cost
one splay. Thus we need to analyze the cost of a series of splay steps. The next
section shows that the amortized cost of a splay is at most 3 log N + 1 single
rotations. Among other things, this means we do not have to worry that the
remove algorithm described previously is biased. The splay tree's amortized

Deletion opera-
tions are much sim-
pler than usual.
They also contain a
splaying step
(sometimes two).

figure 22.8
The remove operation
applied to node 6:
First, 6 is splayed to
the root, leaving two
subtrees; a findMax is
performed on the left
subtree, raising 5 to
the root of the left
subtree; then the right
subtree can be
attached (not shown).

4 6 5

2 6 4 7 4 7

4 7

1 5 7 2 5 2

2 5

1 1

1