数据结构与算法分析 04

查找结构

如果给定一个序列,你将如何在这个序列中查找一个给定元素 target,当找到时返回该元素的迭代器,否则返回末尾迭代器。首先排除时间复杂度 \(\mathcal{O}(N)\) 的朴素算法,这不是本文的重点。

二分法 (Dichotomy) 是一种思想,将一个整体事物分割成两部分,这两部分必须是互补事件,即所有事物必须属于双方中的一方且互斥。如此我们就可以在 \(\mathcal{O}(1)\) 的时间内将问题大小减半。

二分查找 (binary search),又称折半查找,这是一种可以在 \(\mathcal{O}(\log_{}{N})\) 时间复杂度下完成查找的算法。二分查找要求序列必须是有序的,才能正确执行:将序列划分为两部分,如果中间值大于 target,意味着这之后的值都大于 target,需要继续向前找;如果中间值小于 target,意味着这之前的所有值都小于 target,需要继续向后找。

上一篇介绍树时分析了 BST 中为什么很容易发生不平衡现象。在极端情况下,只有一个 leaf 的树,在查找元素时其时间复杂度退化为 \(\mathcal{O}(N)\) 。

为了防止 BST 退化为链表,必须保证其可以维持树的平衡,一次需要有一个 平衡条件 (balanced condition)。如果每个结点都要求其左右子树具有相同的高度,显然是不可能的,因为这样实在是太难了。在 1962 年,由苏联计算机科学家 G.M.Adelson-Velsky 和 Evgenii Landis 在其论文 An algorithm for the organization of information 中公开了数据结构 AVL (Adelson-Velsky and Landis) 树,这是计算机科学中 最早被发现的 自平衡二叉树。

AVL 树将子树的高度限制在差为 1,即一个结点,如果其左子树与由子树的高度差 \(|D_{h}| \leq 1\) ,则认为这棵树是平衡的。因此带有平衡因子 \(-1\) 、 \(0\) 或 \(1\) 的结点被认为是平衡的,而 \(-2\) 或 \(2\) 的平衡因子被认为是需要调整的。平衡因子可以直接存储于结点之中,也可以利用存储在结点中的子树高度计算得出。

简单地计算,一棵 AVL 树的高度最多为 \(1.44 \log_{}{(N + 2)} - 1.328\) ,实际上的高度只比 \(\log_{}{N}\) 稍微多一些。一棵高度为 \(h\) 的 AVL 树,其最少结点数 \(S(h) = S(h - 1) + S(h - 2) + 1\) ,\(S(0)=1, S(1) = 2\) 。而 AVL 的所有操作均可以在 \(\mathcal{O}(\log_{}{N})\) 复杂度下完成。

在进行插入操作时,和普通的 BST 类似,但是不一样的是需要更新路径上所有结点的平衡信息,并插入完成后有可能破坏 AVL 的特性。如果特性被破坏后,需要恢复平衡才能算插入结束。实际上,总可以通过简单的操作进行修正,这种操作被称为 旋转 (rotation)。

将必须重新平衡的结点叫作 \(\alpha\) ,由于任意结点最多有两个孩子,因此高度不平衡时, \(\alpha\) 点的两棵子树的高度差 2。这种不平衡可能出现在下面 4 中情况中:

  1. 对 \(\alpha\) 的左孩子的左子树进行插入
  2. 对 \(\alpha\) 的左孩子的右子树进行插入
  3. 对 \(\alpha\) 的右孩子的左子树进行插入
  4. 对 \(\alpha\) 的右孩子的右子树进行插入

情况 1 和 4 关于结点 \(\alpha\) 镜像对称,情况 2 和 3 关于结点 \(\alpha\) 镜像对称。因此从逻辑上来讲,我们只需要考虑两种情况,而编程时需要考虑上面介绍到的所有 4 种情况。

