
related topics 
{math, number, function} 
{system, computer, user} 
{woman, child, man} 

A splay tree is a selfadjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, lookup and removal in O(log n) amortized time. For many 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 Dominic Sleator and Robert Endre Tarjan in 1985.^{[1]}
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 topdown algorithm can combine the search and the tree reorganization into a single phase.
Contents
Advantages
Good performance for a splay tree depends on the fact that it is selfoptimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The height  though unlikely  is O(n), with the average being O(log n). This is an advantage for nearly all practical applications,^{[citation needed]} and is particularly useful for implementing caches and garbage collection algorithms.
Advantages include:
 Simple implementation—simpler than other selfbalancing binary search trees, such as redblack trees or AVL trees.
 Comparable performance  averagecase performance is as efficient as other trees.^{[citation needed]}
 Small memory footprint—splay trees do not need to store any bookkeeping data.
 Possibility of creating a persistent data structure version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in functional programming, and requires amortized O(log n) space per update.
 Working well with nodes containing identical keys—contrary to other types of selfbalancing trees. Even with identical keys, performance remains amortized O(log n). All tree operations preserve the order of the identical nodes within the tree,^{[citation needed]} which is a property similar to stable sorting algorithms. A carefully designed find operation can return the left most or right most node of a given key.
Full article ▸


related documents 
Axiom schema of specification 
Horner scheme 
Euler–Mascheroni constant 
NPcomplete 
Convergence of random variables 
Preadditive category 
Linear map 
Field extension 
Universal property 
Selforganizing map 
Projective plane 
Bubble sort 
Euler–Maclaurin formula 
Spectral theorem 
Bruteforce search 
Hausdorff space 
Binary tree 
Rice's theorem 
Logical connective 
Additive category 
Binary heap 
Planar graph 
Polymorphism in objectoriented programming 
Isomorphism 
Constructivism (mathematics) 
Chinese remainder theorem 
Cauchy–Schwarz inequality 
Trace (linear algebra) 
Locally compact space 
Transcendental number 
