Splay Tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time(amortized analysis is a method for analyzing a given algorithm's time complexity). For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre 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 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.
Operations to be performed on Splay Tree:
Splaying:
When a node
'x' is accessed, a splay operation is performed on
'x' to move it to the root. To perform a splay operation we carry out 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 that we achieve 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 (the grandparent of x).
It is important to remember to set 'gg' (the great-grandparent of 'x') to now point to 'x' after any splay operation. If 'gg' is null, then 'x' obviously is now the root and must be updated as such.
There are three types of splay steps, each of which has a left- and right-handed case. For the sake of brevity, only one of these two is shown for each type.
These three types are:
1. 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 and 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.
2. 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. Note that 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.
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.
- Splay the newly inserted node x to the top of the tree.
Alternative Method:
- 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 (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then 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.
Alternative Method:
- 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.
Search:
The search operation in Splay tree does the standard BST search, in addition to search, it also splays (move a node to the root). If the search is successful, then the node that is found is splayed and becomes the new root. Else the last node accessed prior to reaching the NULL is splayed and becomes the new root.
There are following cases for the node being accessed:
1)When Node is root We simply return the root, don’t do anything else as the accessed node is already root.
2) Zig: When Node is child of root (the node has no grandparent). Node is either a left child of root (we do a right rotation) or node is a right child of its parent (we do a left rotation).
T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side)
y x
/ \ Zig (Right Rotation) / \
x T3 – - – - – - – - - -> T1 y
/ \ < - - - - - - - - - / \
T1 T2 Zag (Left Rotation) T2 T3
3) When Node has both parent and grandparent.There can be following subcases:
Node is left child of parent and parent is also left child of grand parent (Two right rotations) OR node is right child of its parent and parent is also right child of grand parent (Two Left Rotations).
Zig-Zig (Left Left Case):
G P X
/ \ / \ / \
P T4 rightRotate(G) X G rightRotate(P) T1 P
/ \ ============> / \ / \ ============> / \
X T3 T1 T2 T3 T4 T2 G
/ \ / \
T1 T2 T3 T4
Zag-Zag (Right Right Case):
G P X
/ \ / \ / \
T1 P leftRotate(G) G X leftRotate(P) P T4
/ \ ============> / \ / \ ============> / \
T2 X T1 T2 T3 T4 G T3
/ \ / \
T3 T4 T1 T2
Node is left child of parent and parent is right child of grand parent (Left Rotation followed by right rotation) OR node is right child of its parent and parent is left child of grand parent (Right Rotation followed by left rotation).Zig-Zag (Left Right Case):
G G X
/ \ / \ / \
P T4 leftRotate(P) X T4 rightRotate(G) P G
/ \ ============> / \ ============> / \ / \
T1 X P T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
Zag-Zig (Right Left Case):
G G X
/ \ / \ / \
T1 P rightRotate(P) T1 X leftRotate(P) G P
/ \ =============> / \ ============> / \ / \
X T4 T2 P T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Example:
100 100 [20]
/ \ / \ \
50 200 50 200 50
/ search(20) / search(20) / \
40 ======> [20] ========> 30 100
/ 1. Zig-Zig \ 2. Zig-Zig \ \
30 at 40 30 at 100 40 200
/ \
[20] 40
The important thing to note is, the search or splay operation not only brings the searched key to root, but also balances the BST. For example in above case, height of BST is reduced by 1.
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(n), with the average being O(log n). 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.
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.
- Possibility of creating a persistent data structure version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in functional programming, and requires amortized O(log n) space per update.
- Working well with nodes containing identical keys—contrary to other types of self-balancing trees. Even with identical keys, performance remains amortized O(log n). All tree operations preserve the order of the identical nodes within the tree, which is a property similar to stable sorting algorithms. A carefully designed find operation can return the leftmost or rightmost node of a given key.
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 an operation can be high. However the amortized access cost of this worst case is logarithmic, O(log n). Also, the expected access cost can be reduced to O(log n) by using a randomized variant.
The representation of splay trees can change even when they are accessed in a 'read-only' manner (i.e. by find operations). 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 they can be used in limited ways to implement priority queues even there.
Summary
- Splay trees have excellent locality properties. Frequently accessed items are easy to find. Infrequent items are out of way.
- All splay tree operations take O(Log(n)) time on average. Splay trees can be rigorously shown to run in O(log n) average time per operation, over any sequence of operations (assuming we start from an empty tree)
- Splay trees are simpler compared to AVL and Red-Black Trees as no extra field is required in every tree node.
- Unlike AVL tree, a splay tree can change even with read-only operations like search.
