404blog
🖊️ 计算机学院 高级数据结构 （Advanced Data Structure）
404
  2024 年 02 月 26 日 18:57   2024 年 03 月 27 日 08:26

Basic info

课程名：高级数据结构 （Advanced Data Structure）

主讲教师： $\mathbf{A.P.}$ $\mathrm{Yao-Xiang\;Ding}$

E-mail：$\mathrm{[email protected]}$

分数占比：

  • Assignment $10\%$
  • 讨论 $10\%$
  • Research Project $30\%$
  • Midterm $10\%$
  • Final $40\%$

教材：

  1. $\mathrm{Mark\; Allen\; Weiss}$, Data Structure and Algorithm Analysis in C (2nd Edition)
  2. $\mathrm{Thomas\; H.\; Cormen}$, Introduction to Algorithms (3rd Edition)
  3. $\mathrm{Jon\; Kleinberg}$, Algorithm Design

课程网站：Github Page

Lec 1 : Balanced BST

尽管二叉搜索树可以在一定程度上加快搜索的过程，但其仍有问题。在最差的情况下，即树的每层都只有一个节点时，搜索的复杂度达到 $O(N)$ .

此时，对于除叶节点以外的任何一个节点，他必有一个子树为空，而另一个子树非空。直观上来看这样的树就是“不平衡”的，而假如一个树是完美二叉树或者完全二叉树，对其搜索的复杂度就可以达到或接近 $O(\log n)$ .

因此，一个树越“平衡”，搜索的复杂度越低，我们希望找到一种具备这种平衡性的优化的 BST . 在此之前我们先来定义何为“平衡” .

Height Balance

$【\mathbf{Def}】$ 树的高度平衡：空树是平衡树. 若某树 $T$ 有其左子树 $T_L$ 和右子树 $T_R$，那么树 $T$ 是高度平衡的，当且仅当

  1. $T_L$ 和 $T_R$ 都高度平衡.
  2. $T_L$ 和 $T_R$ 的高度差的绝对值小于等于 $1$.

$【\mathbf{Def}】$ 节点的平衡因数
$n$ 为树的某个节点，$h_L$ 和 $h_R$ 分别为其左右子树的高度，节点的平衡因数$BF(n)=h_L -h_R.$ 对于高度平衡树而言，$BF(n)=-1,0$ 或 $1$. 如果某个节点 $n$ 的平衡因数大于等于 $2$ ，称这个节点失衡.

AVL Trees

$\mathrm{Adelson}$-$\mathrm{Velskii}$-$\mathrm{Landis}$ 树由苏联数学家格奥尔吉·马克西莫维奇和米哈伊洛维奇·兰迪斯发明.

AVL 树是一种自平衡树，自平衡树可以动态的调整树的结构，使树在插入、删除等操作的过程中保持其平衡性。

AVL 树的特点在于旋转操作，这种操作可以在不破坏 BST 特性（即不改变中序遍历）的前提下，使失衡的节点恢复平衡，旋转操作分为四种，分别为左旋（RR），右旋（LL），先左旋再右旋（LR），先右旋再左旋（RL）.

► 单旋操作

Fig. 1

如图展示了一种简单的失衡情况：根节点 $T$ 发生失衡，这一失衡是节点 $R$ 造成的，因此可以对节点 $R$ 进行旋转. 变成如下平衡树:

Fig. 1 After Rotation

单个旋转操作需要保证 BST 的性质不被破坏，如图所示的情况需要将 $R$ 旋转至 $T$ 的位置，而 $T$ 将会成为 $R$ 的左子节点，应当对 $R$ 原本的左子节点 $RL$ 进行调整，使之不破坏 BST 的性质.
Fig. 2

单旋操作的一个实现(以左旋为例)：

1
2
3
4
5
6
7
8
Tree sRoL(Tree t) {
    Tree tl   = t->Left;
    t->Left   = tl->Right;
    tl->Right = t;
    t->h      = max(t->Left->Height, t->Right->Height) + 1;
    tl->h     = max(getHeight(tl->Left), t->h) + 1;
    return tl; 
}

► 双旋操作

有些情况下，对失衡节点无论单旋几次都无法解决失衡，而需要先对失衡节点的子节点先进行旋转，例如如下 BST:
Fig. 3
由于失衡是节点 $LRL$ 带来的，而先对 $L$ 进行左旋
Fig. 3 After First Rotation
再对节点 $T$ 进行右旋，使之完全平衡
Fig. 3 After Second Rotation
双旋操作的一个实现(先左旋再右旋)：

1
2
3
4
Tree dRoR(Tree t) {
    t->Right = sRoL(t->Right);
    return sRoR(t);
}

Splay Trees

伸展树是一种能够自我平衡的 BST, 他能够在均摊的 $O(\log n)$ 时间内完成插入、查找等操作。

伸展树的一个重要特点是，当一个节点 $n$ 被访问过后，会通过一系列旋转操作将 $n$ 移动到根节点处，最近访问的节点会离根节点更近，且伸展树将会越来越平衡.

旋转操作由以下因素决定：

  • $n$ 是其父节点 $p$ 的左子树还是右子树
  • $n$ 的父节点 $p$ 是否是根节点
  • $n$ 的父节点 $p$ 是其父节点 $q$ 的左子树还是右子树

针对不同的情况，伸展树的操作有以下几种：

► Zig或Zag

当 $p$ 为根节点时进行，Zig 操作直接对 $p$ 进行右旋，而Zag 操作与之相反.
Fig. 4 Zig

► Zig-Zig或Zag-Zag

当 $p$ 不为根节点，且 $n$ 和 $p$ 均为左儿子或均为右儿子，Zig-Zig 操作先对 $q$ 进行右旋，再对 $p$ 进行右旋. Zag-Zag 操作与之相反.
Fig. 4 Zig-Zig

► Zig-Zag或Zag-Zig

当 $p$ 不为根节点，且 $n$ 和 $p$ 有一个是左儿子，另一个是右儿子的时候，Zig-Zag 操作先对 $p$ 进行左旋，再对 $q$ 进行右旋. Zag-Zig 操作与之相反.
Fig. 4 Zig-Zag

伸展树的操作基于树的旋转操作，因此三类操作都保证树的先序遍历不改变
做题时可以利用这一特征，记住操作前后树的形状和 $n$, $p$, $q$ 三个节点的顺序即可

Amortized Analysis

对于某种数据结构，如果他的某几个特定操作速度较慢，但大多数操作速度较快，我们可以通过使用摊还分析计算多个连续的操作的平均时间复杂度.

记最差时间为 $T_{worst}$ , 均摊时间为 $T_{amortized}$ , 平均时间复杂度为 $T_{average}$ , 那么有：

上一节提到伸展树可以在均摊的 $O(\log n)$ 时间内完成插入、查找等操作。因此任意 $m$ 个连续的操作最多使用 $O(m\log n)$ 时间.

以下展示一个简单的例子：对于一个栈，定义一种新的操作 multipop(s, k), 他可以连续的从栈 s 中出栈 k 个元素. 假设现在有 n 个由 push, pop, multipop 组成的操作序列.

由于 multipop 的最差时间复杂度为 $O(n)$， 那么这些操作的最差时间复杂度为 $O(n^2)$，事实上，这一结论非常正确，但他并不是一个确界，因为参数恰为 n 的 multipop 不可能被执行 n 次. 因此需要通过摊还分析得出更准确的最差时间复杂度，也即均摊时间复杂度

摊还分析的三种方法：聚合分析、核算法、势法

► 聚合分析

如果一系列的 $n$ 个操作总共的最差时间为 $T(n)$ . 那么平均每个操作的摊还消耗即为 $T(n)/n$ .

上面的例子中，pop 操作的次数至多与 push 次数相等，因此 n 个由 push, pop, multipop 组成的操作序列的最差时间复杂度为 $O(n)$, 均摊下来的每个操作复杂度即为 $O(1)$.

► 核算法

