Splay tree

In computer science, a splay tree (also called Spreizbaum, English Splay tree ) is a special type of binary search tree. The splay tree is a self-organizing data structure with the particularity that the organization of the stored elements potentially not only with modifications (as in AVL tree and red-black tree ) changes, but also in mere inquiries. The requested items are " flushed " in the vicinity of the root, so that they are easier to find at a alsbaldigen new search. All major operations such as insert, search and delete are ( amortized ) running efficiently. For a given query sequence, the splay tree behaves with respect to the asymptotic running time of all queries is equivalent to an optimal static data structure for this sequence. This property is referred to as " static -optimal ". It is believed that the duration of the asymptotic query sequence and is equivalent to the optimum dynamic data structure. This conjecture is known as " dynamic optimality ", and is considered one of the most famous 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 regular trees splay a special operation by which all other operations can be performed very easily.

Splay

If the splay operation applied to an element x in a tree T, it ensures that x is after the operation in the root of T. This is achieved by the element step by step in the tree is hinaufrotiert until it has finally arrived at the root. For this purpose, x in each case compared with his father and grandfather. Due to this comparison, six cases are distinguished, each of which half are symmetric.

Note: rotations are described in Article binary tree.

Zig- rotation

If x is the left child of his father and grandfather did not, and thus is already directly under the root, a zig- rotation (clockwise rotation) is performed. Now, the new root of the tree and the splay operation x terminated. X is in his father's right subtree, analogue a zag rotation ( left rotation ) is performed. X has a grandfather, two single rotations can be assembled into a Kompositrotation.

Zig- zig rotation

If x is the left child of its parent, which is the left child of the grandfather of x, then a zig- zig rotation is performed ( two right - rotations). Here, x is swapped with the grandfather and all other subtrees are placed at the appropriate places. If x is not yet in the root of the tree after the rotation, then weiterrotiert. Symmetrically, the whoosh - whoosh - rotation if x is the right child of his father 's, which is the right child of the grandfather of x.

Zag zig- rotation

If x is the second child (from left) his grandfather, a zig zag rotation ( left rotation followed by a right rotation ) is performed. These exchanges x is the position with his grandfather and all other subtrees are placed at the appropriate places. If x is not yet in the root of the tree after the rotation, then weiterrotiert. Symmetrically, the zig- zag rotation, if x is the left child of his father 's, which is the right child of the grandfather of x.

Amortized running time: O ( log n)

Search

To search for an element x in the tree T, one simply executes splay (x, T). This causes if x was contained in T, it is now in the root. Thus one new root with x only needs to compare. If they are different, x was not in the tree.

Amortized running time: O ( log n)

To insert an element x into a splay tree T, one first looks like a binary tree to x. After this search ends unsuccessfully, one gets the node v would have to be appended to the x. This node v is now brought to the root of the splay operation. Thus, V is now at the root and has two sub-trees T1 and T2. Now the split operation is performed:

X is compared with v:

Thus, x is at the root and at the right place.

Amortized running time: O ( log n)

To delete x from T, one introduces only once a search on x of the element is found, it is deleted, and the subtree to the parent node P ( x) appended. Followed by splay ( P (x), T), which brings the parent node to the root.

Amortized running time: O ( log n)

Unite

The join operation combines two splay trees T1 and T2, which have been separated immediately before by means of split. Here (T1 ∞, ) is first searched using splay the maximal element x1 of the first tree and rotated to the root. Since the two trees T1 and T2, the result of a previous operation are split, all of the elements in T2 are larger than the elements in T1, and therefore the tree is T2 can now make without problems at the right child of x1.

Amortized running time: O ( log n)

Splitting

In order to split a splay tree T at node x in two splay trees, one first makes x means splay to the root of T. Was contain x in the tree, you can now simply disconnect one of the two subtrees. If after the splay operation another element y in the root, so x itself was not included in T. If x is less than y now, so you can cut off the left child of y, otherwise his right.

Amortized running time: O ( log n)