Splay tree

In computer science, a splay tree (also called splay tree ) is a special type of binary search tree . The splay tree is a self-organizing data structure with the peculiarity that the organization of the stored elements potentially changes not only with modifications (as with the AVL tree and red-black tree ), but also with mere inquiries. The requested elements are "flushed" near the root so that they can be found more quickly if you search again as soon as possible. All important operations such as insert , search and delete are carried out efficiently ( amortized ). For a given query sequence, the splay tree behaves with respect to the asymptotic runtime of all queries equivalent to an optimal static data structure for this sequence. This property is called “static optimality”. It is assumed that the asymptotic running time of the query sequence is also equivalent to that of an optimal dynamic data structure. This guess is known as "dynamic optimality" and is one of the most well-known open problems in the field of data structures.

Splay trees were introduced in 1985 by Daniel Sleator and Robert Tarjan under the name Self-Adjusting Binary Search Trees .

Operations

Splay trees have over normal trees a special operation splay by which all other operations can be done very easily.

Splay

If the splay operation is used on an element in a tree , it ensures that after the operation it is in the root of . This is achieved by rotating the element step by step up the tree until it finally reaches the root. For this purpose, each is compared with his father or grandfather. Based on this comparison, a total of six cases are distinguished, half of which are symmetrical. ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$

Note: Rotations are described in the Binary Tree article.

Zig rotation

If the left child is his father's and does not have a grandfather and is therefore already directly under the root, a zig -rotation (right-hand rotation) is carried out. Now the new root of the tree and the splay operation is finished. If his father is in the right subtree, a zack rotation (left rotation) is carried out analogously . If you have a grandfather, two single rotations can be combined to form a composite rotation. ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Zig-zig rotation

If the left child of his father is who is the left child of his grandfather , a zig-zig rotation (two right rotations) is carried out. This is swapped with the grandfather and all other subtrees are placed in the appropriate places. If it is not in the root of the tree after the rotation, the rotation continues. Symmetrical to this is the zack- zag rotation, if the right child is his father's who is the right child of the grandfather's . ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Zag-zig rotation

If the second child (from the left) is his grandfather, a zag-zig rotation (left rotation followed by right rotation) is carried out. This swaps positions with his grandfather and all other subtrees are placed in the appropriate places. If it is not in the root of the tree after the rotation, the rotation continues. Symmetrical to this is the zigzag rotation if the left child is his father, who is the right child of the grandfather of . ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Amortized term: ${\displaystyle O(\log n)}$

Search

To find an element in the tree , just do . This means that if it was contained in, it is now in the root. So you only have to compare the new root with . Are they different, was n't in the tree. ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle splay(x,T)}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle x}$

Amortized term: ${\displaystyle O(\log n)}$

Insert

To insert an element in a splay tree , one first searches as in a binary tree . After this search ends unsuccessfully, you get the node to be appended to. This knot is now brought to the root with the splay operation. So it is now at the root and has two subtrees and . Now the split operation is performed: ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

${\displaystyle x}$is compared to: ${\displaystyle v}$

if greater than , then its left subtree is appended to on the left . The right subtree is attached to the right . ${\displaystyle x}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle T_{1}}$ ${\displaystyle x}$ ${\displaystyle T_{2}}$ ${\displaystyle x}$

if less than , then its right subtree is appended to on the right . The left subtree is attached to the left. ${\displaystyle x}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle T_{2}}$ ${\displaystyle x}$ ${\displaystyle T_{1}}$ ${\displaystyle x}$

So it is at the root and in the right place. ${\displaystyle x}$

Amortized term: ${\displaystyle O(\log n)}$

Clear

To made clear, is carried out once a search on from the item is found, it will be deleted, and the sub-tree to the parent node attached. Followed by , which brings the parent node into the root. ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle P(x)}$ ${\displaystyle splay(P(x),T)}$

Amortized term: ${\displaystyle O(\log n)}$

Unite

The join operation joins two splay trees and , which were split immediately before using split . Here, the maximum element of the first tree is first searched for and rotated into the root. Since the two trees and are the result of a previous split operation, all elements in are larger than the elements in , which is why the tree can now be made the right child of without any problems . ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle splay(\infty ,T_{1})}$ ${\displaystyle x_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle x_{1}}$

Amortized term: ${\displaystyle O(\log n)}$

Split up

To split a splay tree at the node into two splay trees, first make the root of using splay . Was contained in the tree, you can now simply disconnect the connection to one of the two subtrees. If there is another element in the root after the Splay operation , it was not contained in. If it is now smaller than , the left child can be cut off, otherwise his right child . ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$

Amortized term: ${\displaystyle O(\log n)}$

Web links

• Splay trees applet
• Splay tree visualization

Individual evidence

1. ^ ^{A b} Daniel D. Sleator, Robert Tarjan : Self-Adjusting Binary Search Trees . In: Journal of the ACM ( Association for Computing Machinery ) . tape 32 , no. 3 , 1985, pp. 652–686 , doi : 10.1145 / 3828.3835 ( cmu.edu [PDF; 6.1 MB ]).