当一个操作的摊还消耗 $\hat{c_i}$ 超过了他的实际消耗 $c_i$ ，我们可以将这一差异“存”到一个“账户”中. 这一“账户”可以为之后实际消耗大于摊还消耗的操作“支付”差值.
令 $D_i$ 为第 $i$ 次操作后的数据结构，$c_i$ 为第 $i$ 次操作的实际代价，$\hat{c_i}$ 为第 $i$ 次操作的摊还代价.

对于任意 $n$ 个连续操作，我们有:

上面的例子中，三种操作的实际消耗分别是

  • push - $1$
  • pop - $1$
  • multipop - $\min\{s,k\}$

我们可以为这三种操作分别定价，由于 push 操作会带来一个潜在的 pop 或 multipop 操作，因此可以如下定价

  • push - $2$
  • pop - $0$
  • multipop - $0$

在 push 操作时，除了为该操作自己支付 $1$ 的消耗以外，还要为潜在的 pop 操作往账户中预存 1 的消耗. 在 pop 时直接从账户中取出即可. 只要账户余额大于等于 $0$, 这就意味着实际消耗的上界为摊还消耗，即 $O(n)$. 每个操作的平均摊还代价为 $O(1)$

► 势法

考虑某初始数据结构 $D_0$ 上的一系列操作 $Op_1,Op_2,\dots ,Op_n$ 这些操作引起数据结构的改变：

在势法中，我们记录某一步账户中预存的消耗为 $\Phi(D_i)$ （势能）. 由于 $\hat{c_i}-c_i$ 为第 $i$ 步中账户余额的改变量，即 $\Phi(D_i)-\Phi(D_{i-1})$, 移项可得：

为了开始势法的分析，我们需要为数据结构定义一个势函数：$\Phi:D\rightarrow \mathbf{R}_0^+$，这一函数满足：

  1. Typically, $\Phi(D_0)=0$.
  2. $\Phi(D_i)\ge\Phi(D_0)$, for all $i$.

Example : 势法分析 Splay 树均摊复杂度：
定义某结点 $X$ 的势函数为 $\sigma(X)=\log size(X)$ (对平衡树而言， $\log size(X)$ 接近树的高度)

那么整棵树的势函数便可定义为

满足势函数的条件. 接下来分析各种旋转操作下的势函数变化量：

  1. zig / zag 旋转
    Fig. 4 Zig
    这种情况下，只有节点 $n$ 和 $p$ 的势发生了变化，且 $n$ 和 $p$ 各自先后作为根节点时，其势能相同。记旋转后的节点为 $n^\prime$ 和 $p^\prime$. 则势能变化为：
  2. zig-zig / zag-zag 旋转
    Fig. 4 Zig-Zig
    类似的分析由于：$size(n)+size(q)=size(n)-1<size(n).$
    可得：
  3. zig-zag / zag-zig 旋转
    Fig. 4 Zig-Zag
    类似的分析:

单次 splay 操作的摊还代价: 对于一次 splay 操作，其可被拆分成上述若干旋转，有 可以得到 $O(\log n)$ 的摊还代价.

Lec 2 : Red-black Tree and B Tree

为了在插入和删除时减少旋转操作，我们有两种选择

  • 牺牲搜索的时间
  • 放宽平衡条件

M-Ary Search Trees

$m$ 叉搜索树与二叉搜索树类似，每个节点至多有 $m-1$ 个元素，这些元素将范围划分为 $m$ 个区间，每个区间各对应一条子树. 例如，下图展示了一种四叉搜索树：
4-ary tree

B Tree

B 树是一种特殊的平衡 $M$ 叉搜索树，他由两种节点构成：

  1. 内部节点 (Internal Nodes) : 储存数据以及指向子节点的指针
  2. 叶节点 (Leaf Nodes) : 只储存数据

【$\mathbf{Def}$】$M$ 阶 B 树有以下属性：

  1. 根节点要么是叶节点 (无子节点) 要么有 $[2,M]$ 个子节点.
  2. 所有非叶节点有 $[\lceil M/2\rceil,M]$ 个子节点.
  3. 有 $k$ 个子节点的内部节点拥有 $k-1$ 个键.
  4. 所有叶节点都在相同高度.

B 树的阶数 $m\ge 3$, 若 $m=2$, 此时的 B 树退化为平衡 BST.