情况 1 是插入发生在「外边」的情形,我们称之为 一字形 (zig-zig),可以用 单旋转 (single rotation) 解决。假设结点 \(n\) 不满足 AVL 平衡性质,因为其左子树比右子树深 2 层,可以对其进行单旋转修正。修正的过程是:将左子树的根 \(l\) 向上移动一层,而将 \(n\) 向下移动一层, \(n\) 作为 \(l\) 的孩子出现在树中。下图展示了插入后出现不平衡的结点 (红色) 、如何旋转、多余子树如何处理以及子树的层数 (蓝字)。

对应的情况 4 也是 zig-zig,只需要旋转的方向与操作相镜像即可处理。

对于情况 2 、 3 来说,插入在「树内」从而导致 AVL 树无效,这种情况被称为 之字形 (zig-zag),而子树太深通过 single rotation 无法让树平衡,解决这种内部的情形需要 * 双旋转* (double rotation) 解决。

对应的情况 3 也是 zig-zag,只需要旋转的方向与操作相镜像即可处理。

可以发现,无论单旋转与双旋转,它都由两个最基本的操作组成:将结点进行左旋 (left rotation) 或右旋 (right rotation),并将多余的一棵子树挂载到下降结点上。Wikipedia 用以下这幅图概括了 4 种情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 左旋
void rotate_left(Node* node) {
  Node* child = node->right;
  node->right = child->left;
  if (child->left != nullptr) {
    child->left->parent = node;
  }
  child->parent = node->parent;
  child->left = node;
  node->parent = child;
  return child;
}
// 右旋
void rotate_right(Node* node) {
  Node* child = node->left;
  node->left = child->right;
  if (child->right != nullptr) {
    child->right->parent = node;
  }
  child->parent = node->parent;
  child->right = node;
  node->parent = child;
  return child;
}

在进行编程时,可以首先定义左右旋这两种基本操作,在根据情况判断如何组合。对于编程细节,远比理论多得多,编写正确的 loop 算法相对于 recursion 并不是一件容易的事,因此更多的会使用 recursion 进行实现。

还有一个重要问题是如何高效的对高度信息进行存储,可以采用平衡因子作为存储而不是一个 int 类型的高度,或者更近一步,利用 2 bit 存储平衡因子 (毕竟只有 3 个状态)。如果你希望将其隐藏到指针中,也是个不错的选择。存储平衡因子将得到些许速度优势,但丧失了简明性,如果你使用隐藏于指针的方法,更加剧的这一问题,不过好消息是你能为此剩下不少内存空间。最后,以 Wikipedia 上一副构建 AVL 树的动图作为本小节的结束吧。

AVL 树的移除与 BST 相当,同样地,移除操作可能会破坏 AVL 特性,因此我们在移除元素后,同样需要对树进行平衡才能算操作完成。

或许你没有听过这种数据结构,但是它确实存在且就在这里。 伸展树 (splay tree) 是一种相对简单的数据结构,它保证从空树开始任意连续 M 次对树的操作最多花费 \(\mathcal{O}(M \log_{}{N})\) 的时间。这种保证并不排除单次花费 \(\mathcal{O}(N)\) 时间的可能,并且也不保证每次操作的最坏情况都是 \(\mathcal{O}(\log_{}{N})\) 的,不过好在实际上是一样的。当 M 次操作的序列总的最坏情况花费 \(\mathcal{O}(Mf(N))\) 时间,我们就说它的 摊还 (amortized) 运行时间为 \(\mathcal{O}(f(N))\) 的。因此 splay tree 的每次操作的摊还时间复杂度为 \(\mathcal{O}(\log_{}{N})\) 。

当然 splay tree 有着一个事实基础:对于 BST 来说,每次操作最坏情形花费 \(\mathcal{O}(N)\) 并非不好,只要它相对不常发生就行。为了保证 amortized,splay tree 进行一个结点访问就会发生移动操作,它要经过一系列旋转操作被推到 root 上。但是当这个结点过深时,重新将这棵树构造为平衡树可能会花费比旋转更少的时间。

