Data Structures Algorithms 简明教程
Splay Trees
Splay 树是二叉搜索树的变体，因为它包含所有 BST 操作，如插入、删除和搜索，然后是另一个称为 splaying 的扩展操作。
Splay trees are the altered versions of the Binary Search Trees, since it contains all the operations of BSTs, like insertion, deletion and searching, followed by another extended operation called splaying.
例如，一个值“A”应该被插入到树中。如果树为空，则将“A”添加到树的根并退出；但是如果树不为空，则使用二分查找插入操作来插入元素，然后对新节点执行 splaying。
For instance, a value "A" is supposed to be inserted into the tree. If the tree is empty, add "A" to the root of the tree and exit; but if the tree is not empty, use binary search insertion operation to insert the element and then perform splaying on the new node.
类似地，在 splay 树中搜索一个元素之后，包含该元素的节点也必须被 splaying。
Similarly, after searching an element in the splay tree, the node consisting of the element must be splayed as well.
但是我们如何执行 splaying？简单来说，splaying 就是将一个操作节点移到根处的过程。它有六种类型的旋转。
But how do we perform splaying? Splaying, in simpler terms, is just a process to bring an operational node to the root. There are six types of rotations for it.
-
Zig rotation
-
Zag rotation
-
Zig-Zig rotation
-
Zag-Zag rotation
-
Zig-Zag rotation
-
Zag-Zig rotation
Zig rotation
当操作节点是根节点或根节点的左子节点时，执行 zig 旋转。该节点向右旋转。
The zig rotations are performed when the operational node is either the root node or the left child node of the root node. The node is rotated towards its right.
经过移动后，树看起来如下：
After the shift, the tree will look like −
Zag rotation
当操作节点是根节点或根节点的右子节点时，也执行 zag 旋转。该节点向左旋转。
The zag rotations are also performed when the operational node is either the root node or the right child nod of the root node. The node is rotated towards its left.
经过移动后，操作节点变为根节点：
The operational node becomes the root node after the shift −
Zig-Zig rotation
当操作节点同时具有父节点和祖先节点时，执行 zig-zig 旋转。该节点向右移动两个位置。
The zig-zig rotations are performed when the operational node has both parent and a grandparent. The node is rotated two places towards its right.
第一次旋转将树向右移动一个位置：
The first rotation will shift the tree to one position right −
第二次向右旋转将再次将节点移动一个位置。移动后的最终树看起来如下：
The second right rotation will once again shift the node for one position. The final tree after the shift will look like this −
Zag-Zag rotation
当操作节点同时具有父节点和祖先节点时，也执行 zag-zag 旋转。该节点向左移动两个位置。
The zag-zag rotations are also performed when the operational node has both parent and a grandparent. The node is rotated two places towards its left.
经过第一次旋转后，树看起来如下：
After the first rotation, the tree will look like −
然后，第二次旋转后的最终树如下所示。然而，操作节点仍然不是根，因此 splaying 被认为不完整。因此，在这种情况下再次应用其他合适的旋转，直到该节点成为根节点。
Then the final tree after the second rotation is given as follows. However, the operational node is still not the root so the splaying is considered incomplete. Hence, other suitable rotations are again applied in this case until the node becomes the root.
Zig-Zag rotation
当操作节点同时具有父节点和祖先节点时，执行 zig-zag 旋转。但不同之处在于，祖先节点父节点和子节点采用 LRL 格式。该节点先向右旋转，然后向左旋转。
The zig-zag rotations are performed when the operational node has both a parent and a grandparent. But the difference is the grandparent, parent and child are in LRL format. The node is rotated first towards its right followed by left.
经过第一次旋转后，树如下：
After the first rotation, the tree is −
经过第二次旋转后的最终树如下：
The final tree after the second rotation −
Zag-Zig rotation
当操作节点同时具有父节点和祖先节点时，也执行 zag-zig 旋转。但不同之处在于，祖先节点、父节点和子节点采用 RLR 格式。该节点先向左旋转，然后向右旋转。
The zag-zig rotations are also performed when the operational node has both parent and grandparent. But the difference is the grandparent, parent and child are in RLR format. The node is rotated first towards its left followed by right.
进行了第一次旋转，得到如下树：
First rotation is performed, the tree is obtained as −
经过第二次旋转，最终得到如下树。然而，操作节点尚未成为根节点，因此需要执行另一次旋转，将该节点设为根。
After second rotation, the final tree is given as below. However, the operational node is not the root node yet so one more rotation needs to be performed to make the said node as the root.
Basic Operations of Splay Trees
伸展树包含二叉搜索树提供的所有基本操作：插入、删除和搜索。然而，在每个操作之后，都会有一个附加操作将其与二叉搜索树操作区分开来：伸展。我们已经学过伸展，因此，让我们理解其他操作的过程。
A splay contains the same basic operations that a Binary Search Tree provides with: Insertion, Deletion, and Search. However, after every operation there is an additional operation that differs them from Binary Search tree operations: Splaying. We have learned about Splaying already so let us understand the procedures of the other operations.
Insertion operation
伸展树中的插入操作与在二叉搜索树中执行插入操作的方式完全相同。在伸展树中执行插入操作的过程如下：
The insertion operation in a Splay tree is performed in the exact same way insertion in a binary search tree is performed. The procedure to perform the insertion in a splay tree is given as follows −
-
Check whether the tree is empty; if yes, add the new node and exit
-
If the tree is not empty, add the new node to the existing tree using the binary search insertion.
-
Then, suitable splaying is chosen and applied on the newly added node.
Zag (Left) Rotation is applied on the new node
Zag (Left) Rotation is applied on the new node
Deletion operation
伸展树中的删除操作执行如下：
The deletion operation in a splay tree is performed as following −
-
Apply splaying operation on the node to be deleted.
-
Once, the node is made the root, delete the node.
-
Now, the tree is split into two trees, the left subtree and the right subtree; with their respective first nodes as the root nodes: say root_left and root_right.
-
If root_left is a NULL value, then the root_right will become the root of the tree. And vice versa.
-
But if both root_left and root_right are not NULL values, then select the maximum value from the left subtree and make it the new root by connecting the subtrees.
Search operation
伸展树中的搜索操作遵循二叉搜索树操作的相同过程。然而，在进行搜索并找到元素之后，对搜索的节点应用伸展。如果找不到元素，则提示搜索不成功。
The search operation in a Splay tree follows the same procedure of the Binary Search Tree operation. However, after the searching is done and the element is found, splaying is applied on the node searched. If the element is not found, then unsuccessful search is prompted.