Asplay tree is abinary search tree with the additional property that recently accessed elements are quick to access again. Likeself-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal inO(logn)amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to theentropy 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 byDaniel Sleator andRobert Tarjan in 1985.^[1]

All normal operations on a binary search tree are combined with one basic operation, calledsplaying. 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 usetree 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.

Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is O(n), with the average being O(logn).Having frequently-used nodes near the root is an advantage for many practical applications (also seelocality of reference), and is particularly useful for implementingcaches andgarbage collection algorithms.

Advantages include:

• Comparable performance: Average-case performance is as efficient as other trees.^[3]
• Smallmemory footprint: Splay trees do not need to store any bookkeeping data.

The most significant disadvantage of splay trees is that the height of a splay tree can be linear.^[2]: 1 For example, this will be the case after accessing alln elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of a single operation can be high. However theamortized access cost of this worst case is logarithmic, O(logn). Also, the expected access cost can be reduced to O(logn) by using a randomized variant.^[4]

The representation of splay trees can change even when they are accessed in a 'read-only' manner (i.e. byfind operations). This complicates the use of such splay trees in a multi-threaded environment. Specifically, extra management is needed if multiple threads are allowed to performfind operations concurrently. This also makes them unsuitable for general use in purely functional programming, although even there they can be used in limited ways to implement priority queues.

Finally, when the access patternis random, the additional splaying overhead adds a significant constant factor to the cost compared to less-dynamic alternatives.

When a nodex is accessed, a splay operation is performed onx to move it to the root. A splay operation is a sequence ofsplay steps, each of which movesx closer to the root. By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so it provides the desired amortized time bounds.

Each particular step depends on three factors:

• Whetherx is the left or right child of its parent node,p,
• whetherp is the root or not, and if not
• whetherp is the left or right child ofits parent,g (thegrandparent ofx).

There are three types of splay steps, each of which has two symmetric variants: left- and right-handed. For the sake of brevity, only one of these two is shown for each type. (In the following diagrams, circles indicate nodes of interest and triangles indicate sub-trees of arbitrary size.) The three types of splay steps are:

Zig step: this step is done whenp is the root. The tree is rotated on the edge betweenx andp. Zig steps exist to deal with the parity issue, will be done only as the last step in a splay operation, and only whenx has odd depth at the beginning of the operation.

Zig-zig step: this step is done whenp is not the root andx andp are either both right children or are both left children. The picture below shows the case wherex andp are both left children. The tree is rotated on the edge joiningp withits parentg, then rotated on the edge joiningx withp. Zig-zig steps are the only thing that differentiate splay trees from therotate to root method introduced by Allen and Munro^[5] prior to the introduction of splay trees.

Zig-zag step: this step is done whenp is not the root andx is a right child andp is a left child or vice versa (x is left,p is right). The tree is rotated on the edge betweenp andx, and then rotated on the resulting edge betweenx andg.

Given two trees S and T such that all elements of S are smaller than the elements of T, the following steps can be used to join them to a single tree:

• Splay the largest item in S. Now this item is in the root of S and has a null right child.
• Set the right child of the new root to T.

Given a tree and an elementx, return two new trees: one containing all elements less than or equal tox and the other containing all elements greater thanx. This can be done in the following way:

• Splayx. Now it is in the root so the tree to its left contains all elements smaller thanx and the tree to its right contains all element larger thanx.
• Split the right subtree from the rest of the tree.

To insert a valuex into a splay tree:

• Insertx as with a normalbinary search tree.
• Perform a splay onx.

As a result, the newly inserted nodex becomes the root of the tree.

Alternatively:

• Use the split operation to split the tree at the value ofx to two sub-trees: S and T.
• Create a new tree in whichx is the root, S is its left sub-tree and T its right sub-tree.

To delete a nodex, use the same method as with a binary search tree:

• Ifx has two children:
  • Swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor).
  • Remove that node instead.

In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.

Alternatively:

• The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. leaves the tree with two sub trees.
• The two sub-trees are then joined using a "join" operation.

Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node. It is possible to record the access path during the first pass for use during the second, but that requires extra space during the access operation. Another alternative is to keep a parent pointer in every node, which avoids the need for extra space during access operations but may reduce overall time efficiency because of the need to update those pointers.^[1]

Another method which can be used is based on the argument that the tree can be restructured during the way down the access path instead of making a second pass. This top-down splaying routine uses three sets of nodes – left tree, right tree and middle tree. The first two contain all items of original tree known to be less than or greater than current item respectively. The middle tree consists of the sub-tree rooted at the current node. These three sets are updated down the access path while keeping the splay operations in check. Another method, semisplaying, modifies the zig-zig case to reduce the amount of restructuring done in all operations.^[1][6]