实际上,从 splay tree 中也可以看出局部性思想,当一个结点被访问时,它与其附近的结点可能会被频繁的访问,而远端的结点可能很难被访问到。当抖动发生时,splay tree 将会面临非常巨大的开销,因为它总是需要调整较深层的结点。

在实现 splay tree 时,访问一个结点并将其推向 root 时,最简单的方法就是 单旋转 ,即该结点与其父结点实施旋转操作。很明显这可以将一个很深的叶结点推向 root,但其父结点也被推向了与其差不多的深度。

伸展 (splaying) 的方法类似于旋转,不过在从底向上的旋转上,有些其他操作。

令 X 是访问路径上的非根结点,在这个路径上实现旋转。如果 X 的 parent 是树根只需要旋转 X 与其 parent 即可;否则需要考虑如下情况:

  1. 之字形 (zig-zag):只需要像 AVL 一样执行双旋转
  2. 一字形 (zig-zig):将 X 作为根,父结点和祖父结点分别是其孩子的结点,多余子结点向上过继

我们一直认为始终将数据存储于 RAM 中,而不是磁盘中,但如果数据太大以至于不得不放在磁盘时,大 \(\mathcal{O}\) 模型将不再适用。因为 \(\mathcal{O}\) 认为所有操作是相等的,但是涉及磁盘 IO 时,它的代价实在太高了。绝大多数情况下控制运行时间的是磁盘访问次数,因此我们更愿意一次从磁盘中取出大量数据并进行大量计算。

假设你现在将一棵 1000 万个结点的 BST 存储于磁盘之上,显然一棵不平衡的 BST 可能让你访问磁盘 1000 万次;如果你的存储结构是 AVL 树,那会好很多,绝大多数情况下你只需要 \(\log_{}{N}\) 而非 \(1.44 \log_{}{N}\) 次磁盘访问,这大概是 25 次磁盘访问。如果可以将这 1000 万结点的树,压缩到一个非常小的常数,哪怕是一个非常复杂的数据结构,对于 CPU 来说也是不成问题的。显然二叉树并不是一个好的选择,存储层数最低的完全二叉树的高度是 \(\log_{}{N}\) 。如果我们增加树的 degree,那么树的分支会极大增加,而深度却会急剧减少。这样的 M 路分支树被称为 M叉查找树 (M-ary search tree),可以明确的是 compelete M-ary tree 的高度是 \(\log_{M}{N}\) 。

为了防止 M-ary tree 退化,我们会为其加入更加严格的平衡条件,以保证其它的平衡。 1970 年 Rudolf Bayer 与 Edward M. McCreight 在波音研究实验室 (Boeing Research Labs) 发现了自平衡的 B树 (B-tree)。不过不像其他结构那样,两位作者都没有给出这里 B 的含义,你可以认为是 BalancedBayer 甚至是 Boeing,不过 Knuth 在 1980 年发表的论文 CS144C classroom lecture about disk storage and B-trees 中推测其中的含义可能是后两种。

实际上对于 B 树的相关定义与术语并不统一,阶 (order) 被 Knuth 定义为最大数量的子节点 (即最大数量的键加一)。Bayer 认为叶子层是最下面一层的键,而 Knuth 认为叶子层是最下面一层键之下的一层。而在实现上,叶子可能保留了完整的数据记录,也可能只保留了指向完整数据记录的指针。

根据 Knuth 的定义,一个 m 阶 B 树具有以下属性:

  1. 每个结点最多有 m 个子结点
  2. 除根外的所有内部结点最少有 \(\lceil\frac{m}{2}\rceil\) 个子结点
  3. 如果根结点不是叶结点,那么它至少有两个子结点
  4. 有 k 个子结点的非叶子结点拥有 \(k - 1\) 个键
  5. 所有的叶子结点都在同一层

我们定义一个结点最少拥有的子结点数 \(L = \lceil\frac{m}{2}\rceil\) ,而最多拥有的子结点数 \(U = m\) ;而包含的元素的个数最少 \(\lfloor\frac{m}{2}\rfloor\) 个,最多 \(m - 1\) 个。

