Splay tree

According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern.

The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.

One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top.

Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.

Having frequently-used nodes near the root is an advantage for many practical applications (also see locality of reference), and is particularly useful for implementing caches and garbage collection algorithms.

Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of a single operation can be high.

Also, the expected access cost can be reduced to O(log n) by using a randomized variant.

[4] The representation of splay trees can change even when they are accessed in a 'read-only' manner (i.e. by find operations).

Specifically, extra management is needed if multiple threads are allowed to perform find operations concurrently.

This also makes them unsuitable for general use in purely functional programming, although even there they can be used in limited ways to implement priority queues.

Finally, when the access pattern is random, the additional splaying overhead adds a significant constant factor to the cost compared to less-dynamic alternatives.

When a node x is accessed, a splay operation is performed on x to move it to the root.

By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so it provides the desired amortized time bounds.

(In the following diagrams, circles indicate nodes of interest and triangles indicate sub-trees of arbitrary size.)

Alternatively: Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node.

Another alternative is to keep a parent pointer in every node, which avoids the need for extra space during access operations but may reduce overall time efficiency because of the need to update those pointers.

[1] Another method which can be used is based on the argument that the tree can be restructured during the way down the access path instead of making a second pass.

The middle tree consists of the sub-tree rooted at the current node.

These three sets are updated down the access path while keeping the splay operations in check.

Another method, semisplaying, modifies the zig-zig case to reduce the amount of restructuring done in all operations.

A simple amortized analysis of static splay trees can be carried out using the potential method.

The same analysis applies and the amortized cost of a splaying operation is again: where W is the sum of all weights.

The decrease from the initial to the final potential is bounded by: since the maximum size of any single node is W and the minimum is w(x).

Hence the actual time is bounded by: There are several theorems and conjectures regarding the worst-case runtime for performing a sequence S of m accesses in a splay tree containing n elements.

[1] Another way of stating the same result is that, on input sequences where the items are drawn independently at random from a non-uniform probability distribution on n items, the amortized expected (average case) cost of each access is proportional to the entropy of the distribution.

[8] Static Finger Theorem — Assume that the items are numbered from 1 through n in ascending order.

[12] In addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original Sleator and Tarjan paper.

There are several corollaries of the dynamic optimality conjecture that remain unproven: In order to reduce the number of restructuring operations, it is possible to replace the splaying with semi-splaying, in which an element is splayed only halfway towards the root.

[1] The CBTree augments the splay tree with access counts at each node and uses them to restructure infrequently.

This is used along with an optimistic hand-over-hand validation scheme to make a concurrent self-adjusting tree.