作用于二叉查找树上的基本操作（如查找，插入等）的时间复杂度与树的高度成正比。对一个含 n 个节点的完全二叉树，这些操作的最坏情况运行时间为 O(log n)。但如果因为频繁的删除和插入操作，导致树退化成一个 n 个节点的线性链（此时即为一个单链表），则这些操作的最坏情况运行时间为 O(n) 。为了克服以上缺点，很多二叉查找树的变形出现了，如红黑树、AVL树，Treap树等。

本文介绍了二叉查找树的一种改进数据结构–伸展树（Splay Tree）。它的主要特点是不会保证树一直是平衡的，但各种操作的平摊时间复杂度是 O(log n)，因而，从平摊复杂度上看，二叉查找树也是一种平衡二叉树。另外，相比于其他树状数据结构（如红黑树，AVL树等），伸展树的空间要求与编程复杂度要小得多。

定义

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。

旋转

具体来说，在查询到目标节点后，伸展树会不断进行下面三种操作中的一个，直到目标节点成为根节点

每次旋转操作由三个因素决定：

  • x是其父节点p的左儿子还是右儿子；
  • p是否为根；
  • p是其父节点g（x的祖父节点）的左儿子还是右儿子。

在每次旋转操作后，设置g的儿子为x是很重要的。如果g为空，那么x显然就是根节点了。

共有三种旋转操作，每种都有左旋（Zig）和右旋（Zag）两种情况。为了简单起见，对每种旋转操作只展示一种情况。这些旋转操作是：

  • zig: 当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。
1
2
3
4
5
6

    p                x
   / \              / \ 
  x   C            A   p
 / \                  / \
A   B                B   C
            zig
  • Zig-zag 和 Zag-zig：当 p 不为根节点且 x 为左儿子而 p 为右儿子时进行，反之亦然。下图为前述情况（即Zig-zag），需先将 x 左旋到 p 到的位置，再将 x 右旋到 g 的位置。
1
2
3
4
5
6
7
8

     g                g              x
    /  \             / \          /    \
   p    D           x   D        p      g
 /  \              / \          / \    / \
A    x            p   C        A   B  C   D
    / \          / \
   B   C        A   B
                   zig-zag
  • Zig-zig和Zag-zag：当 p 不为根节点且 x 和 p 都为左儿子或都为右儿子时进行。下图为 x 和 p 都为左儿子时的情况（即Zig-zig），需先将 p 右旋到 g 的位置，再将 x 右旋到 p 的位置。

注： 维基百科中写到对于 zig-zig 和 zag-zag 这种情况，是先旋转 p 和 g 之间的边，然后在旋转 p与 x 之间的边。并且明确的说到，这个是扩展树与将节点旋转到根节点方法唯一的区别。但是实际上好像看不出这两个有什么本质的区别。

The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p. Note that zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro[4] prior to the introduction of splay trees.

单旋转操作和双旋转操作见AVL树。下面是zig-zig操作的示意图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

      g            p            x
     / \        /    \         /  \
    p   D      x      g       A    p
   / \        / \    / \          / \
  x   C      A   B  C   D        B   g        
 / \                              / \
A   B                            C   D

      g             g            x
     / \         /    \         /  \
    p   D       x      g       A    g
   / \         / \      \          / \
  x   C       A   p      D        p   D        
 / \             / \             / \
A   B           B   C           B   C

           zig-zig operation

通过上面两种方式都可以实现将 x 节点旋转到顶点。

注：

由于没有领会到 zig-zig 和 zag-zag 场景下先旋转祖父节点与父节点的边，在旋转父与子所在边的好处。或者说两者可能是一样的。在这种情况下，splay 树的旋转也可以使用普通二叉搜索树的旋转方法就能完成要求。而且场景更加简单：

  1. 找到节点,如果是根节点结束，否则跳到步骤 2
  2. 如果节点是左子节点，则右旋，如果为右子节点则左旋，跳到步骤 1

分裂与合并

合并

给出两棵树 S 和 T ，且 S 的所有元素都比 T 的元素要小。下面的步骤可以把它们连接成一棵树：

  • 伸展 S 中最大的节点。现在这个节点变为 S 的根节点，且没有右儿子。
  • 令 T 的根节点变为其右儿子。

分裂

对于分裂操作，如果我们需要在第 k 个结点右侧将序列分成两段，我们只需要将第 k 个结点旋转到根结点，并断开其与右子树的连接。得到的两棵新树对应着分成的两段序列。

优缺点

伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。

  • 可靠的性能——它的平均效率不输于其他平衡树。
  • 存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。

缺点

  • 伸展树最显著的缺点是它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的—— O(log n)。
  • 即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。

参考文献