Splay Trees

From

Revision as of 19:42, 9 April 2009 by Admin (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search
← 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