Below there is an implementation of splay trees in C++, which uses pointers to represent each node on the tree. This implementation is based on bottom-up splaying version and uses the second method of deletion on a splay tree. Also, unlike the above definition, this C++ version doesnot splay the tree on finds – it only splays on insertions and deletions, and the find operation, therefore, has linear time complexity.

#include<functional>#ifndef SPLAY_TREE#define SPLAY_TREEtemplate<typenameT,typenameComp=std::less<T>>classsplay_tree{private:Compcomp;unsignedlongp_size;structnode{node*left,*right;node*parent;Tkey;node(constT&init=T()):left(nullptr),right(nullptr),parent(nullptr),key(init){}~node(){}}*root;voidleft_rotate(node*x){node*y=x->right;if(y){x->right=y->left;if(y->left)y->left->parent=x;y->parent=x->parent;}if(!x->parent)root=y;elseif(x==x->parent->left)x->parent->left=y;elsex->parent->right=y;if(y)y->left=x;x->parent=y;}voidright_rotate(node*x){node*y=x->left;if(y){x->left=y->right;if(y->right)y->right->parent=x;y->parent=x->parent;}if(!x->parent)root=y;elseif(x==x->parent->left)x->parent->left=y;elsex->parent->right=y;if(y)y->right=x;x->parent=y;}voidsplay(node*x){while(x->parent){if(!x->parent->parent){if(x->parent->left==x)right_rotate(x->parent);elseleft_rotate(x->parent);}elseif(x->parent->left==x&&x->parent->parent->left==x->parent){right_rotate(x->parent->parent);right_rotate(x->parent);}elseif(x->parent->right==x&&x->parent->parent->right==x->parent){left_rotate(x->parent->parent);left_rotate(x->parent);}elseif(x->parent->left==x&&x->parent->parent->right==x->parent){right_rotate(x->parent);left_rotate(x->parent);}else{left_rotate(x->parent);right_rotate(x->parent);}}}voidreplace(node*u,node*v){if(!u->parent)root=v;elseif(u==u->parent->left)u->parent->left=v;elseu->parent->right=v;if(v)v->parent=u->parent;}node*subtree_minimum(node*u){while(u->left)u=u->left;returnu;}node*subtree_maximum(node*u){while(u->right)u=u->right;returnu;}public:splay_tree():root(nullptr),p_size(0){}voidinsert(constT&key){node*z=root;node*p=nullptr;while(z){p=z;if(comp(z->key,key))z=z->right;elsez=z->left;}z=newnode(key);z->parent=p;if(!p)root=z;elseif(comp(p->key,z->key))p->right=z;elsep->left=z;splay(z);p_size++;}node*find(constT&key){node*z=root;while(z){if(comp(z->key,key))z=z->right;elseif(comp(key,z->key))z=z->left;elsereturnz;}returnnullptr;}voiderase(constT&key){node*z=find(key);if(!z)return;splay(z);if(!z->left)replace(z,z->right);elseif(!z->right)replace(z,z->left);else{node*y=subtree_minimum(z->right);if(y->parent!=z){replace(y,y->right);y->right=z->right;y->right->parent=y;}replace(z,y);y->left=z->left;y->left->parent=y;}deletez;p_size--;}/* //the alternative implementation    void erase(const T &key) {        node *z = find(key);        if (!z) return;        splay(z);        node *s = z->left;        node *t = z->right;        delete z;        node *sMax = NULL;        if (s) {            s->parent = NULL;            sMax = subtree_maximum(s);            splay(sMax);            root = sMax;        }        if (t) {            if (s)                sMax->right = t;            else                root = t;            t->parent = sMax;        }        p_size--;    }*/constT&minimum(){returnsubtree_minimum(root)->key;}constT&maximum(){returnsubtree_maximum(root)->key;}boolempty()const{returnroot==nullptr;}unsignedlongsize()const{returnp_size;}};#endif// SPLAY_TREE

A simpleamortized analysis of static splay trees can be carried out using thepotential method. Define:

• size(r) = the number of nodes in the sub-tree rooted at noder (includingr).
• rank(r) = log₂(size(r)).
• Φ = the sum of the ranks of all the nodes in the tree.

Φ will tend to be high for poorly balanced trees and low for well-balanced trees.

To apply thepotential method, we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation (see figures above).

ΔΦ	= rank'(p) − rank(p) + rank'(x) − rank(x)	[since only p and x change ranks]
	= rank'(p) − rank(x)	[since rank'(x)=rank(p)]
	≤ rank'(x) − rank(x)	[since rank'(p)<rank'(x)]

