Splay tree
|
|
A splay tree is a self-balancing binary search tree with the additional unusual 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. For many non-uniform sequences of 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 Sleator and Robert Tarjan.
All normal operations on a splay 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 bottom-up algorithm can combine the search and the tree reorganization.
| Contents |
Advantages and disadvantages
Good performance for a splay tree depends on the fact that it is self-balancing, and indeed self optimising, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage for nearly all practical applications, and is particularly useful for implementing caches; however it is important to note that for uniform access, a splay tree's performance will be considerably (although not asymptotically) worse than a somewhat balanced simple binary search tree.
Splay trees also have the advantage of being considerably simpler to implement than other self-balancing binary search trees, such as red-black trees or AVL trees, while their average-case performance is just as efficient. Also, splay trees don't need to store any bookkeeping data, thus minimizing memory requirements. However, these other data structures provide worst-case time guarantees, and can be more efficient in practice for uniform access.
One worst case issue with the basic splay tree algorithm is that of sequentially accessing all the elements of the tree in the sort order. This leaves the tree completely unbalanced (this takes n accesses- each an O(1) operation). Reaccessing the first item triggers an operation that takes O(n) operations to rebalance the tree before returning the first item. This is a significant delay for that final operation, although the amortised performance over the entire sequence is actually O(1). However, recent research shows that randomly rebalancing the tree can avoid this unbalancing effect and give similar performance to the other self-balancing algorithms.
It is possible to create a persistent version of splay trees which allows access to both the previous and new versions after an update. This requires amortized O(log n) space per update.
The splay operation
To do a splay, we carry out a sequence of rotations, each of which moves the target node N closer to the root. Each particular step depends on only two factors:
- Whether N is the left or right child of its parent node, P,
- Whether P is the left or right child of its parent, G (for grandparent node).
Thus, there are four cases:
Case 1: N is the left child of P and P is the left child of G. In this case we perform a double right rotation, so that P becomes N's right child, and G becomes P's right child.
Case 2: N is the right child of P and P is the right child of G. In this case we perform a double left rotation, so that P becomes N's left child, and G becomes P's left child.
Case 3: N is the left child of P and P is the right child of G. In this case we perform a rotation so that G becomes N's left child, and P becomes N's right child.
Case 4: N is the right child of P and P is the left child of G. In this case we perform a rotation so that P becomes N's left child, and G becomes N's right child.
Finally, if N doesn't have a grandparent node, we simply perform a left or right rotation to move it to the root. By performing a splay on the node of interest after every operation, we keep recently accessed nodes near the root and keep the tree roughly balanced, so that we achieve the desired amortized time bounds.
See also
References
- New York University: Dept of Computer Science: Algorithm Visualization: Splay Trees (http://www.cs.nyu.edu/algvis/java/SplayTree.html)
External links
- NIST's Dictionary of Algorithms and Data Structures: Splay Tree (http://www.nist.gov/dads/HTML/splaytree.html)
- The ACM Digital Library: the original publication describing splay trees (http://www.acm.org/pubs/citations/journals/jacm/1985-32-3/p652-sleator/) NB full access requires an ACM Web Account
- Splay Tree Applet (http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/SplayTree-Example.html)
- AVL, Splay and Red/Black Applet (http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm)