Data Structures Algorithms 简明教程
Splay Trees
Splay 树是二叉搜索树的变体，因为它包含所有 BST 操作，如插入、删除和搜索，然后是另一个称为 splaying 的扩展操作。
例如，一个值“A”应该被插入到树中。如果树为空，则将“A”添加到树的根并退出；但是如果树不为空，则使用二分查找插入操作来插入元素，然后对新节点执行 splaying。
类似地，在 splay 树中搜索一个元素之后，包含该元素的节点也必须被 splaying。
但是我们如何执行 splaying？简单来说，splaying 就是将一个操作节点移到根处的过程。它有六种类型的旋转。
-
Zig rotation
-
Zag rotation
-
Zig-Zig rotation
-
Zag-Zag rotation
-
Zig-Zag rotation
-
Zag-Zig rotation
Zig-Zig rotation
当操作节点同时具有父节点和祖先节点时，执行 zig-zig 旋转。该节点向右移动两个位置。
第一次旋转将树向右移动一个位置：
第二次向右旋转将再次将节点移动一个位置。移动后的最终树看起来如下：
Zag-Zag rotation
当操作节点同时具有父节点和祖先节点时，也执行 zag-zag 旋转。该节点向左移动两个位置。
经过第一次旋转后，树看起来如下：
然后，第二次旋转后的最终树如下所示。然而，操作节点仍然不是根，因此 splaying 被认为不完整。因此，在这种情况下再次应用其他合适的旋转，直到该节点成为根节点。
Zig-Zag rotation
当操作节点同时具有父节点和祖先节点时，执行 zig-zag 旋转。但不同之处在于，祖先节点父节点和子节点采用 LRL 格式。该节点先向右旋转，然后向左旋转。
经过第一次旋转后，树如下：
经过第二次旋转后的最终树如下：
Zag-Zig rotation
当操作节点同时具有父节点和祖先节点时，也执行 zag-zig 旋转。但不同之处在于，祖先节点、父节点和子节点采用 RLR 格式。该节点先向左旋转，然后向右旋转。
进行了第一次旋转，得到如下树：
经过第二次旋转，最终得到如下树。然而，操作节点尚未成为根节点，因此需要执行另一次旋转，将该节点设为根。
Basic Operations of Splay Trees
伸展树包含二叉搜索树提供的所有基本操作：插入、删除和搜索。然而，在每个操作之后，都会有一个附加操作将其与二叉搜索树操作区分开来：伸展。我们已经学过伸展，因此，让我们理解其他操作的过程。
Insertion operation
伸展树中的插入操作与在二叉搜索树中执行插入操作的方式完全相同。在伸展树中执行插入操作的过程如下：
-
检查树是否为空；如果为空，则添加新节点并退出
-
如果树不为空，则使用二叉搜索插入将新节点添加到现有树中。
-
然后，选择并应用合适类型的伸展到新添加的节点。
Zag (Left) Rotation is applied on the new node
