数据结构与算法分析读书笔记系列12-高级数据结构

伸展树（splay tree），它保证从空树开始任意连续M次对树的操作最多花费O(MlogN)时间。

伸展树的基本想法是，当一个节点被访问，它就要经过一系列AVL树的旋转被放到根上。注意，如果一个节点很深，那么在其路径上就存在许多的节点也比较深，通过重新构造可以使所有这些节点的进一步访问所花费的时间变少。因此，如果节点过深，那么我们还要求重新构造应具有平衡这棵树（到某种程度）的作用。

当一项X作为一片树叶插入时，称为展开（splay）的一系列树的旋转使得X成为树的新的根。展开操作也在查找期间执行，而且如果一项也没有找到，那么就有对访问路径上的最后的节点施行一次展开。

这种展开操作的直接实现需要从根沿树往下的一次遍历，以及而后的从底向上的一次遍历。

下面指出如何在初始路径上施行一些旋转，以更快的过程得到结果。

红黑树（red black tree）是AVL树流行的另一变种。

红黑树是具有下列着色性质的二叉查找树：

• 每个节点或者着成红色，或者着成黑色。
• 根是黑色的。
• 如果一个节点是红色的，那么它的子节点必须是黑色的。
• 从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。

着色法则的一个推论是，红黑树的高度最多是2log(N+1)。因此，查找保证是一种对数的操作。

和通常一样，困难在于将一个新项插入到树中。通常把新项作为树叶放到树中。如果我们把该项涂成黑色，那么我们肯定违反条件4，因为将会建立一条更长的黑节点的路径。因此这一项必须涂成红色。如果它的父节点是黑的，我们插入完成。如果它的父节点已经是红色的，那么我们得到连续红色节点，它就违反了条件3。在这种情况下，我们必须调整该树以确保条件3满足（且又不引起条件4被破坏）。用于完成这项任务的基本操作是颜色的改变和树的旋转。

通过运用红黑树的一些想法可以应用到跳跃表以保证对数最坏情形操作。下面，描述产生数据结构的最简单的实现方法，1-2-3确定性跳跃表（deteministic skip list）。

为使O(logN)这个界成为最坏情形的界，我们需要保证只有常数个前向指针需要考查直到下降到更低的一层。为此，我们添加一个平衡条件。首先需要两个定义。

• 定义：两个元素称为是链接的（linked），如果至少存在一个指针从一个元素指向另一个元素。
• 定义：两个在高度为h链接的元素间的间隙容量（gap size）定于它们之间高度为h-1的元素的个数。

1-2-3确定性跳跃表满足这样的性质：每个间隙（除在头和尾之间可能的零间隙外）的容量为1、2或3。

显然，当我们沿任一层行进仅仅通过常数个指针然后就可以下降到低一层。因此，在最坏的情形下查找的时间是O(logN)。

为了执行插入，我们必须保证当一个高度为h的新节点加入进来时不会产生具有四个高度为h的节点的间隙。实际上这很简单，我们采用类似于红黑树中所做的自顶向下的方法即可。

设我们在第L层上，并正要降到下一层去。如果我们要降到的间隙容量是3，那么我们提高该间隙的中间项使其高度为L，从而形成两个容量为1的间隙。由于这使得朝向删除的道路上消除了容量为3的间隙，因此插入是安全的。

删除的困难出现在间隙容量为1的情况。当我们看到将要下降到一个容量为1的间隙时，我们把这个间隙放大：或者是通过从相邻间隙（如果容量不为1）借来的方式，或者通过降低该间隙与邻间隙分开的节点的高度的方式。由于这两个都是容量为1的间隙，因此结果变成容量为3的间隙。

整个过程实现的细节：

1. 当我们将1个高为h的节点提升到高h+1的时候，我们不能花费时间O(h)用于将h个指针拷贝到一个新数组。否则，插入的时间界就要变成O(log² N)了。一种合理的方法是用一个链表表示高度为h的节点中的h个前向指针。由于我们是沿着各层向下行进，因此一个节点的链表是以第h层前向指针开始并以第一层前向指针结束。
2. 优化更复杂而且可能占有一些空间。我们不是把节点作为一项和前向指针的链表来存储，而是存储前向指针和前向项对的链表。

注意：有些项出现是多于一次的。事实上，如果一个节点在抽象表示中的高度为h，那么它的项在实际实现中就会出现在h个地方。

