Splay Tree

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of nonrandom 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 Dominic Sleator and Robert Endre Tarjan in 1985.

All normal operations on a binary search tree are combined with 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. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.

Read more about Splay Tree:  Advantages, Disadvantages, Analysis, Performance Theorems, Dynamic Optimality Conjecture

Famous quotes containing the word tree:

    Here is a hero who did nothing but shake the tree as soon as the fruit was ripe. Does this seem to be too small a thing to you? Then take a good look at the tree he shook.
    Friedrich Nietzsche (1844–1900)