根结点
拥有子结点数量的上限与内部结点相同,但没有下限。当树的元素数量小于 \(L - 1\) 时,根结点是唯一结点且没有任何子结点
叶子结点
没有子结点或指向子结点的指针,当然能存储的最大元素数依然是 \(m-1\)
内部结点
除叶结点与根结点外的所有结点,它们通常被表示为一组有序的元素和指向子结点的指针。每一个内部结点含有的子结点范围为 \([L, U]\) ,含有元素的数量在 \([L - 1, U - 1]\) ,而 \(U = 2L\) 或 \(U = 2L - 1\) ,因此所有内部结点至少是半满的

一个深度为 \(n+1\) 的B树可以容纳的元素数量大约是深度为 n 的B树的 U 倍,但是搜索、插入和删除操作的开销也会增加,当然开销的增加速度是极为缓慢的。B树在每一个节点中都存储值,所有的节点有着相同的结构。然而,因为叶子节点没有子节点,所以可以通过使用专门的结构来提高B树的性能。

对于所有平衡树来说,其都是建立在 BST 的基础之上,因此插入一个元素时都需要从根结点开始,找到新元素应该被添加的位置。当找到要插入的结点时,将会有以下情况:

  1. 如果结点拥有元素数量小于最大值,那么有空间容纳新元素,将元素插入到这一结点,并保持结点中的元素有序
  2. 否则这个结点已满,将它平均分裂成两个结点:
    1. 从该结点的原有元素和新元素中选择出中位数
    2. 小于这一中位数的元素放入左边结点,大于的元素放入右边结点
    3. 中位数元素将会被插入到父结点中,插入过程以同样的方法递归向上进行,直到元素被插入到树中。如果最终插入根结点但其已满,选出中位数作为新的根,将根结点分裂为两个结点作为新根的子结点

一般而言,移除一个元素首先定位到该元素并移除,然后调整树的约束条件使其满足。

  • 移除B树叶子结点中的元素,发生下溢出不满足B树约束时,进行再平衡
  • 由于内部结点的元素是左右两个子树的中间值,因此需要合并这两个子树,但可以肯定的是,左子树的所有元素依然小于右子树中的所有元素。
    1. 选择一个新的中间值 (左子树的最大值或右子树的最小值),将其替换掉被移除的元素,需要注意的是贡献新中间值的结点为叶子结点
    2. 判断贡献中间值的叶结点是否满足约束,如果不满足则从该叶子开始再平衡

可以发现,所有需要再平衡的结点都是从叶结点开始的,并向根结点进行,直到树重新平衡

  • 如果缺少元素结点的右兄弟存在且拥有多余的元素,那么进行左旋
    1. 将中间值复制到左子结点的最后
    2. 将中间值替换为右子结点的最小元素,并从右子结点中移除该元素
    3. 树已再次平衡,结束操作
  • 否则,如果缺少元素结点的左兄弟存在且拥有多余的元素,那么进行右旋
    1. 将中间值复制到右子结点的开始
    2. 将中间值替换为左子结点的最小元素,并从左子结点中移除该元素
    3. 树已再次平衡,结束操作
  • 否则,将其与一个直接兄弟结点以及中间值进行合并
    1. 将中间值、左子结点、右子结点都合并到一个结点上 (假设为左子结点),并将中间值和右子结点从父结点中移除
    2. 判断当前父结点的情况
      1. 如果父结点是根且父结点中没有其他元素,则将合并之后的结点作为新的根
      2. 如果父结点不是根,且父结点满足约束,则树已再次平衡,结束操作
      3. 如果父结点不满足内部结点的要求,对父结点进行再平衡操作。如果有多余的子树,则将这棵子树旋转给不平衡结点即可

B+树 (B Plus Tree) 是 B Tree 的一个变种。有人将 B-Tree 读作 B减树 是不正确的, B-Tree 中的 - 是一个连字符。既然是变种,那就有差异:

  1. 内部结点不再存储数据,只对其键进行存储,用以查找叶结点,数据全部由叶子结点存储
  2. 叶结点之间采用指针相连,你可以顺序从叶结点的头部遍历到尾部,而不需要其他额外的操作