► 搜索

从上到下对 $m$ 阶 B 树进行 $m$ 分查找，若找到包含目标值 $k$ 区间的节点，则继续在这个节点上进行线性搜索.

► 插入

假设要在一个以 $r$ 为根节点的 B 树中插入一个新节点 $k$ , 先进行搜索找到 B 树上包含该节点值的区间，这一区间对应了一个叶节点 $l$，要往这一叶节点中插入新的值，可以分为两种情况：

  1. $l$ 中键的数量小于 $m-1$:
    此时直接将 $k$ 的值作为键放入 $l$ 中并对 $l$ 中键重新排序即可. 以下图 4 阶 B 树为例：
    bin

  2. $l$ 中键的数量等于 $m-1$:
    此时 $l$ 节点已满，需要对这一节点进行拆分. 步骤如下:

    1. 选出 $l$ 的所有键值与 $k$ 的值的中位数 $u$.
    2. 小于 $u$ 的数进入左节点 $p$ 中.
    3. 大于 $u$ 的数进入右节点 $q$ 中.
    4. $u$ 上移至其父节点.
    5. 若 $u$ 的父节点也满，则对其父节点进行分裂

    6. 分裂停止或者产生了新的根节点

      以下图 4 阶 B 树为例，插入 17:
      bin2

► 删除

两元素叶节点或四元素叶节点中的元素可直接被删除. 若要删除非叶节点中的元素，类似于 BST, 先找到该元素右侧第一子树中最小的元素替代他（由于平衡性，必在叶节点上），如果这一元素所处的叶为两元素或三元素，直接删除即可，若仅有一个元素，则不可直接删除，因为这样会破坏 2-3-4 树的性质. 此时可以将父节点的元素移下来，并用该节点的兄弟节点的元素补充父节点（类似于旋转操作）如果没有非单元素的兄弟节点，可以讲父节点的元素直接移到某兄弟节点.

B+ Trees

B+ 树是一种特殊的 B 树，他在形式上和 B 树类似，包含以下几种节点：

  1. 根节点
  2. 内部节点
  3. 叶节点

【$\mathbf{Def}$】$m$ 阶的 B+ 树具有以下性质：

  1. 每个节点最多有 $m$ 个子节点
  2. 有 $n$ 个子节点的节点有 $n-1$ 个键值.
  3. 所有数据储存在叶节点中，每个叶节点的最右侧指针指向下一个叶节点.
  4. 内部节点用于作索引，仅含有其子树中的最小关键字.
  5. 除了根节点外，其他节点中所含键值至少有 $\lceil m/2\rceil$ (比同阶 B 树多一个).

► 2-3-4树

2-3-4 树是 $m=4$ 的 B 树，他具有 B 树的所有性质，也具有自己的一些特殊之处，在下文中会提到.

Red-black Tree

为了避免 2-3-4 树的插入和删除的复杂性，同时利用其优点，我们可以采用另一种特殊的二叉树——红黑树.

红黑树于 1972 年由 $\mathrm{Rudolf\; Bayer}$ 发明.

► 基本属性

【$\mathbf{Def}$】红黑树是一种具有以下性质的自平衡二叉搜索树

  1. 每个节点要么是红色的要么是黑色的.
  2. 根节点是黑色的.
  3. 叶节点 (NIL) 是黑色的.
  4. 如果一个节点是红色的，那么他必有两个黑色的子节点.
  5. 对于任何节点，所有从该节点到所有后代叶节点的路径包含相同数量的黑色节点.

以下是一个红黑树的例子：
rb tree
红黑树和 2-3-4 树是一一对应且可以互相转化的, 换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。

【$\mathbf{Def}$】节点 $x$ 的黑高度记作 $bh(x)$. 指的是该节点到某叶节点的路径上黑色节点的数量. 树的黑高度 $bh(T)$ 等于根节点的黑高度.

【$\mathbf{Lemma}$】有 $N$ 个节点的红黑树的高度至多为 $2\log_2(N+1)$.

