CSC 378: Data Structures and Algorithm Analysis

Splay Trees

[ L & D pg 243 - 251 ]

A splay tree is a BST which is not necessarily balanced.

Operations on a splay tree of n nodes can take worst-case time in . However, a sequence of operations takes worst-case time in .

This means that the average time of one operation is . Also this guarantees an upper bound on the total time for a sequence of operations. So this is a stronger statement than one that gives only an average time per operation.

Splay Tree Operations

The operations supported by a splay tree are:

`Member(k,S)`
`Insert(x,S)`
`Delete(k,S)`
`Join(S,S')`	Join S and S' into a single BST, assuming that .
`Split(S,S',S'')`	Split S into two trees, S' and S'', such that .

Everything is based on the Splay operation:

`Splay(k,S)`	Reorganize S such that k is in the root or, if k is not in S, the root is either or .

Here's how the operations are written in terms of Splay:

`Member(k,S)`	Do `Splay(k,S)`. If k is in S, k is now the root.
`Insert(x,S)`	Do `Split(k,S,S',S'')` to get S' and S''. Make x the root and set `left(x) = S'` and `right(x) = S''`.
`Delete(k,S)`	Do `Splay(k,S)`, then `Join(left(S), right(S)).`
`Join(S,S')`	Do `Splay( ,S)`. This yields Then do `right(S) = S'`, which results in
`Split(k,S,S',S'')`	Do `Splay(k,S)`: Then S' is S + left(S) and S'' is right(S).

Note the each operation takes a constant number of splay operations, plus some constant number of minor operations, like pointer manipulation. So we'll only count the cost of Splay operations in analysis.

The Splay Operation

Let x be a node with key k. Splay(k,S) uses rotations to move x up to the root.

The obvious way is to keep rotating at the node containing k until it reaches the root. But if this is done, a sequence of m operations can take time in , rather than as claimed above.

So we must carefully choose the rotations that move a node up to the root.

Each time we move the node upward, we're faced with one of the following situations:

If x has a parent but no grandparent, just Rotate(x).
If x and its parent y are both left or both right children, first Rotate(y), then Rotate(x).
If one of x and its parent is a left child and the other is a right child, first Rotate(x), then Rotate(x) again.

The operations produce the restructurings:

Here is an example in which we Splay(5,S):

Analysis

The amortized analysis of the splay operation is quite involved. Those interested in it can find a clear presentation in The Design and Analysis of Algorithms, by Dexter Kozen, pages 58 to 64 (ISBN 0-387-97687-6, Springer Verlag, 1992).