如何选取键作为父结点的元素可以快速查找子结点,最简单的方法就是选取左子结点的最大值或右子结点的最小值,一般根据实现进行选择。

对 B+ 树操作时,与 B 树几乎一致,但区别是 B+ 树需要从叶结点开始递归向上,且 B+ 树需要修改父结点的分割值,而 B 树不用。

红黑树 (red-black tree) 是一种自平衡二叉树,于 1972 年由 Rudolf Bayer 发明,发明时被称为 对称二叉 B 树,现代名称红黑树来自 Knuth 的博士生 Robert Sedgewick 于 1978 年发表的论文。红黑树的结构复杂,但操作有着良好的最坏情况运行时间:它可以在 \(\mathcal{O}(\log_{}{N})\) 时间内完成查找、插入和删除操作。

红黑树是具有下列着色性质的 BST:

  1. 每个结点要么是黑色要么是红色
  2. 根是黑色的
  3. 如果一个结点是红色的,那么它的子结点必须是黑色的
  4. 从一个结点到一个 NULL 指针的每一条路径都必须包含相同数目的黑色结点

根据着色规则,red-black tree 高度最多是 \(2\log_{}(N+1)\) ,因此查找保证是一种对数的操作。当然还有一条约定,空结点 nullptr 我们假设其为黑色,这样我们可以在不违反约定的情况下,方便操作。

通常困难在于将一个插入一个新结点后,如果将结点涂为黑色将违反性质 4,因为这会让路径上的黑色结点数量加一,但其他路径上黑色结点数量不变。

因此在插入结点时,默认结点为红色,父结点为黑色时,直接插入。在以下的情况中不再讨论这种情况。父结点是红色则会违反规则 3,在这种情况下必须修改树以满足所有性质。

如果新插入的结点 X 是红色的,它有父结点 P,兄弟结点 S,叔父结点 U,以及祖父结点 G。那么需要考虑几种情况:

  1. 如果 P、U 都是红色的,意味着 G 是黑色的,可以将 P、U 重绘为黑色将 G 重绘为红色,这样既不会违反规则 3 也不会违反规则 4。但是 G 之上的情况我们不知道,G 也可能是根,因此需要对 G 进行递归地向上进行重绘操作
  2. 如果 P 与 U 只有一个是红色的,意味着 G 是黑色的,而插入的 X 虽然不违反规则 4 但是违反了规则 3,迫使 X 或 P 变为黑色,而这样又会违反规则 4。为了让树再次符合要求,我们对其需要进行旋转操作并重绘结点颜色,其实这里的旋转操作与 AVL 树中是一致的,只是将结点的平衡因子转换为了颜色信息。
    1. 当 X、P、G 形成 zig-zig 时,我们采用 single rotation
    2. 当 X、P、G 形成 zig-zag 时,我们采用 double rotation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 该函数仅处理父结点是红色的情况,黑色情况则直接插入即可
// 使用头结点方便处理,头结点的 parent 指向 root,root 的 parent 指向 head
void insert_help(Node* node, Node* head) {
  // 当结点不是树的根或父结点是红色时,进行循环
  while (node != head->parent && node->parent->tag == RED) {
    Node* uncle = get_uncle(node);
    Node* grandparent = get_grandparent(node);
    Node* parent = node->parent;
    // 如果叔父结点不为空且为红色,符合情况 1
    if (uncle != nullptr && uncle->tag == RED) {
      parent->tag = uncle->tag = BLACK;
      grandparent->tag = RED;
      node = grandparent;
      continue;
    }
    // 判断 zig-zig 或 zig-zag 类型,进行相应的旋转
    if (parent == grandparent->left) {
      if (node == parent->right) { // l-r 的 zig-zag
        node = parent;
        parent = rotate_left(parent);
      }
      rotate_right(grandparent); // l-l 的 zig-zig
    } else {
      if (node == node->parent->left) { // r-l 的 zig-zag
        node = parent;
        parent = rotate_right(parent);
      }
      ratate_left(grandparent); // r-r 的 zig-zig
    }
    grandparent->tag = RED;
    parent->tag = BLACK;
  }
  head->parent->tag = BLACK;
}