【$\mathbf{Proof}$】
先证明：对任意以 $x$ 为根的子树 $T_x$, $sizeof(T_x)\ge2^{bh(x)}-1$.

  1. 若 $h(x)=0$ 即 $T_x$ 为空，$bh(x)=0$, 满足假设条件.
  2. 假设存在 $k$, 使得对于任意 $h(x)\le k$ 的情况，都有 $sizeof(T_x)\ge2^{bh(x)}-1$
  3. 对于 $x$ 使得 $h(x)=k+1$, 那么他的子树 $v$ 满足： $bh(v)=bh(x) $ 或 $bh(v)=bh(x)-1$. 由于 $h(v)\le k$, $sizeof(v)\ge2^{bh(v)}-1\ge2^{bh(x)-1}-1$. 因此 $sizeof(T_x)\ge2^{bh(x)}-1$

再证明 $bh(T)\ge h(T)/2$ : 显然.
因此 $sizeof(T)\ge2^{h(T)/2}-1$ $,h(T)\le2\log_2(sizeof(T)+1)$

类似于 AVL 树和伸展树，当红黑树的性质（红黑节点规则、平衡性）在插入、删除等操作时被破坏，需要通过某些节点的旋转操作来维护其属性. 相较于 AVL 树，红黑树可以减少旋转操作，这一点体现在删除上，对于 AVL 树，其在删除节点时旋转操作的次数为 $O(\log N)$,而红黑树的次数 $\le 3.$

► 插入

类似于 BST 的插入操作. 插入的节点总是红色的，当插入的节点的父节点也是红色的时候，需要通过旋转、改色来维护二叉树性质，并继续向上调整，直到碰到根节点或修复完成. 另外，维护前后黑色节点的数量应当不变.

这样的插入有数种情况, 为方便讨论，定义 $c$ 为当前插入的节点，$p$ 为 $c$ 的父节点，$g$ 为 $c$ 的祖父节点，$u$ 为 $p$ 的兄弟节点（ $c$ 的叔节点）

  1. $u$ 存在且为红色：$g$ 由黑变红，$p$ 和 $u$ 由红变黑 case1
  2. $u$ 不存在或是黑色，且 $c,p$ 和 $p,g$ 间左右一致 ：$g$ 右旋并变为红色，$p$ 变为黑色 case1
  3. $u$ 不存在或是黑色，且 $c,p$ 和 $p,g$ 间左右相反 ：$p$ 左旋之后，假装 $p$ 是新插入的节点，按照情况 2 处理.case1

► 删除

红黑树的删除操作较为逆天. 假设要删除的节点为 $v$, 被用来替代 $v$ 的节点是 $u$. 红黑树的删除可以遵循以下步骤：

  1. 标准的 BST 删除操作
  2. 维护红黑树性质：大致以下情况
    1. $u$ 或 $v$ 为红色节点
    2. $u$ 和 $v$ 均为黑色节点
      1. $u$ 是根节点
      2. $u$ 非根节点
        1. $u$ 的兄弟 $s$ 是黑色且 $s$ 的子节点至少有一个是红色
          • LL/RR vs. LR/RL
        2. $u$ 的兄弟 $s$ 是黑色且他的两个孩子都是黑色
        3. $u$ 的兄弟 $s$ 是红色

