Splay Trees

From

(Difference between revisions)
Jump to: navigation, search
(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


Personal tools
MediaWiki Appliance - Powered by TurnKey Linux