Encyclopedia > Splay tree

  Article Content

Splay tree

A splay tree is a self-adjusting binary search tree. 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 based on 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. To do this, the element is first found with a standard tree search, then tree rotations are performed in a specific fashion to bring the element to the top.

Reference: The ACM Digital Library (http://www.acm.org/pubs/citations/journals/jacm/1985-32-3/p652-sleator/) has the original publication describing splay trees.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Anna Karenina

...     Contents Anna Karenina Anna Karenina is a novel by Leo Tolstoy published in 1877 through 1878, set against the background of Russian society of tha ...

 
 
 
This page was created in 50.2 ms