树与堆 Tree and Heap¶

该部分的内容可以看作围绕二叉搜索树及其优化展开。

对于每种具体的树，关注它的：成员、操作、结构。

成员：为了保持平衡条件，节点可能需要额外保存信息，比如深度、颜色等。
操作：树形结构的操作是相似的，最重要的三个是查找、插入、删除。为了实现这些操作，具体的结构会有一些辅助操作。很多操作是递归的，想清楚终止情况和递归条件。
结构：加上平衡条件后，这些树展现出不同的结构，也对它们的操作复杂度产生影响。

复杂度总结

堆：

操作	二叉堆	左式堆	斜堆	二项队列	斐波那契堆
`Insert`	\(O(\log N)\)	\(O(\log N)\)	\(O(\log N)\)	\(O(1)\)	\(O(1)\)
`Merge`	\(O(N)\)	\(O(\log N)\)	\(O(\log N)\)	\(O(\log N)\)	\(O(1)\)
`DeleteMin`	\(O(\log N)\)	\(O(\log N)\)	\(O(\log N)\)	\(O(\log N)\)	\(O(\log N)\)
`Delete`	\(O(\log N)\)	\(O(\log N)\)		\(O(\log N)\)	\(O(\log N)\)
`DecreaseKey`	\(O(\log N)\)	\(O(\log N)\)		\(O(\log N)\)	\(O(1)\)

树：

二叉搜索树 Binary Search Tree¶

成员操作结构

Key
Left
Right

Find
FindMin
FindMax
Insert
Delete
- Leaf
- One
- Two

难点：删除操作（具有两个子节点的情况）

可以直接编写代码完成删除操作。《算法导论》设置了一个 transplant 操作，用一个子树替换掉另一个子树。我们看看怎么用这个操作完成两个子节点情况的删除。

找到接替节点（右侧最小或左侧最大）
如果接替节点不是被删除节点的直接孩子：
- 提出该节点：调用 transplant 让它的孩子取代它
调用 transplant 替换掉被删除的整个子树
修改指针，把被删除节点的孩子接回接替节点上

平均深度为 \(O(\log N)\)。这里的平均指的是对所有可能的插入序列而言。
删除算法偏好某一侧节点，容易使另一侧树相比之下更深。

AVL 树 AVL Tree¶

成员操作结构

Key, Left, Right
Height

高度信息的存储

Height 成员能够容纳的最大数决定了树的最大高度。因为树是平衡的，即使 8 位 255 的绝对高度，也足以应付普遍的情况。

Find, FindMin，FindMax
Insert
Delete
- 一般采用懒惰删除，课内未介绍删除方法。

辅助操作：

SingleRotateWithLeft，SingleRotateWithRight
DoubleRotateWithLeft，DoubleRotateWithRight

难点：旋转操作

按课本上的函数命名，with 哪一侧就是把哪一侧的节点旋转到该节点位置。旋转操作本质上负责过继孩子，并将新的根节点返回，供上层设置为新的孩子。

单旋转无法解决内侧树过深的问题。可以想象，对该节点执行旋转后，内侧树的高度并没有减少。双旋转操作先进入内侧树，将深度旋转到外侧，再回到上层进行单旋转，从而解决内侧树过深的问题。

不要忘记在旋转操作中维护节点高度信息。

难点：插入操作

AVL 树的插入于二叉搜索树的插入一样，都是递归的。只是在插入后，需要检测子树的高度差，维护平衡条件。维护在递归返回时第一个检测到不满足平衡条件的节点进行，使插入后不平衡的子树高度减少 1，路径上所有节点的平衡也恢复了。

除了高度差，还需要确定新节点插入的位置是“外侧”还是“内侧”（与子树的根节点比较），以决定执行单或双旋转。

旋转操作更改了节点的位置，需要维护节点的高度。插入操作也参与高度的维护，将高度的变化递归向上传递。

下面是一个分支情况的代码：

if(X < T->Key)
    T->Left = Insert(X, T->Left);
    if(Height(T->left) - Height(T->Right) == 2)
        if(X < T->Left->Key)
            T = SingleRotateWithLeft(T);
        else 
            T = DoubleRotateWithLeft(T)
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;

定义：空树高度为 -1
平衡条件：左、右子树高度最多差 1

节点数与高度的关系

设高度为 \(h\) 的 AVL 树节点最少为 \(S(h)\) 个，有 \(S(h) = S(h-1) + S(h-2) + 1\)。AVL 树与斐波那契数相关。

对上面高度与节点数的关系求解，容易得到 AVL 树的最大高度为 \(1.44\log(N+2) - 1.328\)，一般情况下只比 \(\log N\) 高一些。

