Editing Splay tree (section)

{{Short description|Self-adjusting binary search tree}}
{{Use dmy dates|date=January 2022}}
{{Infobox data structure-amortized
|name=Splay tree
|type=Tree
|invented_year=1985
|invented_by=[[Daniel Dominic Sleator]] and [[Robert Endre Tarjan]]
|space_avg=O(''n'')
| search_avg=O(log ''n'')<ref name="SleatorTarjan" />{{rp|659}}
|search_worst=O(''n'')<ref name=BrinkmannDegraerDeLoof />{{rp|1}}
|insert_avg=O(log ''n'')<ref name="SleatorTarjan" />{{rp|659}}
|insert_worst=O(''n'')
|delete_avg=O(log ''n'')<ref name="SleatorTarjan" />{{rp|659}}
|delete_worst=O(''n'')
}}

A '''splay tree''' is a [[binary search tree]] with the additional property that recently accessed elements are quick to access again.  Like [[self-balancing binary search tree]]s, a splay tree performs basic operations such as insertion, look-up and removal in [[big O notation|O]](log ''n'') [[amortized analysis|amortized]] time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the [[Entropy (information theory)|entropy]] of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by [[Daniel Sleator]] and [[Robert Tarjan]] in 1985.<ref name="SleatorTarjan">{{harvnb|Sleator|Tarjan|1985}}.</ref>

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 with the basic search operation is to first perform a standard binary tree search for the element in question, and then use [[tree rotation]]s 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.