伸展树(SplayTree)的意义与实现

概念

  伸展树也是一种平衡二叉搜索树,她不要求自己时刻保持平衡,但她却有这样一条有趣的性质:在一个节点被访问之后,需要将这个节点推至根节点,这样下次能迅速地访问到该节点。其余特性和一般的二叉搜索树一致。

应用场景

  在刚开始看到这棵树时,十分好奇,为什么每次访问之后,要将这个节点推送至根节点呢?什么样的场景需要用到伸展树呢?
  我们的生活中有很多场景都会遵循**”二八原则”** ,80%的人只会用到20%的数据,例如热门消息的访问量是远远大于普通消息,输入法中常用的字是非常少的。用另外一种说法,这叫数据局部性,包括以下两个含义:

  1. 刚刚被访问过的元素, 极有可能在不久之后再次被访问到;
  2. 将被访问的下一元素, 极有可能就处于不久之前被访问过的某个元素的附近;

  因此伸展树也非常有意义。

复杂度分析

原理

一个简单的想法(不建议使用)

  一个简单的实现方式就是:访问过一个元素后,从下向上执行单旋转,与父节点实施旋转,最终将其旋转至根节点。
  举一个栗子,考虑在下面的树中访问对 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 ,修改成从上往下的实现,抽空完成。

代码实现

github地址