Splay Trees
From
m (Protected "Splay Trees" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) |
(→Splay Tree behavior) |
||
| Line 6: | Line 6: | ||
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. | 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. | ||
<br/><br/> | <br/><br/> | ||
| + | ---- | ||
| + | {{CS2/ChapNav}} | ||
| + | ---- | ||
| + | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Revision as of 17:06, 9 April 2009
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
