Splay Trees
From
(→Splay Tree behavior) |
|||
| Line 1: | Line 1: | ||
| + | <noinclude> | ||
| + | {{CS2:BookNav|base=/|up=Binary Trees|prev=Red-Black Trees|next=Heaps}} | ||
| + | </noinclude> | ||
| + | <br/> | ||
A Splay tree is not actually a data structure, rather it is a set of rules for improving the performance of a BST, and they were first introduced by D. D. Sleator and R. E. Tarjan in 1985. | A Splay tree is not actually a data structure, rather it is a set of rules for improving the performance of a BST, and they were first introduced by D. D. Sleator and R. E. Tarjan in 1985. | ||
<br/><br/> | <br/><br/> | ||
Current revision as of 19:42, 9 April 2009
| ← Red-Black Trees | ↑ Binary Trees | Heaps → |
A Splay tree is not actually a data structure, rather it is a set of rules for improving the performance of a BST, and they were first introduced by D. D. Sleator and R. E. Tarjan in 1985.
Splay Tree behavior
The principle behind a Splay tree is that of locality of reference, the same principle that is behind cache memory. Whenever a node S is accessed, inserted or searched, it is moved by a series of rotations to the root of the tree. This movement is called splaying. If a node is deleted, its former parent is splayed. No single operation on a splay tree is guaranteed to be efficient, rather a series of operations over time become efficient, so that the average cost per operation is low.
Experimental studies claim that a random sequence of dictionary operation are actually faster with a Splay tree than with either an AVL tree or a Red-Black tree. And, a Spay tree has the added advantage that it is easier to code than either an AVL or a Red-Black tree.
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