自底向上的操作需要父指针或栈保存路径,而自顶向下时实际是对红黑树应用自顶向下保证 S 不会时红色的过程。

在向下的过程中,如果结点 N 有两个红色的孩子时,将孩子重绘为黑色,结点 N 重绘为红色。结点 N 与其父结点 P 都为红色时,将违反红黑树的着色性质,此时对其进行 zig-zig 或 zig-zag 旋转即可。至于叔父结点 U 在自顶向下的过程中排除了红色的可能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 自顶向下插入,value 是待插入的值
void insert(Node* node, Node* head, T& value, Node** pos = nullptr) {
  bool inserted = false;
  if (node == nullptr) { // 插入结点,默认为红色
    node = new Node(value);
    *pos = node;
    inserted = true;
  }
  if (node->left != nullptr && node->left->tag == RED &&
      node->right != nullptr && node->right->tag == RED) {
    node->left->tag = node->right->tag = BLACK;
    node->tag = RED;
  }
  head->parent->tag = BLACK;
  Node* gp = get_grandparent(node);
  Node* parent = node->parent;
  if (node->tag == RED && parent->tag == RED) {
    // 判断 zig-zig 或 zig-zag 类型,进行相应的旋转
    if (parent == gp->left) {
      if (node == parent->right) { // l-r 的 zig-zag
        parent = rotate_left(parent);
      }
      rotate_right(gp); // l-l 的 zig-zig
    } else {
      if (node == parent->left) { // r-l 的 zig-zag
        parent = rotate_right(parent);
      }
      ratate_left(gp); // r-r 的 zig-zig
    }
    gp->tag = RED;
    parent->tag = BLACK;
  }
  if (inserted) {
    return;
  }
  if (node->val < value) {
    insert(node->left, head, &node->left, value);
  } else {
    insert(node->right, head, &node->right, value);
  }
}

删除结点时,所有情况都可以归结于删除一个叶结点,因为删除带有两个孩子的结点,都可以与其左子树最大结点或右子树最小结点的值进行交换,这只改变了值没有改变颜色,并不影响红黑树的性质。之后删除交换后的叶结点即可。对于红色叶结点,我们可以将其直接删除,这不影响红黑树的结构,如果有孩子我们只需要用其孩子代替它即可。如此我们需要保证在自顶向下过程中保证叶结点是红色的。

假设当前结点是 N,其兄弟结点 S、父结点 P、叔父结点 U 和祖父结点 G。开始时需要将树根重涂为红色,沿树向下遍历,当到达一个结点时,确保 P 是红色、N 和 S 是黑色。在此过程中会遇到一些情况:

  1. N 有两个黑色的孩子,此时
    1. S 也有两个黑色的孩子,那么重涂反转 N、S、P 的颜色,树结构不变
    2. S 有红色的孩子,根据红色的孩子进行 signal rotate 或 double rotate。如果两个孩子都是红色,任选一个进行旋转即可
  2. N 有红色的孩子,此时向下递归
    1. 新的 N 是红色,继续递归
    2. 新的 N 是黑色,对 S 和 P 进行旋转,S 成为 P 的父结点,重绘 P 与 S 的颜色,即可得到红色的父结点 P。对于 P 来说,回到情况 1

二叉B树 (Binary B-tree) 是一种简单但颇有竞争力的实现,被称为 BB 树,可以理解为带有附加条件的红黑树:一个结点最多有一个红色的孩子。当然还有一些法则:

  1. 只有右孩子可以是红色的,这样总可以使用内部结点的右子树的最小结点代替该结点
  2. 递归地编写过程
  3. 信息存储在整数中,而不是 bit 与每个结点一起存储。这个信息主要是结点的层次信息
    1. 若是 1,则该结点是叶结点
    2. 是父结点的层次,则该结点是红色的
    3. 比父结点的层次少 1,该结点是黑色的