ΔΦ	= rank'(g) − rank(g) + rank'(p) − rank(p) + rank'(x) − rank(x)
	= rank'(g) + rank'(p) − rank(p) − rank(x)	[since rank'(x)=rank(g)]
	≤ rank'(g) + rank'(x) − 2 rank(x)	[since rank(x)<rank(p) and rank'(x)>rank'(p)]
	≤ 3(rank'(x)−rank(x)) − 2	[due to the concavity of the log function]

ΔΦ	= rank'(g) − rank(g) + rank'(p) − rank(p) + rank'(x) − rank(x)
	≤ rank'(g) + rank'(p) − 2 rank(x)	[since rank'(x)=rank(g) and rank(x)<rank(p)]
	≤ 3(rank'(x)−rank(x)) − 2	[due to the concavity of the log function]

The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence:

amortized-cost	= cost + ΔΦ
	≤ 3(rank'(x)−rank(x))

When summed over the entire splay operation, thistelescopes to 1 + 3(rank(root)−rank(x)) which is O(logn), since we use The Zig operation at most once and the amortized cost of zig is at most 1+3(rank'(x)−rank(x)).

So now we know that the totalamortized time for a sequence ofm operations is:

${\displaystyle T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(m)=O(m\log n)}$

To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done (Φ_i) to the final state after all operations are completed (Φ_f).

${\displaystyle {\mathrm{\Phi }}_i-{\mathrm{\Phi }}_f=\sum _x{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_i(x)-{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_f(x)=O(n\log n)}$

where thebig O notation can be justified by the fact that for every nodex, the minimum rank is 0 and the maximum rank is log(n).

Now we can finally bound the actual time:

${\displaystyle T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(m)=O(m\log n+n\log n)}$

The above analysis can be generalized in the following way.

• Assign to each noder a weightw(r).
• Define size(r) = the sum of weights of nodes in the sub-tree rooted at noder (includingr).
• Define rank(r) and Φ exactly as above.

The same analysis applies and the amortized cost of a splaying operation is again:

${\displaystyle 1+3(\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(root)-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(x))}$

whereW is the sum of all weights.

The decrease from the initial to the final potential is bounded by:

${\displaystyle {\mathrm{\Phi }}_i-{\mathrm{\Phi }}_f\le \sum _{x\in tree}\log \frac{W}{w(x)}}$

since the maximum size of any single node isW and the minimum isw(x).

Hence the actual time is bounded by:

${\displaystyle O\left(\sum _{x\in sequence}\left(1+3\log \frac{W}{w(x)}\right)+\sum _{x\in tree}\log \frac{W}{w(x)}\right)=O\left(m+\sum _{x\in sequence}\log \frac{W}{w(x)}+\sum _{x\in tree}\log \frac{W}{w(x)}\right)}$

There are several theorems and conjectures regarding the worst-case runtime for performing a sequenceS ofm accesses in a splay tree containingn elements.

In addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original Sleator and Tarjan paper. This conjecture is known as thedynamic optimality conjecture and it basically claims that splay trees perform as well as any other binary search tree algorithm up to a constant factor.

Dynamic Optimality Conjecture:^[1] Let${\displaystyle A}$ be any binary search tree algorithm that accesses an element${\displaystyle x}$ by traversing the path from the root to${\displaystyle x}$ at a cost of${\displaystyle d(x)+1}$, and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let${\displaystyle A(S)}$ be the cost for${\displaystyle A}$ to perform the sequence${\displaystyle S}$ of accesses. Then the cost for a splay tree to perform the same accesses is${\displaystyle O[n+A(S)]}$.

There are several corollaries of the dynamic optimality conjecture that remain unproven:

Traversal Conjecture:^[1] Let${\displaystyle T_1}$ and${\displaystyle T_2}$ be two splay trees containing the same elements. Let${\displaystyle S}$ be the sequence obtained by visiting the elements in${\displaystyle T_2}$ in preorder (i.e., depth first search order). The total cost of performing the sequence${\displaystyle S}$ of accesses on${\displaystyle T_1}$ is${\displaystyle O(n)}$.

Deque Conjecture:^[11][13][14] Let${\displaystyle S}$ be a sequence of${\displaystyle m}$double-ended queue operations (push, pop, inject, eject). Then the cost of performing${\displaystyle S}$ on a splay tree is${\displaystyle O(m+n)}$.

Split Conjecture:^[6] Let${\displaystyle S}$ be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order${\displaystyle S}$, splitting each tree into two separate trees at each deleted item, is${\displaystyle O(n)}$.

In order to reduce the number of restructuring operations, it is possible to replace the splaying withsemi-splaying, in which an element is splayed only halfway towards the root.^[1][2]

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 firstm access operations.^[1]

The CBTree augments the splay tree with access counts at each node and uses them to restructure infrequently. A variant of the CBTree called the LazyCBTree does at most one rotation on each lookup. This is used along with an optimistic hand-over-hand validation scheme to make a concurrent self-adjusting tree.^[15]

Using pointer-compression techniques,^[16] it is possible to construct asuccinct splay tree.

• 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)

• Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014)."The CB tree: a practical concurrent self-adjusting search tree".Distributed Computing.27 (6):393–417.doi:10.1007/s00446-014-0229-0.
• Albers, Susanne; Karpinski, Marek (28 February 2002)."Randomized Splay Trees: Theoretical and Experimental Results"(PDF).Information Processing Letters.81 (4):213–221.doi:10.1016/s0020-0190(01)00230-7.
• Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Fagerberg, Rolf (2010). "An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times". In Kaplan, H. (ed.).Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Vol. 6139. pp. 38–49.arXiv:1003.0139.doi:10.1007/978-3-642-13731-0_5.ISBN 978-3-642-13730-3.
• Allen, Brian; Munro, Ian (October 1978)."Self-organizing binary search trees".Journal of the ACM.25 (4):526–535.doi:10.1145/322092.322094.S2CID 15967344.
• Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (January 2009)."Rehabilitation of an unloved child: semi-splaying"(PDF).Software: Practice and Experience.39 (1):33–45.CiteSeerX 10.1.1.84.790.doi:10.1002/spe.v39:1.hdl:11382/102133.The results show that semi-splaying, which was introduced in the same paper as splaying, performs better than splaying under almost all possible conditions. This makes semi-splaying a good alternative for all applications where normally splaying would be applied. The reason why splaying became so prominent while semi-splaying is relatively unknown and much less studied is hard to understand.
• Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (January 2000). "On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences".SIAM Journal on Computing.30 (1):1–43.CiteSeerX 10.1.1.36.4558.doi:10.1137/s0097539797326988.
• Cole, Richard (January 2000). "On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof".SIAM Journal on Computing.30 (1):44–85.CiteSeerX 10.1.1.36.2713.doi:10.1137/S009753979732699X.
• Elmasry, Amr (April 2004)."On the sequential access theorem and Deque conjecture for splay trees".Theoretical Computer Science.314 (3):459–466.doi:10.1016/j.tcs.2004.01.019.
• Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014).Data Structures and Algorithms in Java (6 ed.). Wiley. p. 506.ISBN 978-1-118-77133-4.
• Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Victor K. (1995)."Splay trees for data compression". In Clarkson, Kenneth L. (ed.).Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22–24 January 1995. San Francisco, California, USA. ACM/SIAM. pp. 522–530.Average depth of access in a splay tree is proportional to the entropy.
• Knuth, Donald (1997).The Art of Computer Programming. Vol. 3: Sorting and Searching (3rd ed.). Addison-Wesley. p. 478.ISBN 0-201-89685-0.The time needed to access data in a splay tree is known to be at most a small constant multiple of the access time of a statically optimum tree, when amortized over any series of operations.
• Lucas, Joan M. (1991). "On the Competitiveness of Splay Trees: Relations to the Union-Find Problem".On-line Algorithms: Proceedings of a DIMACS Workshop, February 11–13, 1991. Series in Discrete Mathematics and Theoretical Computer Science. Vol. 7.Center for Discrete Mathematics and Theoretical Computer Science. pp. 95–124.ISBN 0-8218-7111-0.
• Pettie, Seth (2008). "Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture".Proc. 19th ACM-SIAM Symposium on Discrete Algorithms(PDF). pp. 1115–1124.arXiv:0707.2160.
• Sleator, Daniel D.;Tarjan, Robert E. (1985)."Self-Adjusting Binary Search Trees"(PDF).Journal of the ACM.32 (3):652–686.doi:10.1145/3828.3835.S2CID 1165848.
• Sundar, Rajamani (1992). "On the Deque conjecture for the splay algorithm".Combinatorica.12 (1):95–124.doi:10.1007/BF01191208.S2CID 27422556.
• Tarjan, Robert E. (1985). "Sequential access in splay trees takes linear time".Combinatorica.5 (4):367–378.doi:10.1007/BF02579253.S2CID 34757821.
• Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Kuszmaul, William; Tagliavini, Guido (2023). "Tiny Pointers".Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA):477–508.doi:10.1137/1.9781611977554.ch21.ISBN 978-1-61197-755-4.S2CID 244709005.

• 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

• Binary trees
• Search trees
• Amortized data structures

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from January 2022
• CS1: long volume value