接下来分情况开始讨论：

  • i. 若 $u$ 或 $v$ 为红色，将 $u$ 改为黑色 （注意，由于最后的删除过程肯定存在 $v$ 是 $u$ 的父节点，因此两者不会同为红色）

  • ii. 若 $u$ 和 $v$ 都是黑色结点，直接删除 $v$ 并用 $u$ 替代，此时红黑树的性质 5 被破坏，为了进行维护，我们使 $u$ 成为双黑节点，接下来的任务是将这个双黑节点变回普通节点

  • ii. a. 若双黑节点 $u$ 是根节点，其可直接变为普通黑节点，$bh(T)$ 减一.
  • ii. b. 若双黑节点 $u$ 不是根节点，可分为三种情况，记 $u$ 的兄弟节点为 $s$, 他们的父节点为 $p$.
  • ii. b. a. 若 $s$ 是黑色节点，且 $s$ 至少有一个红色子节点，记作 $r$
    • LL / RR - $r$ 是 $s$ 左子，$s$ 是 $p$ 左子 :
      1. $s$ 左子改为 $s$ 颜色，$s$ 改为 $p$ 的颜色.
      2. 右旋节点 $p$ 并将其改为黑色.
      3. $u$ 改回普通黑节点.
    • LR / RL - $r$ 是 $s$ 右子，$s$ 是 $p$ 左子 :
      1. $r$ 改为 $p$ 的颜色.
      2. 左旋 $s$.
      3. 右旋 $p$ 并改为黑色.
      4. $u$ 改回普通黑节点.
  • ii. b. b. 若 $s$ 为黑色节点，且 $s$ 没有红色子节点
    • $u$ 的父节点 $p$ 为黑
      1. $p$ 变为双黑节点.
      2. $u$ 变回单黑节点.
      3. $s$ 改为红色.
      4. 继续处理 $p$.
    • $u$ 的父节点 $p$ 为红
      1. $s$ 变红节点.
      2. $u$ 改回单黑节点
      3. $p$ 变黑节点.
  • ii. b. c. 若 $s$ 是红色节点
    1. 右旋 $p$, $p$ 改红色，$s$ 改黑色.
    2. 此时与 ii. b. b. 情况相同.

(逆天了)

► 拓展

2-3 树：类似于 2-3-4 树，是一种自平衡的三叉搜索树，同样的，他也可以转化为一种特殊的二叉树：左斜红黑树.

与普通红黑树不同的是，左斜红黑树不具有红黑节点，而是分为红黑链，此处不展开讨论.
llrbt

红黑树的应用：

  1. 广泛用于C ++的STL中，map 和 set 是用红黑树实现的;
  2. Linux的的进程调度，用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个结点，左指针指向相邻的虚拟内存空间，右指针指向相邻的高地址虚拟内存空间;
  3. IO多路复用的epoll采用红黑树组织管理sockfd，以支持快速的增删改查;
  4. Nginx中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器;
  5. Java的 TreeMap 和 TreeSet 的实现;

（参考自知乎)

Lec 3 : Inverted File Index

检索

信息检索是从大量非结构化集合中查找满足信息需求的材料的过程.

  • 集合：文档的集合

逆索引（Inverted file index）是一种常见的文本检索技术，他通过将单词或短语作为关键词并将其在文档中的位置记录在一个索引中实现快速的文本检索.

【$\mathbf{Def}$】索引 在上下文中定位某段给定文本. 即建立 文本位置 $\rightarrow$ 文本内容的单射.
【$\mathbf{Def}$】逆索引 对于每一个单词，记录他出现在哪些文档的哪些位置中，并记录它们出现的频次.

基本实现

例如，有以下文档集合：
nva
我们可以建立这种索引：
b

优化

如果将所有词都存入逆索引，那么工作量非常大，且会有很大的冗余. 因此我们可以通过一系列方法来对其进行改进

► 停用词

有些词语会频繁的出现在所有文档中，但他们往往不会被用于索引. 例如单词 a、 the、 I 等，因此可以在建立逆索引时跳过这些词语, 这一类词就被称作停用词.

停用词的共同点是他们通常有着较高的出现频次，但并不能盲目的设计停用词.

► 词干分析

词干分析 是一种将单词转化为词干的技术，例如，可以将 eats, ate, eaten, eating 等词转化为 eat. 这些词由于他们的词干相同，因此往往在上下文中含义类似，我们在检索 eat 时，当然也希望找到 ate . 这一技术可以让多个单词共享同一个逆索引记录，从而对建立索引和搜索进行优化.

分布式

Lec 4 : Leftist Heap and skew Heap

Leftist Heap

左偏树是一种类似堆的二叉树，它的根节点总是树中的最小值。左偏树的每次取出/加入操作的时间复杂度为 $O(\log n)$ 与小根堆相同。与堆不同的是，合并两个数量为 $n$ 的堆的时间复杂度为 $O(n\log n)$ ,而左偏树则更快：$O(\log n)$ .

