伸展树(Splay Tree)是特殊的二叉查找树。
它的特殊是指，它除了本身是棵二叉查找树之外，它还具备一个特点: 当某个节点被访问时，
伸展树会通过旋转使该节点成为树根。这样做的好处是，下次要访问该节点时，能够迅速的访问到该节点。
SplayTreeNode是伸展树节点对应的类。它包括的几个组成元素:
(01) key -- 是关键字，是用来对伸展树的节点进行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
当我们沿着树向下搜索某个节点X的时候，我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。
没有被移走的节点构成的树称作中树。在伸展操作的过程中：
1、当前节点X是中树的根。
2、左树L保存小于X的节点。
3、右树R保存大于X的节点。
开始时候，X是树T的根，左右树L和R都是空的。
伸展树是第三种二叉树的变种。
在节点中没有存储平衡信息或节点颜色的信息。
作为替代，伸展树是链表维护的“上移”方法与二叉树之间的交叉。
无需像我们对红黑树所做的那样尝试保持树处于平衡状态，将实现的是另一种恒定重排的形式：每次访问树时，都使用双旋转和单旋转重排树，
使得访问过的节点位于树的根。
1、zig：
如上图，在搜索到X的时候，所查找的节点比X小，将Y旋转到中树的树根。旋转之后，X及其右子树被移动到右树上。很显然，右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置，也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点，其值越大。
2、zig-zig:
在这种情况下，所查找的节点在Z的子树中，也就是，所查找的节点比X和Y都小。所以要将X，Y及其右子树都移动到右树中。首先是Y绕X右旋，然后Z绕Y右旋，最后将Z的右子树（此时Z的右子节点为Y）移动到右树中。注意右树中挂载点的位置。
3、zig-zag:
在这种情况中，首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着，对Z进行左旋，将Y及其左子树移动到左树上。这样，这种情况就被分成了两个Zig情况。这样，在编程的时候就会简化，但是操作的数目增加（相当于两次Zig情况）。
最后，在查找到节点后，将三棵树合并。如图：
将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。
右连接：将当前根及其右子树连接到右树上。左子结点作为新根。 左连接：将当前根及其左子树连接到左树上。右子结点作为新根。
越是在路径前面被移动到右树的节点，其值越大；越是在路径前面移动到左树的节点，其值越小。
这很显然，右连接，将当前根以及右子树全部连接到右树，即把整课树中值大的一部分移走（大于等于当前根），
后面，在进行右连接，其值肯定小于之前的，所以，要加在右树的左边。
右连接：将当前根及其右子树连接到右树上。左子结点作为新根。
左连接：将当前根及其左子树连接到左树上。右子结点作为新根。
T ： 当前的根节点。
Function Top-Down-Splay
Do
If X 小于 T Then
If X 等于 T 的左子结点 Then //zig
右连接
ElseIf X 小于 T 的左子结点 Then //zig-zig
T的左子节点绕T右旋
右连接
Else X大于 T 的左子结点 Then //zig-zag
右连接
左连接
EndIf
ElseIf X大于 T Then
IF X 等于 T 的右子结点 Then
左连接
ElseIf X 大于 T 的右子结点 Then
T的右子节点绕T左旋
左连接
Else X小于 T 的右子结点 Then
左连接
右连接
EndIf
EndIf
While ！(找到 X或遇到空节点)
组合左中右树
EndFunction