简单地,我们就可以得到一颗 AA 树。并且左孩子必然比其父结点低一个层次,右孩子可能比父结点低 0 或 1 个层次,但不会更多。

1
2
3
4
5
6
7
8
9
struct AANode {
  Comparable element;
  AANode* left;
  AANode* right;
  int level;
  AANode() : left(nullptr), right(nullptr), level(1) {}
  AANode(const Comparable& e)
      : element(e), left(nullptr), right(nullptr), level(1) {}
};

水平链接 (horizontal link) 是一个结点与同层次上的孩子所建立的链接,这种水平链接都是右链接,并且不含有两个连续的水平链接。

不过这有一些情况需要注意,插入新结点时,可能导致左水平链 (插入 2) 或连续两个右水平链 (插入 45)。通过右旋可以消除掉左水平链,而左旋则可以消除多余的右水平链,这两个过程分别称为 skew 和 split。

由于新建了一个左水平结点或连续右水平结点,会引起结点 N 的原始父结点 P 的一些问题,这些问题可以通过上滤 skew/split 的方法解决。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void skew(AANode* node) {
  if (node->left->level == node->level) {
    rotate_right(node);
  }
}
void split(AANode* node) {
  if (node->right->right->level == node->level) {
    rotate_left(node);
    ++node->level;
  }
}

有了上述基础,AA 树的插入操作可以说是相当简单,和非平衡 BST 的插入实现基本一致。

1
2
3
4
5
6
7
void insert(const Comparable& val, AANode*& root) {
  root == nullptr ?
      static_cast<void>(root = new AANode(val)) :
      insert(val, val < root->element ? root->left : root->right);
  skew(root);
  split(root);
}

删除操作对比插入操作就会复杂许多。但是值得注意的是,我们为了编程更加容易增添了一些法则,这些法则为我们去除了一些特殊情况。可以肯定,若结点不是叶结点,那么它一定有右结点,那么在删除操作时,总可以使用右子树上最小的孩子替代这个结点,保证它是在第一层。在递归过程中,非叶结点的层次可能会被破坏,实际上只有递归路径上的子结点可能受到影响,我们依然需要处理这些情况。

以上图 AA 树为例,删除值为 1 的结点时,结点 2 和 5 成为第一层结点,结点 3 与 5 之间引入了 左水平链接 。实际上,只需要三次 skew 与两次 split 就可以完全重新安排这些水平的边。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void remove(const Comparable& val, AANode* root) {
  if (root == nullptr) {
    return;
  }
  static AANode* last_node = root;       // 寻找替换结点
  static AANode* deleted_node = nullptr; // 待删除结点
  if (val < root->element) {
    remove(val, root->left);
  } else {
    deleted_node = root;
    remove(val, root->right);
  }
  if (root == last_node) {
    // 如果 val 结点是叶结点,直接删除
    if (deleted_node == nullptr || val != deleted_node->element) {
      return;
    }
    deleted_node->element = root->element;
    deleted_node = nullptr;
    root = root->right;
    delete last_node;
  } else {
    // 不是树的底部,需要对其进行平衡
    if (root->left->level < root->level - 1 ||
        root->right->level < root->level - 1) {
      if (root->right->level > --root->level) {
        root->right->level = root->level;
      }
      skew(root);
      skew(root->right);
      skew(root->right->right);
      split(root);
      split(root->right);
    }
  }
}

对于任意序列,希望得到一个与 BST 的平均时间复杂度相匹配的期望时间界。对于最简单的 \(\mathcal{O}(N)\) 时间界的链表,如果每隔一个结点额外附加一个到其前面两个位置的链,那么最多只需要考察 \(\lfloor N/2 \rfloor + 1\) 个结点。扩展这种思路,每隔三个、五个等等结点增设一个新链,将缩小时间界,但大幅浪费了存储空间,并且有效插入过于呆板。

