|
In this article:
- What are Splay Trees
- Advantages and disadvantages of Splay Trees
What are Splay Trees
A splay tree is type of self-balancing binary search tree which has an additional feature which is absent in other self-balancing binary search trees that the elements in the tree that have been accessed recently can be accessed very quickly. The splay tree was invented by Daniel Sleator and Robert Tarjan. A splay tree takes O(log(n)) time to perform the operations like insertion, retrieval and removal of elements. A splay tree are better than other type of search trees in their operations when it comes to executing set or sets non-uniform operations.
A splay tree performs a particular operation which is called splaying (as the name Splay tree itself implies). Thus, every operation on a splay tree is accompanied with the splaying operation. When splaying is to be done, the elements in the tree are rearranged such that a certain element is placed at the root of the tree. There exist various methods to achieve this. For example, first, that particular element maybe searched for in the tree by using the usual search method. Then, all the elements maybe rotated within the tree so as to bring that particular element at the root.
Advantages and disadvantages of Splay Trees
The use of splay trees provides certain advantages:
- Faster performance:
A splay tree is known for giving a faster performance than other variants of self-balancing trees owing to its self-optimizing nature. This is so because the nodes that have been accessed recently in the tree are constantly moving closer to the root of the tree, with the most recent node being at the node and the nodes accessed before it placed after the root node and so on. This is beneficial for all uses of a splay tree, most prominently for implementing caches.
- Easier Implementation
When compared to other types of self-balancing trees including AVL trees and red-black trees, it is easier to implement a splay tree. In spite of this, splay trees are as efficient as any other type of self-balancing binary trees.
- Lower memory space
Since no bookkeeping data is associated to the nodes and it does not need to be stored alongwith the splay trees, the memory required to store a splay tree is lesser as compared to other types of trees.
- Efficiency with identical keys
Splay trees prove to be a better solution for situations where identical keys are contained in the nodes, thus providing it a major advantage over the other self balancing trees. The time taken to perform the operations on nodes which have identical keys still remains amortized and does not change from O(log n). This is so because whenever the nodes of the tree contain identical keys, the tree (or rather, its operation) always “keeps in mind” their order in the tree. This is also the case with stable sorting algorithms. By using an efficient find or search operation, it is possible to detect the left most or the right most node for a given key.
However, there are certain disadvantages or ‘issues’ of splay trees that need to be considered when using them:
- When it comes to uniform access within the tree, a splay tree proves to be less efficient in performance as compared to a simpler type of balanced binary tree. This difference in performance, however, is not asymptotical but is worse than a comparatively more balanced binary tree.
- A problem arises with the splay tree’s basic algorithm itself. This occurs when the elements of the tree are to be accessed sequentially, one after another, in a sorted order. When this is done, the whole tree becomes unbalanced and accessing the first item again requires a larger amount of time. This is a significant delay for the particular final operation originally intended though the overall performance remains unchanged. A workaround for this has been found in the form of rebalancing the tree at random to avoid the unbalancing that occurs due to the above operation.
|