确定性跳跃表插入过程考虑的情况比红黑树少得多。我们所付出的代价似乎是空间：在最坏的情况下我们有2N个节点，每个节点包含两个指针和一项。对于红黑树，我们有N个节点，每个节点包含两个指针、一项以及一个颜色位（bit）。因此，我们可能要用到两倍多的空间。可是，事情没有糟到那一步。首先，经验指出，确定性跳跃表平均使用大约1.57N个节点。其次，在某些情况下，确定性跳跃表实际使用的空间少于红黑树。（如某些机器上一个附加位（bit）是非常昂贵的）。确定性跳跃表的性能似乎比红黑树要强。

正如存在链表形式和水平数组形式的高阶B树一样，我们也有这两种形式的高阶确定性跳跃表。哪种方法最好，可能紧密依赖于特定的系统和应用。

因为大量可能的旋转，红黑树的编程相当复杂，特别是删除操作。确定性跳跃表的编程虽然在一定程度上要少一些，但仍然是相当复杂的，这由所需的三个标记可以看出。当然，确定性跳跃表中的删除是一项非平凡的工作。这一节，描述二叉B-树（binary B-tree）一种简单但颇具竞争力的实现方法，这种树叫做BB-树。BB-树是带有一个附加条件的红黑树变种：一个节点最多可以有一个红儿子，也类似2-3B树。

编程的一项法则：

1. 首先，我们加入只有右儿子可以是红的条件，这就消除了约一半的可能重新构建的情形。它也消除在删除算法中一个恼人的情形；如果一个内部节点只有一个儿子，那么这个儿子一定是右儿子（它刚好是红色的），因为黑色左儿子将会违反红黑树的条件4.因此，我们总可以用一个内部节点的右子树中的最小节点代替该内部节点。
2. 我们递归地编写这些过程。
3. 我们把信息存在一个短（short）型数（例如8个比特）中，而不是把一个颜色位（bit）和每个节点一起存储。这个信息就是节点的层次（level）。节点的level相当于红黑树中的节点的黑高度。
   • 若该节点是树叶，节点的层次是1
   • 若节点是红的，节点的层次是它的父节点的层次
   • 若节点是黑的，节点的层次比它的父节点的层次少1

如此得到的结果是一颗AA-树。

如果我们将AA结构要求从颜色转换成层次，那么我们看到，左儿子必然比它的父节点恰好低一个层次，而右儿子可能比父节点低0或1个层次（但不会更多）。

水平链接（horizontal link）是一个节点与同层次上的儿子之间的连接。这种结构需求使得水平链接是向右的指针，并且不能有两个连续的水平链接。

• 禁止出现连续两个水平链接，水平链接也可解释为一个节点跟它的右孩子节点的level相同（左孩子节点永远比它的父节点level小1）.这个规定其实相当于红黑树中不能出现两个连续的红色节点。
• 禁止向左的水平链接，也就是说一个节点最多只能出现一次向右的水平方向链。这个因为向左的水平链接相当于左孩子能为红色节点，这在AA树的定义中是不允许的。

在这两种情况下一次单旋转都可以使问题得到解决：通过右旋转消除左水平链接，通过左旋转消除连续的右水平链接。这些过程分别叫做Skew和Split。Skew就是一个右旋转，split就是一个左旋转，但二者不是互逆的。一次Skew除去一个左水平链接，但可能会创建连续的右水平链接，因此我们首先执行Skew，然后再Split。在一次Split之后，中间节点R的层次增加。由于新建一个左水平节点或连续的右水平节点，因而引起X的原来父节点的一些问题，这两个问题都可以通过上滤Skew/Split的方法解决。如果们使用递归算法，那么这可以自动地完成。

当然，删除操作是更复杂的，不过，由于我们除去了许多的特殊情况，程序代码实际上是相当合理的。如果一个节点不是树叶，那么它必然有一个右儿子，这意味着，当删除一个节点的时候，我们总可以用其右子树上最小的儿子代替这个节点，这保证它是在第一层上。

为了查看是否那些非叶子节点的层次被一次递归调用所破坏，需要检查这些非叶子节点。令T为当前节点。如果删除将T的一个儿子的层次降低到比T的层次低2，那么T的层次也需要降低。此外，如果T有一个右红儿子，那么T的右儿子也必须将它的层次降低。此时可能在一个层次上有6个节点：T，T的右红儿子R，R的两个儿子，以及这些儿子的右红儿子。

