伸展树（SplayTree）的意义与实现
概念
伸展树也是一种平衡二叉搜索树，她不要求自己时刻保持平衡，但她却有这样一条有趣的性质：在一个节点被访问之后，需要将这个节点推至根节点，这样下次能迅速地访问到该节点。其余特性和一般的二叉搜索树一致。
应用场景
在刚开始看到这棵树时，十分好奇，为什么每次访问之后，要将这个节点推送至根节点呢？什么样的场景需要用到伸展树呢?
我们的生活中有很多场景都会遵循**”二八原则”** ，80%的人只会用到20%的数据，例如热门消息的访问量是远远大于普通消息，输入法中常用的字是非常少的。用另外一种说法，这叫数据局部性，包括以下两个含义：
- 刚刚被访问过的元素， 极有可能在不久之后再次被访问到;
- 将被访问的下一元素， 极有可能就处于不久之前被访问过的某个元素的附近;
因此伸展树也非常有意义。
复杂度分析
原理
一个简单的想法（不建议使用）
一个简单的实现方式就是：访问过一个元素后，从下向上执行单旋转，与父节点实施旋转，最终将其旋转至根节点。
举一个栗子，考虑在下面的树中访问对 k1 进行一次访问之后所发生的情况。
首先，我们在 k1 和她的父节点 k2 之间实施一次单旋转，得到下面的图。
然后，在 k1 和 k3 之间实施一次单旋转，得到下一棵树。
再实施两次单旋转直到 k1 到达树根
这些旋转的效果是将 k1 一直旋转到树根，使得对 k1 的进一步访问很容易（暂时的）。不足的是，她把另外一个节点（k3）几乎推向和 k1 以前同样的深度。而对那个节点的访问又将把另外的节点向深处推进，如此等等。虽然这个策略使得对 k1 的访问花费时间减少，但她并没有明显地改变（原先）访问路径上其他节点的状况。换句话说，访问多次后，树的平均深度和以前差距不大，因此这个想法还不够好。
展开（非常优雅）
展开（Splaying）的思路类似于上面介绍的旋转的想法，不过在旋转如何实施上我们稍有选择的余地。我们仍然从底部向上沿着访问路径旋转。令 X 是访问路径上的一个（非根）节点，我们将在这个路径上实施旋转操作。如果 X 的父节点是树根，那么我们只要旋转 X 和数根。否则， X 就有父亲（P）和祖父（G），存在两种情况以及对冲的情形需要考虑。
第一种情况是之字形（zig-zag）,这里 X 是右儿子， P 是左儿子（反之亦然）。遇到这种情况，我们就执行一次双旋转（也就是两次单旋转）。
否则，就是第二种情况一字形（zig-zig）， X 和 P 都是左儿子，或者都是右儿子。这种情况下，我们把图六左边的树变成右边的树。
现在，我们用展开的方式再对图一的树进行旋转，看一下两种策略导致的差异。
展开的第一步是在 k1 ，显然是一个之字形，因此我们用 k1、k2 和 k3 执行一次标准的AVL树双旋转，得到如下的树，和图三中的树是一致的。
在 k1 展开的下一步是一个一字形，我们用 k1、k4 和 k5 做一字形旋转，得到最后的树，如图八。
我们对比下图四和图八，他们分别是通过一个简单的想法 和 伸展，将 k1 旋转至根节点后得到的树。我们可以发现伸展操作不仅将访问的节点移动到根处，而且还将访问路径上的大部分节点的深度大致减少一半的效果，不过从这些小例子很难看出来。
伸展树也有注意点，当访问路径太长而导致超出正常查找时间时，这些旋转对未来的操作有益。当访问耗时很少时，这些旋转不那么有益，甚至有害。
删除
删除操作比较简单：首先将需要删除的节点 D 旋转至根节点，D 有两个子树，左子树 DL 和右子树 DR ，将 DL 中其最大值旋转至根节点，此时子树 DL 没有右孩子，将 DR 作为 DL 的右孩子即可。
思考
对 splayTree 做了一些测试。随机插入一万个数据后，计算她的原始深度。之后随机访问其中的元素，再次计算她的深度，会发现这个现象：树的深度大概率比伸展前的原始深度要大一些。
对此，感到疑惑，深度变大，平均性能岂不是降低了。我考虑是否是我代码写错了，但仔细思考一下，的确存在这种情况。例如图六中一字形情况，B 子树深度较小， C 子树深度比较大，那么旋转之后，树的深度的确变大了。图五中，如果 D 子树 深度较大，那么旋转之后，整体树的高度也会增加。仔细思考，虽然整体树的高度可能增加了，但平均每个节点的深度一定是降低的！树整体是变优的（有一点最右二叉树的意思）
或许需要优化一下 splayTree ，修改成从上往下的实现，抽空完成。