普通的最小堆需要维持其两特征：

  • 结构特征: 完全二叉树
  • 顺序特征: 每个子树的根节点小于其所有的子节点

左偏树的顺序属性与最小堆一致，但其结构属性有所变化.

► 结构属性

【$\mathbf{Def}$】空路径长度 $Npl(X)$ 定义为节点 $X$ 到某个具有一个或零个子节点的节点的最短路径长度. $Npl(NULL) = -1.$

【$\mathbf{Def}$】对左偏树的任意节点，其左子树的空路径长度大于等于其右子树的.

左偏树的这种特性导致其左侧逐渐变深.

【$\mathbf{Theorem}$】在右侧路径上有 $r$ 个节点的左偏树至少有 $2^r-1$ 个节点.

► 左偏树的合并(递归)

时间复杂度为 $O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Heap Merge(Heap H1, Heap H2)
{
    if(H1 == NULL) return H2;
    if(H2 == NULL) return H1;
    if(H1->Element < H2->Element) swap(H1, H2);
    if(H1->Left == NULL)
    {
        H1->Left = H2;
    }
    else
    {
        H1->Right = Merge(H1->Right, H2);
        if(H1->Left->Npl < H1->Right->Npl)
            swap(H1->Left, H1->Right);
        H1->Npl = H1->Right->Npl + 1;
    }
    return H1;
}

Skew Heap

Lec 5 :

🖊️ 计算机学院 高级数据结构 （Advanced Data Structure）
2024/02/26/ads/
作者
404
發布于
2024-02-26 18:57
許可
 留言
評論插件加載失敗
正在加載評論插件
  1. Basic info
  2. Lec 1 : Balanced BST
    1. Height Balance
    2. AVL Trees
      1. ► 单旋操作
      2. ► 双旋操作
    3. Splay Trees
      1. ► Zig或Zag
      2. ► Zig-Zig或Zag-Zag
      3. ► Zig-Zag或Zag-Zig
    4. Amortized Analysis
      1. ► 聚合分析
      2. ► 核算法
      3. ► 势法
  3. Lec 2 : Red-black Tree and B Tree
    1. M-Ary Search Trees
    2. B Tree
      1. ► 搜索
      2. ► 插入
      3. ► 删除
    3. B+ Trees
      1. ► 2-3-4树
    4. Red-black Tree
      1. ► 基本属性
      2. ► 插入
      3. ► 删除
      4. ► 拓展
  4. Lec 3 : Inverted File Index
    1. 检索
    2. 基本实现
    3. 优化
      1. ► 停用词
      2. ► 词干分析
    4. 分布式
  5. Lec 4 : Leftist Heap and skew Heap
    1. Leftist Heap
      1. ► 结构属性
      2. ► 左偏树的合并(递归)
    2. Skew Heap
  6. Lec 5 :
© 2023 - 2024    404
Hexo 框架 & 主題 Keep
本站由 提供部署服務
  1. Basic info
  2. Lec 1 : Balanced BST
    1. Height Balance
    2. AVL Trees
      1. ► 单旋操作
      2. ► 双旋操作
    3. Splay Trees
      1. ► Zig或Zag
      2. ► Zig-Zig或Zag-Zag
      3. ► Zig-Zag或Zag-Zig
    4. Amortized Analysis
      1. ► 聚合分析
      2. ► 核算法
      3. ► 势法
  3. Lec 2 : Red-black Tree and B Tree
    1. M-Ary Search Trees
    2. B Tree
      1. ► 搜索
      2. ► 插入
      3. ► 删除
    3. B+ Trees
      1. ► 2-3-4树
    4. Red-black Tree
      1. ► 基本属性
      2. ► 插入
      3. ► 删除
      4. ► 拓展
  4. Lec 3 : Inverted File Index
    1. 检索
    2. 基本实现
    3. 优化
      1. ► 停用词
      2. ► 词干分析
    4. 分布式
  5. Lec 4 : Leftist Heap and skew Heap
    1. Leftist Heap
      1. ► 结构属性
      2. ► 左偏树的合并(递归)
    2. Skew Heap
  6. Lec 5 :