如果删除来自左边，可能会引入左水平链接，需要两次旋转，这种情况不涉及当前节点T。另一方面，如果删除来自右边，那么T的左节点可能忽然之间变成水平的；这也需要一次类似的双旋转（从T开始）。为了避免测试所有这些情形，我们只要调用三次Skew即可。一旦调用完成，则再调用两次Split就足以重新安排这些水平的边。

讨论的最后一种二叉查找树可能是最简单的，叫做treap树(tree-heap树堆)。它像跳跃表一样使用随机数并且对任意的输入都能给出O(logN)的期望时间的性能。查找时间等同于非平衡二叉树（比平衡查找树慢），而插入数据只比递归非平衡二叉查找树的实现方法稍慢。虽然删除操作要慢的多，但仍然是O(logN)期望时间。

treap树相对比较简单。树中的每个节点存储一项，一个左和右指针，以及一个优先级，该优先级是建立节点时自定指定的。一个treap树就是一颗二叉查找树，但其节点优先级满足堆序性质；任意节点的优先级必须至少和它父亲的优先级一样大。因此根节点的优先级最低。

treap树的插入操作，在一项最为树叶插入之后，我们将它沿着该treap树向上旋转直到它的优先级满足堆序为止。可以证明旋转的期望次数小于2。

treap树的删除操作，在要被删除的项找到之后，通过把它的优先级增加到∞并沿着低优先级诸儿子的路径向下旋转而可将其删除。一旦它是树叶，就可以把它删除。对于删除，注意当节点逻辑上是树叶时，它仍然有NullNode作为它的左儿子和右儿子。因此，它与右儿子旋转，在旋转后，T为NullNode，而右儿子被释放。

treap树特别容易实现是因为我们不必担心调整优先级域。平衡树处理方法的困难之一是一次操作过程中未能更新信息而导致错误。和其它插入和删除的程序相比，treap树，特别是以非递归方法的实现，更加的容易。

k-d树（k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用多种应用场合，如多维键值搜素（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（binary space partitioning）的一种特殊情况。

二维查找树具有简单的性质：在奇数层上的分支按照第一个关键字进行，而在偶数层上的分支按照第二个关键字进行。根是任意选取的奇数层。向一棵2-d树进行插入操作是向一棵二叉查找树插入操作的扩展：在沿树下行时，我们需要保留当前的层。为保持程序代码简单，我们假设基本的项是两个元素的数组。此时我们把层限制在0和1之间。

一棵随机构造的2-d树与一棵随机二叉查找树具有相同的结构性质：高度平均为O(logN)，但最坏情形则是O(N)。

不像二叉查找树有精巧的O(logN)最坏情形的变种存在，没有已知的方案能够保证一棵平衡的2-d树。问题在于，这样一种方案很可能基于树的旋转，而树旋转在2-d树中是行不通的。我们能够做的最好的办法是通过重新构造子树来定期地对树进行平衡。

正交范围查询（rang query）给出其第一个关键字在一个特殊的值集合之间且第二个关键字在另一个特殊的值集合之间的所有的项。我们可以要求精确的匹配，或者基于两个关键字中的一个关键字匹配；后者称为部分匹配查询(partial match query)。这两种都是（正交）范围查询的特殊情形。

配对堆是一种实现简单、均摊复杂度优越的堆数据结构，配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法，配对堆是一个更优的选择，且支持以下操作（假设该堆是最小堆）：

• find-min(查找最小值)：返回堆顶。
• merge（合并）：比较两个堆顶，将堆顶较大的堆设为另一个的孩子。
• insert（插入）：创建一个只有一个元素的堆，并合并至原堆中。
• decrease-key（减小元素）（可选）：将以该节点为根的子树移除，减小其权值，并合并回去。
• delete-min（删除最小值）：删除根并将其子树合并至一起。

唯一比较复杂的操作是堆中最小值的删除操作。标准方法是（两趟合并法）：首先将子堆从左到右、一对一地合并，然后再从右到左合并该堆。

上面，我们看到二叉查找树的几种有效的变种。自顶向下伸展树提供O(logN)摊还性能，treap树给出O（logN）随机化的性能，而红黑树、确定性跳跃表和AA-树则均给出对基本操作的O(logN)最坏情形性能。k-d树给出了执行范围查找的实际方法。配对堆是最实际的可合并的优先队列，特别是当需要DecreaseKey操作的时候。