伸展树 Splay Tree¶

成员操作结构

Key，Left，Right
Parent

伸展树需要保存父节点信息以进行伸展操作。

Find, Insert，Delete

对节点的访问（上面的三个操作）会将元素移动到根节点。

辅助方法：

Splay：通过旋转将节点移动到根
SingleRotateWithLeft，SingleRotateWithRight
DoubleRotateWithLeft，DoubleRotateWithRight

难点：伸展

伸展有三种情况，记该节点、父节点和祖父节点为 \(X\)、\(P\)、\(G\)：

没有祖父节点：旋转 \(P\) 使 \(X\) 为根
三角情况（Zig-Zag）：双旋转，也就是先后旋转 \(P\)、\(G\) 使 \(X\) 为根
线形情况（Zig-Zig）：先后旋转 \(G\)、\(P\) 使 \(X\) 为根

注意线形情况旋转的顺序。对于线形的情况，如果逐层向上旋转，路径上的节点又按原来的顺序连接起来，相对位置不变，没有改善这些节点的高度情况。

最近搜索、插入、删除的元素都会被 Splay 到根节点

伸展树各个操作的摊还复杂度是 \(O(\log N)\)。

难点：伸展树的摊还分析

使用势函数法。==todo==

红黑树 Red-Black Tree¶

成员结构操作

Key, Left, Right
Parent
Color

颜色

有的书籍将线染色，这是等价的，只需要把线的颜色存储在下方的节点。

性质：

节点颜色红或黑
根节点黑
空节点是黑的
红节点的两个子节点都是黑的
节点到所有后代空节点（不计自身）的路径上，包含相同数目黑色节点

最后两条性质决定红黑树的高度。

难点：证明红黑树的高度

以 \(x\) 为根的子树中至少含有 \(2^{bh(x)}-1\) 个节点
- 数学归纳法：子节点黑高为 \(bh(x)\) 或 \(bh(x)-1\)，最少情况 \(2*(2^{bh(x)-1}) + 1 = 2^{bh(x)} - 1\)
- 直观理解：把红色节点去掉，剩余节点个数一定大于等于高度为 \(bh(x)\) 的完全平衡二叉树节点个数，因为可能会变成孩子更多的树。因此至少有 \(2^{bh(x)}-1\) 个节点
\(bh(root) \geq h/2\)：因为路径上至少有一半节点为黑色

上面两条性质结合得到：含有 \(n\) 个节点的红黑树高度最多为 \(2\log(n+1)\)。

搜索操作复杂度为 \(O(\log n)\)
插入操作复杂度为 \(O(\log n)\)
- \(O(\log n)\) 搜索，最多两次旋转，\(O(\log n)\) 次染色

Find, Insert, Delete

辅助方法：

InsertFix
Transplant
DeleteFix

难点：插入修复

找到插入的位置，插入红色的新节点（记为 \(Z\)），然后调用 InsertFix。

插入节点后可能被破坏的性质是：

根节点变红：这是是因为 \(Z\) 移动到了根
红节点的孩子还是红节点：这是因为 \(P\) 也是红节点

InsertFix 循环条件是 \(P\) 为红色。每次循环保持：最多只有一条红黑树性质被破坏。可以推出，循环结束时，被破坏的性质只可能是根节点变红，对此进行修复即可。

循环内部可能会调整节点的位置以修复 \(P\) 是红节点的问题，此时需要维护黑高性质。关注下面的操作中黑色是怎么在节点之间“分解”、“转移”的。

因为 \(P\) 红，\(G\) 必定黑。根据 \(Z\) 的叔节点（记为 \(U\)）的颜色，与 \(P\)、\(G\) 相对位置分三种情况（对称后有六种）：

没有叔节点：\(U\) 是黑色的
红色：
- 目标：将 \(G\) 的黑高转移到 \(U\) 和 \(P\) 上
- 操作：\(G\) 染成红色，\(U\) 和 \(P\) 染成黑色；让 \(Z\) 指向 \(G\)，进入下一轮循环。因为此时 \(Z\) 可能破坏红黑树性质。
黑色：
- 线形：把 \(G\) 的黑色转移给 \(P\)，然后让 \(P\) 旋转到 \(G\) 的位置。这解决的是红色父子的问题。
- 三角形：对 \(P\) 旋转把 \(Z\) 整到外面，然后按线形的方法操作，即把 \(G\) 的黑色转移给 \(Z\)，然后让 \(Z\) 旋转到 \(G\) 的位置

双旋转的进一步认识

如果不把 \(Z\) 整到外面，直接转移颜色对 \(G\) 旋转，则红色问题又转移到 \(G\) 上，没有解决。这和 AVL 树单旋转时遇到的问题一样，在 AVL 树中单旋转无法解决内侧树过深的问题。这些情况加深了我们对旋转操作的认识：单旋转改变外侧树高度，双旋转采用两次单旋转改变内侧树高度。

难点：删除修复

删除操作基于二叉树删除操作，回顾这三种情况的处理方式。红黑树中删除时，接替节点的值替换被删除节点，颜色不变。被删除或移动到树中的节点为 \(y\)，记录它的原始颜色。如果原始颜色为黑色，则接替 \(y\) 的节点 \(x\) 可能引起红黑树性质的破坏：

现在，给 \(x\) 赋予一层额外的黑色
循环条件 \(x\) 是黑色且不是根节点（因为直到 \(x\) 为红色节点，才能把额外的黑色化解）
- 如果 \(x\) 的兄弟是红色，此时父亲一定是黑色
  - 该情况下无法将整层的黑色向上传递，只好旋转变化为下面的情况
  - 旋转，让兄弟变黑，父亲变红，进入下面的情况
- 如果 \(x\) 的兄弟是黑色
  - 兄弟的两个孩子都是黑色（如果有红孩子，就不能执行该步的操作，会违反红节点性质）
    - 让兄弟变红，\(x\) 设为父亲（相当于把该层黑色向上传递）
  - 兄弟的近孩子是红色，远孩子是黑色
    - 旋转，将红色的孩子弄出去，进入下面的情况
  - 兄弟的远孩子是红色
    - 旋转父亲，让兄弟接替父亲，变成父亲的颜色。父亲下来变黑（自己的双黑传递上去），兄弟的远孩子变黑（兄弟的黑色导致的），达到平衡
离开循环，将 \(x\) 染黑

删除操作复杂度为 \(O(\log n)\)

完美平衡的 2-3 查找树¶

该部分来源于《算法》。完美平衡的 2-3 查找树与红黑树一一对应，理解这一对应关系有助于理解红黑树的结构：红黑树为什么能够通过黑高实现所谓的“平衡”？当你看到将红链接画平的红黑树时，相信你会有新的理解。这也将帮助我们过渡到 B 树。

==todo==

B 族树¶

B 族树有很多种具体的实现方式，不同书里的讲解方式也可能会有一些差异（主要是在 Order 等参数的定义上，本质不会变）。

B 树一般用于 DBMS 等大量数据的存储，性能指标一般是对磁盘的访问量，即访问节点的数量。

值得注意的是，B 族树都是从根节点向上增长的，因此 Insert() 操作常常是对根节点特殊处理的包装，对内部节点的插入使用 InsertNotFull() 等函数。

《算法导论》中的 B 树¶

成员操作结构

n：节点关键字数量
leaf
key[n]
child[n+1]

所有操作都是单程下行的，无需返回。

Search(root, key)：返回节点指针和下标
SplitChild(root, i)：\(2t-1=2(t-1)+1\)
- root 是非满的节点
- i 标记非满的子节点
Insert(root, key)
- 包装 InsertNotFull()，处理根节点满情况（向上增长）
InsertNotFull(root, key)
- 叶节点直接插入
- 非叶节点，递归向下前先考虑 SplitChild

关键字数量的限制：定义最小度数 \(t\geq2\)
- 根节点以外的节点，关键字可以有 \(t-1\sim2t-1\) 个
- 根节点至少 \(1\) 个关键字。
高度的限制：所有叶节点高度相同。根节点深度为 \(0\)。

高度：\(h\leq \log_t \frac{n+1}2\)。画图容易知道，深度 \(h\) 至少有 \(2t^{h-1}\) 个节点，求和得到结论。

《算法》中的 B 树¶

事实上《算法》中的 B 树很像课内介绍的 B+ 树。

成员操作结构

Page:

external：布尔值，是否为外部页
pair：键和链接

《算法》中的 B 树 API 是基于符号表封装的，每个节点中包含一个 Page 对象。这样封装有一定优点：操作 Page 时只需要管符号表操作不需要考虑树的链接，操作 BTreeSET 时只需要考虑抽象的节点操作不需要考虑符号表的变动。

Page 负责实际的数据操作（当然也需要对内、外部页作分别处理，但这很简单）：

split：分裂
next：可能含有键的子树
contains：查找
add：添加键

而 BTreeSET 更像是 Page 的管理器，封装后对外只剩下两个操作：

add
contains

有了 Page 的抽象，这些操作的实现非常简答。比如非根节点的 add 只有几行：

if(h.isExternal()) { h.add(key); return;}
Page next = h.next(key);
add(next, key);
if(next.isFull())
    h.add(next.split);

参数 \(M\) 阶：

其他节点：\(M/2\sim M-1\) 对键和链接
根节点：\(2\sim M-1\) 对键和链接

B 树的性能分析很容易，因为内部节点一定是由含有 \(M\) 个键的饱和节点分裂而来，可知总链接数为 \(M/2\sim M-1\)，形成度为 \(M/2 \sim M-1\) 的完全树，故查找或插入成本均为 \(\log_M N\sim \log_{M/2} N\) 次磁盘操作。

B+ 树¶

成员结构操作

n
leaf
key[n]
child[n+1]
next：需要遍历的实现会出现，指向下一个叶子节点

使用哨兵和重复的键值

如果允许自由实现，可以使用哨兵，并允许键值在内部节点重复出现。这样可以将 key 和 child 合并为 map<key, child>，简化操作。

B+ 树中，所有数据都在叶子节点上，非叶子节点只存储索引。这样的设计使得 B+ 树既方便索引又方便遍历。

定义 \(M\) 为 B+ 树的 order。

根节点：\(2\sim M\) 个孩子，即 \(1\sim M-1\) 个 Key
非叶子节点：\(\lceil M/2 \rceil \sim M\) 个孩子，即 \(\lceil M/2 \rceil - 1 \sim M-1\) 个 Key
（非根）叶子节点：\(\lceil M/2 \rceil \sim M\) 个孩子，也是 Key

设一个内部节点有 \(N\) 个孩子，那么它有 \(N-1\) 个 Key，是除第一个子树外的其他子树的最小值。注意这里是子树而不是孩子。

Find
Insert
SplitLeaf
SplitInternal

删除不做要求。

难点：分裂操作

B+ 树叶子是数据，内部节点是索引。对于课内教授的 B+ 树，键值不允许在内部节点多次出现，因此内外节点需要分别处理：

分裂叶子节点时，作为索引的值复制到父节点中
分裂内部节点时，作为索引的值上移到父节点中

二叉堆 Binary Heap¶

二叉堆是完全二叉树。它有两个性质：

结构性质：完全二叉树
堆序性质：任意节点的关键字不大于（或不小于）其孩子节点的关键字

==todo==

左式树/堆 Leftist Tree/Heap¶

Youtube 讲解视频

回顾：二叉堆合并

合并二叉堆：

拷贝所有元素
构建堆：插入或线性时间建堆（Heapify）

复杂度为 \(O(N\log N)\) 或 \(O(N)\)。

成员操作

Key, Left, Right
NPL：Null Path Length，零路径长

概念：S 值/零路径长（Null Path Length）

和红黑树中一样，我们把空指针视为外部节点。

S 值：从一个节点到外部节点的最短路径长度。

\(S(null) = 0\)
\(S(x) = 1 + \min(S(x.left), S(x.right))\)

Merge
Insert, Delete：这两个操作都基于合并。插入就是和单节点合并，删除只发生在根部，删除根节点就是合并左右孩子。

左式堆：合并

前向步骤：比较两个根节点，取出较小根节点的右孩子和另一个堆合并，直到有一个待合并的堆为空。
反向步骤：用合并结果替换掉较小根节点的右孩子。如果会违背左式树的性质，交换左右孩子。

复杂度分析：每次合并操作都是 \(O(1)\)，持续向右进行。向右最长路径为 S 值，因此合并操作的复杂度为 \(O(\log N)\)。

结构

左式树/堆的性质

\(S(x.left) \geq S(x.right)\)

结合 \(S(x) = 1 + \min(S(x.left), S(x.right))\) 可以马上知道，S 值是通向最右侧外部节点的路径长度。

从该性质，利用数学归纳法，可以得到：

以 \(x\) 为根的子树至少有 \(2^{S(x)}-1\) 个节点
以 \(x\) 为根的子树 \(S(x) \leq \log(N+1)\)

满足堆序性质的左式树就是左式堆。显然：左式堆不需要是完全二叉树。

斜堆 Skew Heap¶

Skew Heap 是左式堆的一种变种，它不维护左式堆的性质，总是在合并操作中交换左右孩子。因此它不考虑零路径长。

不交换的情况是：右路径上最大的节点的孩子没有交换过。

Always swap the left and right children except that the largest of all the nodes on the right paths does not have its children swapped.

二项队列 Binomial Queue¶

二项队列是二项树组成的森林，每个树是堆有序的。

与上面的堆相比，二项堆能够实现摊还常数时间的插入建堆操作。

成员结构操作

BinNode
- Key
- Left
- Right
BinQueue
- Size：节点总数
- Trees：指向树根的指针数组

高度：

单节点树 \(B_0\) 高度为 \(0\)。
高度 \(k\) 的树 \(B_k\) 由两个高度 \(k-1\) 的树 \(B_{k-1}\) 合并而来，合并的方式是把一个树连到另一个树的根部。
- 每次高度增加都会往根部连一个相同的树的根，因此高度为 \(k\) 的树根 \(B_k\) 有 \(k\) 个孩子，这些孩子分别是 \(B_0, B_1, \cdots, B_{k-1}\)。
- 递归很容易得到高度为 \(k\) 的树 \(B_k\) 有 \(2^k\) 个节点。
- 第 \(d\) 层的节点数为 \(\binom{k}{d}\)，这同样可以根据归纳法和组合数的性质 \(C_k^i + C_k^{i-1} = C_{k+1}^i\) 得到。

辅助：
- CombineTrees：合并两棵树
FindMin：
- 最小的节点一定在根部。
- 森林中最多有 \(\lceil \log N \rceil\) 棵树。
- 复杂度为 \(O(\log N)\)。
Merge：
- 类似数字逻辑电路中的进位加法器。
- 合并高度相同的两棵树时，必须保证堆序性质，即将较大树的根作为较小树的孩子。
- 根据所合并两个队列当前高度上的树和进位的树，分 \(2^3=8\) 种情况讨论。

合并操作伪代码

BinQueue  Merge( BinQueue H1, BinQueue H2 )
{
    BinTree T1, T2, Carry = NULL;  
    int i, j;
    if ( H1->CurrentSize + H2-> CurrentSize > Capacity )  ErrorMessage();
    H1->CurrentSize += H2-> CurrentSize;
    for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
        T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
        switch( 4*!!Carry + 2*!!T2 + !!T1 ) { 
        case 0: /* 000 */
        case 1: /* 001 */  break; 
        case 2: /* 010 */  H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
        case 4: /* 100 */  H1->TheTrees[i] = Carry; Carry = NULL; break;
        case 3: /* 011 */  Carry = CombineTrees( T1, T2 );
                        H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
        case 5: /* 101 */  Carry = CombineTrees( T1, Carry );
                        H1->TheTrees[i] = NULL; break;
        case 6: /* 110 */  Carry = CombineTrees( T2, Carry );
                        H2->TheTrees[i] = NULL; break;
        case 7: /* 111 */  H1->TheTrees[i] = Carry; 
                        Carry = CombineTrees( T1, T2 ); 
                        H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}

Insert：
- 合并一个只有一个节点的树和原队列。
DeleteMin：
- 找到最小根所在的树，移出森林。
- 删除它，它的孩子们组成一个新的森林。
- 合并这个森林和原森林。

将任意大小的优先队列表示为二项队列

把队列大小表示为二进制，为 \(1\) 的位对应一个二项树。这样的表示方法是唯一的。

斐波那契堆 Fibonacci Heap¶

树的遍历¶

层序遍历¶

不论是一般表示的树，还是左孩子右兄弟表示的树，甚至是森林，层序遍历都可以使用队列解决。以一般表示的树为例：

从根开始，将根节点入队
进入循环，循环条件为队列非空
队首元素出队，打印，并将孩子入队

下面是一段二叉树层序遍历的示例代码：

#include <queue>

class BinaryTree{
    int key;
    BinaryTree *left, *right;
public:
    friend std::ostream &operator<<(std::ostream &os, BinaryTree &tree);
};

std::ostream &operator<<(std::ostream &os, BinaryTree &tree){
    std::queue<BinaryTree *> q;
    q.push(&tree);
    while(!q.empty()){
        BinaryTree *node = q.front();
        q.pop();
        os << node->key << " ";
        if(node->left)
            q.push(node->left);
        if(node->right)
            q.push(node->right);
    }
    return os;
}

扩展：换行层序遍历

如果要求按行输出树的每一层，需要怎么做呢？

左孩子右兄弟表示法¶

其他¶

ART 树：这是我在《高级数据结构与算法》课程作业中实践的数据结构，来自高效全文本搜索引擎 TypeSense。具体内容请查阅论文。
- 与各类二叉搜索树相比，它能极大地节省空间
- 它针对体系结构做了优化，精巧设计节点，在主存上表现很好
- 访问速度趋近哈希表，同时还支持模糊搜索和范围查找