visiting the elements in in preorder (i.e., depth first search order). The total cost of performing the sequence of accesses on is . Deque Conjecture:. Let be a sequence of double-ended queue operations (push, pop, inject, eject). Then the cost of performing on a splay tree is . Split Conjecture: Let be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order is . Variants In order to reduce the number of restructuring operations, it is possible to replace the splaying with semi-splaying, in which an element is splayed only halfway towards the root. Another way to reduce restructuring is to do full splaying, but only in some of the access operations – only when the access path is longer than a threshold, or only in the first m access operations. See also AVL tree B-tree Finger tree Geometry of binary search trees Iacono's working set structure Link/cut tree List of data structures Scapegoat tree Splaysort, a sorting algorithm using splay trees T-tree Treap Tree rotation Trees Zipper (data structure) Notes References External links NIST's Dictionary of Algorithms and Data Structures: Splay Tree Implementations in C and Java (by Daniel Sleator) Pointers to splay tree visualizations Fast and efficient implementation of Splay trees Top-Down Splay Tree Java implementation Zipper Trees Binary trees Search trees Amortized data structures