【CPP】各种各样的树（6）——自底向上的伸展树

昨（shang）天（zhou）结尾说到AVL树的弊端，然后提到了伸展树这个东西，那这次就来说说这个伸展树的第一种实现，自底向上的伸展树。

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树。伸展树能在O(log n)内完成插入、查找和删除操作，由Daniel Sleator和Robert Endre Tarjan在1985年发明。上周说的AVL树在每个操作的时候都要进行Fix操作，而且需要在每个结点保存height值来判断结点是否失衡，这都是非常耗费资源的想法，但是在实际中我们其实对树每个结点的平衡并没有那么严格的要求，我们只希望树的高度可以尽可能的小，需要查找的结点可以不要在那么深的地方罢了，这就催生的伸展树。

伸展树的主要操作是伸展/展开（Splay）。首先伸展树利用到一个思想，近期被访问的数据在接下来的时间有可能还会被访问到，需要将其放在浅一些的地方，这是很符合实际的思想。所以伸展树就会在树里的数据被访问时将那个数据移到最浅（树根），然后不断累积访问可以把结点按照访问顺序大致排列一次。而如何将数据移到树根呢？由于上次说了AVL树，很容易就想到我们可以采用旋转操作，那么想要不断把结点上移，很容易就想到只要不断地单旋转就好了，但是实践中我们发现不断单旋转虽然可以把结点成功上，但是并不能有效地改良树的总体高度，伸展树使用了另外的旋转方法，让每次访问不仅能把访问的结点移到根部还能大致把整棵树的深度减小一半。

而其实这个所谓的另外的旋转方法也不复杂，其实就是之前的双旋转的变形。先找到我们要访问的结点，然后往上寻找结点的两层父结点，若父结点与自己构成了之字形（Zig-Zag），我们进行普通的双旋转，若构成一字形（Zig-Zig），我们从上往下进行两次同方向单旋转，若只有一层父结点，我们进行简单的单旋转，然后结束循环。也就是下面的图的样子。

看完原理就来看看代码，自底向上的伸展树需要想办法保存各结点的父结点，一般有两种保存方式，一种是给每个结点增加一个父结点指针，另一种是用栈来保存访问路径，我这里选择后面一种。代码的解释都写在了注释当中了。

其中的删除操作主要是利用了伸展树的特性，通过访问将目标移到树根然后很方便地使用左子树的最右结点来删除，又完成了删除又让树的深度变低，可谓一举两得了。

最后我们用一个简单的展开实例来实践伸展树。想要更深入的理解可以像《数据结构与算法分析》中一样，先从32到1插入一棵长链树，然后从1到10展开看各步的结果，可以很直观地看出展开操作对树深度的改善效果。

讲完了自底向上的伸展树，想必大家又会想，这样不是还要用一个栈来保存结点吗？而且这样展开一棵树实际上需要从上向下再从下到上遍历两次树才能完成，看起来也不会特别有效率嘛。没错，这两点就是这种写法的伸展树的缺点，下次来说自顶而下的伸展树。