对于上图,类似二分搜索,每个结点都必须带有指向前 \(2^i\) 个结点的链接。如果取消掉这一限制,改为对于有 k 个链的结点称为 k 阶结点 (level k node),那么任意 k 阶结点的第 i 阶链接的下个结点,至少为 i 阶结点 (\(k \ge i\))。我们需要在插入新元素时就决定其是多少阶结点,可以肯定一般有 \(\frac{1}{2^i}\) 个结点是 \(i\) 阶的。因此只需要生成结点时以这个概率随机选择结点的阶数即可。即可得到一个随机化的跳跃表。

执行插入操作时,在头结点从最高阶的链开始,沿着链一直走,直到下一个结点大于查找值或为 null,此时,转到下一阶继续该策略。直到找到目标结点后,将新结点插入到其后,需要注意的是新结点的阶是随机的。而这一操作期望开销为 \(\mathcal{O}(\log_{}N)\) 。

与散列表类似,跳跃表需要估计表中元素的数目,从而确定阶的数目。

将红黑树的某些想法应用到跳跃表时,可以保证对数最坏情形操作。本节主要展示 1-2-3 确定性跳跃表 (deterministic skip list),为确定性跳跃表添加一个平衡条件:每个间隙容量为 1、2 或 3。

首先有些概念需要确定:

  1. 两个元素之间至少存在一个链,即从一个元素直接指向另一个元素,这两个元素才能被称为链接的
  2. 两个高度 h 相链接的元素,之间的 间隙容量 (gap size) 等于它们之间高度为 \(h - 1\) 的元素的个数

为了执行插入操作,必须保证当一个高度为 h 的新结点加入进来时不会产生具有 4 个高度为 h 的结点间隙。这很好解决,使用像红黑树一样的自顶向下的方法即可。假设现在位于第 L 层上,要降到下一层去,如果降到间隙容量为 3 的层,则提升该间隙的中项使其高度为 L,从而形成两个容量为 1 的间隙。

而在删除操作时相对困难一些,主要是间隙容量为 1 时。此时需要放大间隙容量,或从相邻的间隙中借来一些结点,或降低分隔结点的高度。

直接实现是困难的,需要注意的是,当一个高为 \(h\) 的结点提升到高 \(h + 1\) 的时候,不能花费时间 \(\mathcal{O}(h)\) 用于将 h 个链复制到一个新数组,否则时间界就会变为 \(\mathcal{O}(\log^2 N)\) 。真正实现的跳跃表结构与逻辑结构有一定的差别。

可以发现有些结点出现了多次,实际上一个结点的高度为 h,那么它就会出现 h 次。而实现中,每个结点都有两个指针域,而尾结点使用 \(\inf\) 代替,以简化实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct SkipNode {
  Comparable element;
  SkipNode* right;
  SkipNode* down;
  SkipNode() = default;
  SkipNode(const Comparable& e = Comparable(),
           SkipNode* rt = nullptr, SkipNode* dt = nullptr)
      : element(e), right(rt), down(dt) {}
};
class DSL {
 private:
  Comparable INFINITY;
  SkipNode* header;
  SkipNode* bottom;
  SkipNode* tail;
 public:
  explicit DSL(const Comparable& inf) : INFINITY(inf) {
    this->bottom = new SkipNode();
    this->bottom->right = this->bottom->down = this->bottom;
    this->tail = new SkipNode(INFINITY);
    this->tail->right = this->tail;
    this->header = new SkipNode(INFINITY, tail, bottom);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void insert(const Comparable& val) {
  SkipNode* curr = this->header;
  this->bottom->element = val;
  while (curr != this->bottom) {
    while (curr->element < val) {
      curr = curr->right;
    }
    if (curr->down->right->right->element < curr->element) {
      curr->right =
          new SkipNode(curr->element, curr->right, curr->down->right->right);
      curr->element = curr->down->right->element;
    } else {
      curr = curr->down;
    }
  }
  if (this->header->right != this->tail) {
    this->header = new SkipNode(INFINITY, this->tail, this->header);
  }
}