Splay tree


A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. 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.
All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. 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.

Advantages

Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is O, with the average being O.
Having frequently-used nodes near the root is an advantage for many practical applications, and is particularly useful for implementing caches and garbage collection algorithms.
Advantages include:
  • Comparable performance: Average-case performance is as efficient as other trees.
  • Small memory footprint: Splay trees do not need to store any bookkeeping data.

    Disadvantages

The most significant disadvantage of splay trees is that the height of a splay tree can be linear. For example, this will be the case after accessing all n elements in non-decreasing order. 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. However the amortized access cost of this worst case is logarithmic, O. Also, the expected access cost can be reduced to O by using a randomized variant.
The representation of splay trees can change even when they are accessed in a 'read-only' manner. This complicates the use of such splay trees in a multi-threaded environment. 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.

Operations

Splaying

When a node x is accessed, a splay operation is performed on x to move it to the root. A splay operation is a sequence of splay steps, each of which moves x closer 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.
Each particular step depends on three factors:
  • Whether x is the left or right child of its parent node, p,
  • whether p is the root or not, and if not
  • whether p is the left or right child of its parent, g.
There are three types of splay steps, each of which has two symmetric variants: left- and right-handed. For the sake of brevity, only one of these two is shown for each type. The three types of splay steps are:
Zig step: this step is done when p is the root. The tree is rotated on the edge between x and p. Zig steps exist to deal with the parity issue, will be done only as the last step in a splay operation, and only when x has odd depth at the beginning of the operation.
Zig-zig step: this step is done when p is not the root and x and p are either both right children or are both left children. The picture below shows the case where x and p are both left children. The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p. Zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro prior to the introduction of splay trees.
center
Zig-zag step: this step is done when p is not the root and x is a right child and p is a left child or vice versa. The tree is rotated on the edge between p and x, and then rotated on the resulting edge between x and g.
center

Join

Given two trees S and T such that all elements of S are smaller than the elements of T, the following steps can be used to join them to a single tree:
  • Splay the largest item in S. Now this item is in the root of S and has a null right child.
  • Set the right child of the new root to T.

    Split

Given a tree and an element x, return two new trees: one containing all elements less than or equal to x and the other containing all elements greater than x. This can be done in the following way:
  • Splay x. Now it is in the root so the tree to its left contains all elements smaller than x and the tree to its right contains all element larger than x.
  • Split the right subtree from the rest of the tree.

    Insertion

To insert a value x into a splay tree:
  • Insert x as with a normal binary search tree.
  • Perform a splay on x.
As a result, the newly inserted node x becomes the root of the tree.
Alternatively:
  • Use the split operation to split the tree at the value of x to two sub-trees: S and T.
  • Create a new tree in which x is the root, S is its left sub-tree and T its right sub-tree.

    Deletion

To delete a node x, use the same method as with a binary search tree:
  • If x has two children:
  • * Swap its value with that of either the rightmost node of its left sub tree or the leftmost node of its right subtree.
  • * Remove that node instead.
In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.
Alternatively:
  • The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. leaves the tree with two sub trees.
  • The two sub-trees are then joined using a "join" operation.

    Implementation and variants

Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node. It is possible to record the access path during the first pass for use during the second, but that requires extra space during the access operation. 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.
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. This top-down splaying routine uses three sets of nodes – left tree, right tree and middle tree. The first two contain all items of original tree known to be less than or greater than current item respectively. 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.
Below there is an implementation of splay trees in C++, which uses pointers to represent each node on the tree. This implementation is based on bottom-up splaying version and uses the second method of deletion on a splay tree. Also, unlike the above definition, this C++ version does not splay the tree on finds – it only splays on insertions and deletions, and the find operation, therefore, has linear time complexity.

  1. include
  2. ifndef SPLAY_TREE
  3. define SPLAY_TREE
template>
class splay_tree ;
  1. endif // SPLAY_TREE

Analysis

A simple amortized analysis of static splay trees can be carried out using the potential method. Define:
  • size = the number of nodes in the sub-tree rooted at node r.
  • rank = log2.
  • Φ = the sum of the ranks of all the nodes in the tree.
Φ will tend to be high for poorly balanced trees and low for well-balanced trees.
To apply the potential method, we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation.

Zig step

Zig-zig step

Zig-zag step

The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence:
When summed over the entire splay operation, this telescopes to 1 + 3−rank) which is O, since we use The Zig operation at most once and the amortized cost of zig is at most 1+3−rank).
So now we know that the total amortized time for a sequence of m operations is:
To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done to the final state after all operations are completed.
where the big O notation can be justified by the fact that for every node x, the minimum rank is 0 and the maximum rank is log.
Now we can finally bound the actual time: