高级数据结构与算法分析

红黑树

定义与性质

一棵合法的 红黑树 是遵循以下五条性质的二叉搜索树：
（1）节点要么为红色要么为黑色
（2）NIL 节点为黑色节点
（3）红色节点的子节点必然为黑色节点
（4）从根节点到所有 NIL 节点的简单路径上的 黑色节点 数量 相同
（5）根节点为黑色节点

一棵包含 $n$ 个 内部节点 的红黑树的 最大高度 为 $2\ln{(n+1)}$

插入操作

B+树

定义与性质

一棵阶为 $m$ 的 B+树 具有以下性质：
（1）根节点 要么是一个叶子节点，要么有 $2$ 至 $m$ 个子节点
（2）所有的 非叶子节点（除了根节点）都有 $\lceil\frac{m}{2}\rceil$ 至 $m$ 个子节点
（3）所有的 叶子节点 具有 相同的高度
假设所有的 非根节点 都有 $\lceil\frac{m}{2}\rceil$ 至 $m$ 个儿子

所有的数据都保存在 叶子节点 中
每一个 内部节点 包含 $m$ 个指针指向子节点

左倾堆

定义与性质

空路径长度 null path length $Npl(X)$
从节点 $X$ 任意没有两个孩子的子节点的 最短距离，特别地 $Npl(\mathrm{NULL})=-1$
对于 叶子节点 或只有 一个 孩子的子节点，有 $Npl(X)=0$

$$Npl(X)=1+\min\{Npl(C)\space|\space C \space\mathrm{is\space a\space child\space of\space}X\}$$

左倾堆 leftist heap
对于左倾堆的每个节点，左节点的 $Npl$ 值 大于等于 右节点的 $Npl$ 值

性质1 一个$Npl(\mathrm{root})=r$ 的左倾堆 至少 有 $2^r-1$ 个节点
性质2 一个包含 $N$ 个节点的左倾堆的 $Npl(\mathrm{root})$ 最大为 $\lfloor\log(N+1)\rfloor$

合并操作

递归合并，每次选取根节点 值较小 的作为合并后的根节点，并将其右子树继续进行合并操作，如果递归结束后右子树的 $Npl$ 更大就对左右子树进行 交换

由于每次操作都是沿着向右的方向进行，根据性质可知递归的复杂度为 $\log N$

插入操作

看作一个单节点的子树与原树合并

删除操作

看作删除根节点后两个子树的合并

斜堆

定义与性质

斜堆 skew heap 也称为 自适应堆 self-adjusting heap 是另一种可并堆，不需要记录任意一个节点的距离，只是在合并操作上有所改变

合并操作

递归 版本：
（1）比较两个堆，记 $p$ 是 $\mathrm{root}$ 键值更小的堆，$q$ 是另一个堆，$r$ 是合并后的堆
（2）根据堆的性质，选择 $p$ 的根节点作为 $r$ 的根节点
（3）令 $r$ 的右子树为 $p$ 的左子树
（4）令$r$ 的左子树为 $p$ 的右子树与 $q$ 合并的结果
迭代 版本：
（1）把每个堆的每棵右子树切下来，使得得到的每棵树的右子树均为空
（2）按照 $\mathrm{root}$ 的键值升序排序这些树
（3）迭代合并具有最大 $\mathrm{root}$ 键值的两棵树

复杂度分析

重节点 heavy node 称一个节点是重的当且仅当它的右子树节点数大于等于左子树
定义势能函数

$$\Phi(D_i)=\text{the number of heavy nodes}$$

考虑第 $i$ 次合并过程，它们 右路径 上的轻重节点个数分别为 $l_p,h_p,l_q,h_q$ ，合并代价为

$$c_i=l_p+l_q+h_p+h_q$$

一次操作后重节点一定变为轻节点，而轻节点不一定变成重节点，因为：
对于 重节点，原先较大的右子树会与另一棵树合并成为左子树，变得更大
对于 轻节点，左子树和另一棵树合并可能比原来的右子树大，不确定

$$\Phi(D_{i+1})-\Phi(D_i)\leq l_p+l_q-h_p-h_q=O(\log N)$$

而右路径上的轻节点个数是 $O(\log\space N)$ 级别的，所以总复杂度为 $O(n\log n)$

二项堆

定义与性质

二项堆 binomial queue 是二项树的构成的森林
二项树 binomial tree 是递归构造的，$B_k$ 由 $B_{k-1}$ 连接至另一个 $B_{k-1}$ 的根节点构成

性质1 对于二项树 $B_k$ 高度为 $d$ 的节点数量为 $C_k^d$
性质2 对于二项树 $B_k$ 节点总数为 $2^k$
性质3 可以对大小为 $n$ 的二项堆二进制拆分、合并

查询操作

对于森林中的每一个树的根节点求最小值，复杂度为 $O(\log n)$

合并操作

类比二进制中的竖式加法确定将哪些二项树合并

删除操作

查询根节点键值最小的二项树删除根节点，然后将产生的森林视为新的二项堆并合并

构造方式

可以使用链表的存储形式，即 左儿子右兄弟 的方式连接