数据结构 | EinNiemand's Blog

绪论

算法

计算 = 信息处理 = 借助某种工具，遵照一定规则，以明确而机械的形式进行
计算模型 = 计算机 = 信息处理工具

算法，是指基于特定的计算模型，旨在解决某一信息处理问题的指令序列。

有穷性：任意算法都应在执行有限次基本操作之后终止并给出输出
正确性：所给的输出应能符合由问题本身在事先确定的条件
健壮性：能处理各种极端的输入实例
可计算性
效率

起泡排序

void bubblesort1A(int A[], int n) { // 0 <= n
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (int i = 1; i < n; i++) {
            if (A[i - 1] > A[i]) {
                swap(A[i - 1], A[i]);
                sorted = false;
            }
        }
        n--; // 至此末位元素必然就位
    }
}

复杂度度量

问题实例的规模，往往是决定计算成本的最主要因素。通常，规模接近，计算成本也接近；规模扩大，计算成本亦上升。

$T_A(n)$ $T_{A} (n)$ = 算法 A 求解某一规模为 $n$ $n$ 的实例所需的计算成本，简化为 $T(n)$ $T (n)$
- 取 $T(n) = \max\{T(P) | \left\vert P \right\vert = n\}$

计算模型

图灵机

部件
- Tape：依次均匀地划分为单元格，各存有某一字符，初始均为“#”
  - 字符的种类有限
- Head
  - 总是对准某一单元格，并可读取或改写其中的字符
  - 每经过一个节拍，可转向左侧或右侧的邻格
- State
  - TM 总是处于有限种状态中的某一种
  - 每经过一个节拍可按照规则转向另一种状态
  - $h = \text{halt}$
Transition Function： $(q,c;d,L/R,p)$
- 若当前状态为 $q$ $q$ ，且当前字符为 $c$ $c$ ，则
  - 将当前字符改写为 $d$
  - 转向左/右侧邻格
  - 转入 $p$ 状态
从启动至停机，所经历的节拍数目即可用以度量计算的成本

实例

将二进制非负整数加一

(<, 1; 0, L, <) // 左行, 1-> 0
(<, 0; 1, R, >) // 调头, 0-> 1
(<, #; 1, R, >) // 调头, #-> 1
(>, 0; 0, R, >) // 右行
(>, #; #, L, h/<) // 停止/进行下一轮运行

RAM

组成
- 寄存器顺序编号，总数没有限制
- 可通过编号直接访问任意寄存器（call-by-rank）
- 每一基本操作只需常数时间
在这些模型中
- 算法的运行时间 $\propto$ 算法需要执行的基本操作次数
- $T(n)$ = 算法为求解规模为 $n$ 的问题，所需执行的基本操作次数

渐近复杂度

问题规模足够大之后，计算成本的增长趋势

big-O notation

$T(n) = O(f(n)) \iff \exist c > 0 \quad \text{s.t.} \quad T(n) < c \cdot f(n) \quad \forall n \gg 2$

由 $O$ 记号提供的渐近上界不一定是紧确的。使用 $o$ 记号表示一个非渐近紧确的上界。

$T(n) = o(f(n)) \iff \forall c > 0 \quad \text{s.t.} \quad T(n) < c \cdot f(n) \quad \forall n \gg 2$
对于 $f(n) = o(g(n))$ ， $\begin{aligned}\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\end{aligned}$
渐近符号也可以用来刻画算法的某个其他方面（如使用的空间数量）

其他记号

$T(n) = \Omega(f(n)) \iff \exist c > 0 \quad \text{s.t.} \quad T(n) > c \cdot f(n) \quad \forall n \gg 2$
- $\omega$ 记号同 $o$ 理
$T(n) = \Theta(f(n)) \iff \exist c_1 > c_2 > 0 \quad\text{s.t.} \quad c_1 \cdot f(n) > T(n) > c_2 \cdot f(n) \quad \forall n \gg 2$

定义多重对数函数为 $\log^*(n) = \min{i\ge 0 : \log^{(i)}(n) \le 1 } $

由此可得 $\begin{aligned}\exist f(n), \lim_{n \to \infty} f(n) = \infty \quad \text{s.t.} \quad f(n) = \Theta(f(\log n))\end{aligned}$
for (i = 1; i < n; i = (1 << i))

复杂度分析

$O(1)$ $O (1)$ ：常数
- 通常不含循环、分支、子程序调用
- 仅需 $O(1)$ 辅助空间的算法，称为就地算法
- C++等高级语言的基本指令，均等效于常数条 RAM 的基本指令
$O(\log^c n)$ $O (lo g^{c} n)$ ：对数
- $\forall c > 0, \quad \log n = O(n^c)$
- $\ln (n!) \approx (n + 0.5) \ln n - n$
- $\begin{aligned}\sum_{i=1}^n \frac{1}{i} = \ln n + \gamma + \Theta(\frac{1}{2n}),\quad \gamma \approx 0.577216\end{aligned}$
$O(n^c)$ $O (n^{c})$ ：多项式
- $a_k \cdot n^k + a_{k-1} \cdot n^{k - 1} + \cdots + a_1 \cdot n + a_0 = O(n^k), \quad a_k > 0$
$O(2^n)$ $O (2^{n})$ ：指数
- $T(n) = O(a^n), \quad a > 1$
- 从 $O(n^c)$ 到 $O(2^n)$ ，是从有效算法到无效算法的分水岭
- Subset Sum $\rightarrow$ NP-complete

输入规模

待计算问题的输入规模，应严格定义为“用以描述输入所需的空间规模”。

封底估算

根据数据结构和算法的渐近复杂度，凭借在实际计算环境中积累的经验，针对计算过程主要部分进行的粗略估算。

迭代与递归

int sum(int A[], int n) { // 数组求和(线性递归版)
    if (n < 1) // 平凡情况, 递归基
        return 0;
    else
        return sum(A, n - 1) + A[n - 1];
} // O(1)*递归深度 = O(1)*(n+1) = O(n)

线性递归

每一层次至多有一个实例，且它们构成一个线性的次序关系。

减而治之

为求解一个大规模的问题，可以
- 将其划分为两个子问题：其一平凡，另一规模缩减
- 分别求解子问题；再由子问题的解，得到原问题的解
递归每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。
计算过程中出现过的所有递归实例，其所需时间总和，即为整体运行时间
空间复杂度：递归深度 + 额外申请空间

尾递归和递归消除

在线性递归算法中，若递归调用在递归实例中恰好以 最后一步操作 的形式出现，则称作尾递归
属于尾递归形式的算法，均可简捷地转换为等效的迭代版本

void reverse(int *A, int n) {
    if (n < 2) return;
    swap(A[0], A[n - 1]);
    reverse(A + 1, n - 2);
}
void reverse(int *A, int lo, int hi) {
	while (lo < hi)
        swap(A[lo++], A[hi--]);
} // O(hi - lo + 1), cache-friendly

分而治之

为求解一个大规模的问题，可以
- 将其划分为若干子问题（通常两个，且规模 大体相当）
- 分别求解子问题；再由子问题的解，得到原问题的解
为使分治策略真正有效，需要保证
- 子问题之间相互独立
- 子问题划分和子解答合并能高效实现

主定理

分治策略对应的递推式，通常形如 $T(n) = a \cdot T(n / b) + O(g(n))$
- 原问题被分为 $a$ 个规模均为 $n/b$ 的子任务
- 任务的划分、解的合并，总共耗时 $g(n)$
若 $g(n) = \Omega(n^{\log_b a + \epsilon})$ ，则 $T(n) = \Theta(g(n))$
- $\epsilon > 0$ 意味着存在多项式级别的差距
- quickSelect（average case）： $T(n) = 1 \cdot T(n / 2) + O(n) = O(n)$
若 $g(n) = O(n^{\log_b a - \epsilon})$ ，则 $T(n) = \Theta(n^{\log_b a})$
- large integer multiplicaton： $T(n) = 3 \cdot T(n / 2) + O(n) = O(n^{\log_2 3})$
若 $g(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ ，则 $T(n) = \begin{cases} \Theta(n^{\log_b a} \cdot \log^{k + 1} n), & k > -1 \\ \Theta(n^{\log_b a} \cdot \log\log n), & k = - 1 \\ \Theta(n^{\log_b a}), & k < -1 \end{cases}$
- STL mergesort： $T(n) = 2 \cdot T(n / 2) + O(n \cdot \log n) = O(n \cdot \log^2 n)$

Akra-Bazzi Theorem

分治策略对应的递推式，更一般地形如 $\begin{aligned}T(n) = \sum_{i = 1}^k a_i \cdot T(b_i \cdot n + h_i(n)) + O(g(n))\end{aligned}$ $T (n) = i = 1 \sum k a_{i} \cdot T (b_{i} \cdot n + h_{i} (n)) + O (g (n))$
- 其中 $0 < a_i, 0 < b_i < 1, \left\vert h_i(n) \right\vert = O(n / \log^2n)$
- $0 \le g(n)$ 且存在正常数 $d$ 使得 $\left\vert g'(n) \right\vert = O(n^d)$
- 只要取 $p$ 使得 $\begin{aligned}\sum_{i = 1}^k a_i \cdot b_i^p = 1\end{aligned}$ ，则 $T(n) = \Theta(n^p \cdot (1 + \int_1^n g(u) / u^{p + 1}\, {\rm d}u))$
- 如对于算法 LinearSelect ，有
  - $T(n) = 1 \cdot T(3/4 \cdot n) + 1 \cdot T(1/5 \cdot n) + O(n) = O(n)$

总和最大区段

分而治之

$\mathcal{A}[lo, hi) = \mathcal{A}[lo, mi) \cup \mathcal{A}[mi, hi) = \mathcal{P} \cup \mathcal{S}$
借助递归，求得 $\mathcal{P}、\mathcal{S}$ 内部的 GS，并考察跨越切分线的区段

int gs_DC(int A[], int lo, int hi) { // O(nlogn)
    if (hi - lo < 2) return A[lo];
    int mi = (lo + hi) / 2;
    
    int gsL = A[mi - 1], sL = 0, i = mi;
    while (lo < i--)
        if (gsL < (sL += A[i])) gsL = sL;
    int gsR = A[mi], sR = 0, j = mi - 1;
    while (++j < hi)
        if (gsR < (sR += A[j])) gsR = sR;
    return max(gsL + gsR, max(gs_DC(A, lo, mi), gs_DC(A, mi, hi)));
}

减而治之

最短的总和非正的后缀 $\sim$ 总和最大区段
若 $suffix(k) = \mathcal{A}[k, hi), \quad k = \max\{lo \le i < hi | sum[i, hi) \le 0\}$ $s u f f i x (k) = A [k, h i), k = max {l o \leq i < h i ∣ s u m [i, h i) \leq 0}$
- 则 $GS(lo, hi) = \mathcal{A}[i, j)$ 要么是其后缀，要么与之无交
- 可用反证法证明

int gs_LS(int A[], int n) {
    int gs = A[0], s = 0, i = n;
    while (i-- > 0) {
        s += A[i];
        if (gs < s) gs = s;
        if (s <= 0) s = 0;
    }
}

更相减损术

渐进时间复杂度为 $O(\log(a+b))$ ，且可推广至多个整数的情况

__int64 gcdCN(__int64 a, __int64 b) {
	int r = 0;
    while (!((a & 1) || (b & 1))) {
        a >>= 1, b >>= 1, r++;
    }
    while (1) {
        while (~(a & 1)) a >>= 1;
        while (~(b & 1)) b >>= 1;
        if (a > b) a = a - b;
        else b = b - a;
        if (a == 0) return b << r;
        if (b == 0) return a << r;
    }
}

动态规划

`fib()`

递归

1	int fib(int n) { return (n < 2) ? n : fib(n - 1) + fib(n - 2); }

复杂度： $T(0) = T(1) = 1$ $T (0) = T (1) = 1$ ， $T(n) = T(n - 1) + T(n - 2), \quad \forall n > 1$ $T (n) = T (n - 1) + T (n - 2), \forall n > 1$
- 令 $S(n) = [T(n) + 1] / 2 = S(n - 1) + S(n - 2) = fib(n + 1)$
- $T(n) = 2 \cdot S(n) - 1 = 2 \cdot fib(n + 1) - 1 = O(fib(n + 1)) = O(\phi ^ n)$
- 其中 $\phi = (1 + \sqrt{5}) / 2$
低效的根源在于，有大量重复的递归实例
- 去重之后，总共不过 $O(n)$ 种
记忆化：记住答案，直接“抄袭”（n-1）

Dynamic Programming

由自顶向下递归，改为自底向上迭代

int fib(int n) {
    int f = 1, g = 0;
    while (n-- > 0) {
        g = g + f;
        f = g - f;
    } // (f, g) -> (g, f + g)
	return g;
}

$T(n) = O(n)$ ，且仅需 $O(1)$ 空间

最长公共子序列

子序列：由序列中若干字符，按原相对次序构成（子串则需要连续）
Longest Common Subsequence：两个序列之间公共子序列中的最长者

分治递归

unsigned int lcs(char const *A, int n, const char *B, int m) {
    if (n < 1 || m < 1) return 0;
    if (A[n - 1] == B[m - 1])
        return 1 + lcs(A, n - 1, B, m - 1);
    else
        return max(lcs(A, n - 1, B, m), lcs(A, n, B, m));
}

LCS 的每一个解，对应于（0，0）与（n，m）之间的一条单调通路；反之亦然
最好情况 $O(n + m)$
最坏情况，就是 LCS(A[0], B[0]) 的重复次数，可达 $\binom{n + m}{n}$ $(n n + m)$
- 当 $n = m$ ，为 $\Omega(2^n)$ （ $O(4^n)$ ）
记忆化（或 DP）则只需 $O(nm)$

向量

抽象数据类型

数据结构都可看作是由若干数据项组成的集合，同时对数据项定义一组标准的操作。
抽象数据类型（Abstract Data Type，ADT）
- 将数据结构的外部特性与其内部实现相分离，提供一致且标准的对外接口，隐藏内部的实现细节
数据结构（Data Structure）
- 基于某种特定语言，实现 ADT 的一整套算法

从数组到向量

数组
- 元素各由编号唯一指代，并可直接访问
- 若每个元素占用空间为 $s$ （包含 padding），则 $A[i]$ 的物理地址为 $A + i \times s$
向量
- 数组的抽象和泛化，由一组元素按线性次序封装而成
- 各元素与 $[0, n)$ 内的秩一一对应
  1
  using Rank = unsigned int; // call-by-rank

Vector ADT

操作	功能	适用对象
`size() / empty()`	报告元素总数／判定是否为空	向量
`get(r) / put(r, e)`	获取秩为 r 的元素 / 用 e 替换秩为 r 元素的数值	向量
`insert(r, e) / insert(e)`	将 e 作为秩为 r 的／最后一个元素插入	向量
`remove(r) / remove(lo, hi)`	删除秩为 r／区间内的元素	向量
`disordered() / sort(lo, hi) / unsort(lo, hi)`	检测是否整体有序／整体排序／整体置乱	向量
`find(e, lo, hi) / search(e, lo, hi)`	在指定区间内查找目标 e	向量 / 有序向量
`dedup() / uniquify()`	剔除相等的元素	向量 / 有序向量
`traverse( visit() )`	遍历向量，统一按 `visit()` 处理所有元素	向量

可扩充的向量

动态空间管理
- 在即将上溢时，适当扩大内部数组的容量

扩容算法

template<typename T> void Vector<T>::copyFrom(T const *A, Rank lo, Rank hi) {
    _elem = new T[_capacity = (hi - lo) * 2];
    for (_size = 0; lo < hi; _size++, lo++) {
        _elem[_size] = A[lo];
    }
}
template<typename T> void Vector<T>::expand() {
    if (_size < _capacity) return;
    T* oldElem = _elem;
    copyFrom(oldElem, 0, _capacity);
    delete oldElem;
}

分摊分析

平均（average complexity）：根据各种操作出现概率的分布，将对应的成本加权平均
- 各种可能的操作，作为独立事件分别考查
- 割裂了操作之间的相关性和连贯性
分摊（amortized complexity）：连续实施的足够多次操作，所需总体成本摊还至单次操作
- 从实际可行的角度，对一系列操作做整体的考量
- 更加忠实地刻画了 可能出现的操作序列

容量递增策略

1	_elem = new T[_capacity += INCREMENT];

最坏情况：初始容量 0 的空向量，连续插入 $n = m \cdot I \gg 2$ $n = m \cdot I ≫ 2$ 个元素，无删除
- 总体耗时 = $0 + I + \cdots + (m - 1) \cdot I = O(n^2)$
- 每次插入删除操作分摊成本为 $O(n)$
空间利用率（装填因子）： $\lambda = \_size / \_capacity \approx 100\%$

容量加倍策略

1	_elem = new T[_capacity *= 2];

最坏情况：初始容量 1 的满向量，连续插入 $n = 2^m \gg 2$ $n = 2^{m} ≫ 2$ 个元素，无删除
- 总体耗时 = $1 + 2 + \cdots + 2^{m - 1} = O(n)$
- 每次（insert/remove）操作分摊成本为 $O(1)$
$\lambda > 50\%$

无序向量

删除

template<typename T> void Vector<T>::shrink() {
    if (_size << 2 > _capacity) return; // 以 25%(必须 < 50%)为界
    T* oldElem = _elem; _elem = new T[_capacity >>= 1];
    for (Rank i = 0; i < _size; i++) _elem[i] = oldElem[i];
    delete oldElem[];
}
template<typename T> Rank remove(Rank lo, Rank hi) {
    if (lo == hi) return 0;
    while (hi < _size) _elem[lo++] = _elem[hi++]; // 后缀[hi, n)前移
    _size = lo; shrink();
    return hi - lo;
}

查找

顺序查找
- 输入敏感（input-sensitive）
- 最好 $O(1)$ ，最差 $O(n)$

去重

template<typename T> Rank Vector<T>::dedup() {
    Rank oldSize = _size;
    for (Rank i = 1; i < _size;) {
        if (find(_elem[i], 0, i) == -1) i++; // O(i)
        else remove(i); // O(_size - i)
    }
    return oldSize - _size;
} // O(n^2)

有序向量

在有序序列中，任何一对相邻元素必顺序
- 相邻逆序对的数目，可在一定程度上度量向量的紊乱程度
无序向量经预处理转换为有序向量之后，相关算法多可优化

唯一化

template<typename T> Rank Vector<T>::uniquify() {
	Rank i = 0, j = 0;
    while (++j < _size) {
        if (_elem[i] != _elem[j]) {
            _elem[++i] = _elem[j];
        }
    }
    _size = ++i; shrink();
    return j - i;
}

二分查找（版本 A）

减而治之
- 若轴点 $mi$ $m i$ 取作重点，则每经过 至多两次 比较
  - 或者能够命中
  - 或者将问题规模减半

template<typename T> static Rank binSearch(T *S, T const &e, Rank lo, Rank hi) {
    while (lo < hi) {
        Rank mi = (lo + hi) >> 1;
        if (e < S[mi]) hi = mi;
        else if (S[mi] < e) lo = mi + 1;
        else return mi;
    }
    return -1; // 失败
}

线性“递归”： $T(n) = T(n / 2) + O(1) = O(\log n)$ $T (n) = T (n / 2) + O (1) = O (lo g n)$
- “递归跟踪”：轴点总能取到中点，递归深度 $O(\log n)$
关键码的比较次数 $\sim$ $\sim$ 平均查找长度
- $ASL_{succ} = O(1.50 \cdot \log n)$
- $ASL_{fail} = O(1.50 \cdot \log n)$

Fibonacci 查找

版本 A：转向左、右分支前的关键码比较次数不等，而递归深度却相同
- 可以通过递归深度的不均衡对转向成本的不均衡做补偿
- 若 $n = fib(k) - 1$ $n = f i b (k) - 1$ ，则可取 $mi = lo + fib(k - 1) - 1$ $m i = l o + f i b (k - 1) - 1$
  - 前、后子向量长度分别为 $fib(k - 1) - 1$ 、 $fib(k - 2) - 1$
  - 失败查找长度，最大为 $k - 1$ ，最小为 $k - 2$
  - 成功查找长度，最大为 $k - 1$ ，最小为 $2$

template<typename T> static Rank fibSearch(T *S, T const &e, Rank lo, Rank hi) {
    for (Fib fib(hi - lo); lo < hi;) { // Fib 数列制表备查
        while (hi - lo < fib.get()) fib.prev(); // 自后向前顺序查找轴点(分摊 O(1))
        Rank mi = lo + fib.get() - 1;
        if (e < S[mi]) hi = mi;
        else if (S[mi] < e) lo = mi + 1;
        else return mi;
    }
    return -1;
} // 有多个命中元素时, 不能保证返回秩最大者; 失败时, 简单地返回 －1, 而不能指示失败的位置

通用策略

在任何区间 $[0,n)$ $[0, n)$ 内，总是选取 $[\lambda \cdot n]$ $[λ \cdot n]$ 作为轴点， $0 \le \lambda < 1$ $0 \leq λ < 1$
- Fibonacci 查找对应 $\lambda = \frac{1}{\phi} = \frac{\sqrt{5} - 1}{2}$
这类查找算法的渐近复杂度为 $\alpha(\lambda) \cdot \log_2 n = O(\log n)$ $α (λ) \cdot lo g_{2} n = O (lo g n)$
- 递推式： $\alpha(\lambda) \cdot \log_2 n = \lambda \cdot [1 + \alpha(\lambda) \cdot \log_2 (\lambda n)] + (1 - \lambda) \cdot [2 + \alpha(\lambda) \cdot \log_2 ((1 - \lambda) n)]$
- 当 $\lambda = \frac{\sqrt{5} - 1}{2}$ 时， $\alpha(\lambda) = 1.440420...$ 达到最小

二分查找（版本 B）

每次迭代仅做一次关键码比较
- $e < x \rightarrow [lo, mi)$
- $x \le e \rightarrow [mi, hi)$
直到 $hi - lo = 1$ ，才判断是否命中
相较于版本 A，最好（坏）情况下更坏（好），整体性能更趋均衡

template<typename T> static Rank binSearch(T *S, T const &e, Rank lo, Rank hi) {
    while (hi - lo > 1) { // 有效查找区间的宽度缩短至 1 时, 算法才终止
        Rank mi = (lo + hi) >> 1;
        if (e < S[mi]) hi = mi;
        else lo = mi;
    }
    return e == S[lo] ? lo : -1;
}

返回值改进

约定总是返回 $m = search(e) = M - 1$ $m = s e a r c h (e) = M - 1$
- $-\infty \le m = \max\{k | [k] \le e\}$ ， $\min\{k | e < [k]\} = M \le +\infty$
直接改进版本 B
- return e < S[lo] ? lo - 1 : lo;

二分查找（版本 C）

template<typename T> static Rank binSearch(T *S, T const &e, Rank lo, Rank hi) {
    while (lo < hi) { // [0, lo) <= e < [hi, n)
        Rank mi = (lo + hi) >> 1;
        if (e < S[mi]) hi = mi;
        else lo = mi + 1;
    }
    // 出口时, 区间宽度缩减至 0, 且必有 [lo = hi] = M
    return lo - 1; // 至此, [lo] 为大于 e 的最小者
}

在算法执行过程中的任意时刻
- $[lo - 1]$ 总是（已确认的）不大于 $e$ 的最大者
- $[hi]$ 总是（已确认的）大于 $e$ 的最小者
算法终止时， $[lo - 1] = [hi - 1]$ 即为全局不大于 $e$ 的最大者
$ASL_{succ} = ASL_{fail} = O(1.00 \cdot \log n)$

插值查找

大数定律：越长的序列，元素的分布越有规律
- 最为常见：独立且均匀的随机分布
因此，通过猜测轴点 $mi$ ，可以极大地提高收敛速度
- $mi \approx lo + (hi - lo) \cdot \frac{e - A[lo]}{A[hi] - A[lo]}$
最坏情况： $hi - lo = O(n)$ （ $1, 1, \dots, 2, 10^{10}$ 中查找“2”）
平均：每经过一次比较，待查找区间宽度由 $n$ 缩至 $\sqrt{n}$
- $n \rightarrow n^{1/2^1} \rightarrow n^{1/2^2} \rightarrow \cdots 2$ ， $O(\log \log n)$
每经过一次比较，查找区间宽度的数值 $n$ 开方，有效字长 $\log n$ 减半
- 插值查找 = 在字长意义上的折半查找
- 二分查找 = 在字长意义上的顺序查找
实际可行的方法：算法接力
- 先插值查找，迅速缩小查找范围
- 再改为二分查找，进一步缩小
- 最后顺序查找

起泡排序

扫描交换，依次比较每一对相邻元素；如有必要，交换之。直至某趟扫描后，确认相邻元素均以顺序。

经过 $k$ 趟扫描交换后，最大的 $k$ 个元素必然就位，问题规模缩减至 $n - k$
至多 $n$ 趟扫描后，算法必然终止，并给出正确解答

template<typename T> void Vector<T>::bubbleSort(Rank lo, Rank hi) {
    for (Rank last; lo < hi; hi = last) {
        for (Rank i = (last = lo) + 1; i < hi; ) {
            if (_elem[i - 1] > _elem[i]) {
                swap(_elem[i - 1], _elem[i]);
                last = i;
            }
        }
    }
} // 跳跃版, 每次扫描后[last, hi)为已有序后缀

时间效率：最好 $O(n)$ ，最坏 $O(n^2)$
在起泡排序中，唯有相邻元素才可交换，故是稳定的
- 排序算法的稳定性：相等的元素在输入、输出序列中的相对次序，是否保持不变？

比较树

基于比较式算法（Comparison-Based Algorithm，CBA）可以被转换为一个树形结构。该树形结构具有以下性质：
- 每一内部节点各对应于一次比对操作
- 内部节点的左、右分支，分别对应与在两种比对结果下的执行方向
- 叶节点（或根到叶节点的路径）对应于算法某次执行的完整过程及输出
- 反过来，算法的每一运行过程都对应于从根到某一叶节点的路径
设 $CT(A)$ $C T (A)$ 为某一 CBA 式算法 $A$ $A$ 对应的比较树
- 那么算法 $A$ 在最坏情况下的运行时间，取决于该树的高度 $h(CT(A))$
- 算法 $A$ 的时间复杂度应不低于 $\Omega(h(CT(A)))$
若某一问题的输出结果不少于 $N$ $N$ 种，则
- 比较树叶节点不可能少于 $N$ 个，树高不可能低于 $\log_2 N$
由此任一 CBA 式排序算法对应的比较树高度应为
- $h \ge \left \lceil \log_3(n!) \right \rceil = \left \lceil \log_3(e) \cdot \ln(n!) \right \rceil = \Omega(n \log n)$
- 最坏情况下 CBA 式排序算法至少需要 $\Omega(n \log n)$ 时间， $n$ 为待排序元素数目

归并排序

分而治之，向量和列表通用
- 序列一分为二
- 子序列递归排序
- 合并有序子序列

template<typename T> void Vector<T>::mergeSort(Rank lo, Rank hi) {
    if (hi - lo < 2) return;
    Rank mi = (lo + hi) >> 1;
    mergeSort(lo, mi);
    mergeSort(mi, hi);
    merge(lo, mi, hi); // 归并
}

二路归并

有序序列合二为一，保持有序

template<typename T> void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {
	Rank i = 0; T* A = _elem + lo;
    Rank j = 0, lb = mi - lo; T* B = new T[lb];
    for (Rank i = 0; i < lb; i++) B[i] = A[i];
    Rank k = 0, lc = hi - mi; T* C = _elem + mi;
    // 后缀 C[0, lc) = _elem[mi, hi), 就地
    while ((j < lb) && (k < lc))
        A[i++] = (B[j] <= C[k]) ? B[j++] : C[k++];
    while (j < lb)
        A[i++] = B[j++]; // 若 B 先耗尽, A 中对应的 C 的残余已然有序
    delete[] B;
}

复杂度

二路归并每次累计迭代步数 $\le lb + lc = n$ $\leq l b + l c = n$ ，只需 $O(n)$ $O (n)$
- 总体 $T(n) = 2 \cdot T(n / 2) + O(n) = O(n \log n)$
优点
- 最坏情况下最优 $O(n\log n)$ 性能
- 不需随机读写，完全顺序访问
- 实现恰当，可保证稳定
- 适用于外部排序，易于并行化
缺点
- 非就地
- 即使输入已完全（或接近）有序，仍需 $\Omega(n \log n)$ 时间

位图

期望功能，对于有限整数集 $S$ ， $\forall 0 \le k < U$
- $k \in S\, ?$ ，bool test(int k)
- $S \cup \{k\}$ ，void set(int k)
- $S \setminus \{k\}$ ，void clear(int k)

结构：用每一个比特位标记一个整数，8 位压缩为一个 char

class Bitmap {
private:
    unsigned char *M;
    Rank N, _sz;
public:
    Bitmap(Rank n = 8) {
        M = new unsigned char[N = (n + 7) / 8];
        memset(M, 0, N); _sz = 0;
    }
    ~Bitmap() { delete[] M; M = NULL; _sz = 0; }
    void set(int k); void clear(int k); bool test(int k);
}

实现

bool test(Rank k) {
    expand(k);
    return M[k >> 3] & (0x80 >> (k & 0x07));
}
void set(Rank k) {
    if (test(k)) return;
    expand(k); _sz++;
    M[k >> 3] |= (0x80 >> (k & 0x07));
}
void clear(Rank k) {
    if (!test(k)) return;
    expand(k); _sz--;
    M[k >> 3] &= ~(0x80 >> (k & 0x07));
}

典型应用

小集合+大数据

数据体量大，但有大量相等数据
- $m \ll n$

筛法

void Erathsthenes(Rank n, char *file) {
    Bitmap B(n); B.set(0), B.set(1);
    for (Rank i = 2; i < n; i++) {
        if (!B.test(i)) {
            for (Rank j = 2 * i; j < n; j+= i) {
                B.set(j);
            }
        }
    }
    B.dump(file);
}

内循环每趟迭代 $O(n / i)$ 步，由素数定理外循环至多 $\frac{n}{\ln n}$ 趟，累计耗时

$\begin{aligned}&\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \cdots \\ < \quad &\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \cdots + \frac{n}{n / \ln n} \\ = \quad &O(n \cdot (\ln(n / \ln n) - 1)) = O(n \cdot \log n) \end{aligned}$
常系数优化：内循环的起点可以改为 i * i ，外循环的终止条件可以改为 i * i < n

快速初始化

将 $B[]$ 拆分成一对等长向量
- F[k] （初始）存储元素的插入顺序（可能发生变化，主要用来检验数据是否有效），同时也是 T[] 中 $k$ 对应的下标。T[] 用来存储元素 $k$
每个有效元素满足 T[F[k]] == k && F[T[i]] = i ，构成 校验环

Rank F[m]; // From
Rank T[m], top = 0; // To 及栈顶位置标记

bool Bitmap::test(Rank k) {
    return (F[k] != -1) && (F[k] < top) && (k == T[F[k]]);
}

void Bitmap::reset() { top = 0; } // O(1)复位

void Bitmap::set(Rank k) { // O(1)插入
    if (!test(k)) {
        T[top] = k;
        F[k] = top++;
    }
}

void Bitmap::clear(Rank k) { // O(1)删除
    if (test(k) && (--top)) {
        F[T[top]] = F[k];
        T[F[k]] = T[top];
    } // 相当于使用栈顶的元素顶替被删除的空位
}

列表

循位置访问

列表（list）是采用动态储存策略的典型结构
- 元素称为节点，通过引用或者指针彼此联接
- 在 逻辑上 构成一个线性序列，各元素的物理地址将不再决定逻辑次序
- 动态操作可以在局部完成，复杂度有望控制在 $O(1)$
循位置访问：利用节点之间的相互引用，找到特定的节点
- 如果按逻辑次序进行连续访问，单次也是 $O(1)$
- call-by-position

接口与实现

ListNode

操作接口	功能
`pred()` / `succ()`	当前节点的前驱/后继节点的位置
`data()`	当前节点所存数据对象
`insertPred()` / `insertSucc()`	插入前驱/后继节点，返回新节点位置

List ADT

操作接口	功能	适用对象
`size()` / `empty()`	报告节点总数 / 判定是否为空	列表
`first()` / `last()`	返回首 / 末节点的位置	列表
`insertFirst()` / `insertLast()`	将 e 当作首／末节点插入	列表
`insert(p, e)` / `insert(e, p)`	将 e 当作节点 p 的直接后继、前驱插入	列表
`remove(p)`	删除节点 p	列表
`sort(p, n)` / `sort()`	区间／整体排序	列表
`find(e, n, p)` / `search(e, n, p)`	在指定区间内查找目标 e	列表 / 有序列表
`dedup()` / `uniquify()`	剔除相等的节点	列表 / 有序列表
`traverse(visit())`	遍历列表，统一按 `visit()` 处理所有节点	列表

可设置哨兵节点

ListNodePosi<T> head, tail;
template<typename T> void List<T>::init() {
    head = new ListNode<T>;
    tail = new ListNode<T>;
    
    head->succ = tail; head->pred = null;
    tail->pred = head; tail->succ = null;
    _size = 0;
}

动态储存策略带来的静态操作效率低下

template<typename T> T& List<T>::operator[] (Rank r) const {
    ListNodePosi<T> p = first();
    while (r-- > 0) p = p->succ;
    return p->data;
}

有序列表

唯一化

template<typename T> Rank List<T>::uniquify() {
    if (_size < 2) return 0;
    Rank oldSize = _size;
    ListNodePost<T> p = first(), q;
    while (tail != (q = p->succ())) { // 反复考察紧邻节点对(p, q)
        if (p->data != q->data) p = q;
        else remove(q);
    }
} // O(n)

查找

template<typename T> ListNodePost<T> List<T>::search(T const &e, Rank n, ListNodePosi<T> p) const {
    do {
        p = p->pred; n--;
    } while ((n != -1) && (e < p->data));
    return p;
} // 在有序列表内节点 p 的 n 个真前驱中, 找到不大于 e 的最靠后者

最好 $O(1)$ ，最坏 $O(n)$ ；等概率时平均 $O(n)$
不能借助有序性提高查找效率，因为无法高效实现秩的随机访问

选择排序

起泡排序扫描交换的实质无非是
- 通过比较找到当前的最大元素 $M$ ，并通过交换使其就位
- 其中 $O(n)$ 次交换完全没有必要
在经 $O(n)$ 次比较确定 $M$ 后，仅需一次交换即可

template<typename T> ListNodePosi<T> List<T>::selectMax(ListNodePosi<T> p, rank n) {
    ListNodePosi<T> max = p;
    for (ListNodePosi<T> cur = p; n > 1; n--) {
        if (!((cur = cur->succ)->data < max->data))
            max = cur;
    }
    return max;
}

template<typename T> void List<T>::selectionSort(ListNodePosi<T> p, Rank n) {
    ListNodePosi<T> h = p->pred;
    ListNodePosi<T> t = p;
    for (Rank i = 0; i < n; i++) t = t->succ;
    // 待排序区间为(h, t)
    while (n > 1) {
        insert(remove(selectMax(h->succ, n)), t);
        // 可改为互换 data, 减少额外开销
        t = t->pred; n--;
    }
}

采用 平移法，可保证稳定性；每一组相等的元素，都保持输入时的相对次序
总体时间复杂度为 $\Theta(n^2)$ ，主要来自于元素的比较操作

循环节

任何一个序列 $\mathcal{A}[0,n)$ $A [0, n)$ ，都可分解为若干个循环节
- 元素 $\mathcal{A}[k]$ $A [k]$ 在序列对应的有序序列 $\mathcal{S}[0, n)$ $S [0, n)$ 中的秩，记作 $r(\mathcal{A}[k]) = r(k) \in [0, n)$ $r (A [k]) = r (k) \in [0, n)$ ，其所属循环节为
  - $k, r(k), r(r(k)), \dots, r(\dots (r(r(k))) \dots) = k$
  - $r^0(k), r^1(k), r^2(k), \dots, r^{(d)}(k) = k$
任意循环节长度 $d \le n$ ，循环节之间互不相交

对于 交换法 选择排序

每迭代一步， $M$ $M$ 都会脱离原属的循环节，自成一个循环节
- $M$ 原属循环节，长度恰好减少一个单位；其他循环节保持不变
多余的交换： $M$ $M$ 已经就位，实际上无需交换
- 最初有 $c$ $c$ 个循环节，则这种情况会出现 $c-1$ $c - 1$ 次（不计入最后一次迭代）
  - 若交换不多余，则循环节数量 +1
- 最大值为 $n$ ，期望 $\Theta(\log n)$

插入排序

始终将序列视为两部分
- 前缀 $S[0, r)$ ：有序
- 后缀 $U[r, n)$ ：待排序
反复地，针对 $e = A[r]$ ，在 $S$ 中查找适当位置，插入 $e$ ， $r$ ++

template<typename T> void List<T>::insertionSort(ListNodePosi<T> p, Rank n) {
    for (Rank r = 0; r < n; r++) {
        insert(search(p->data, r, p), p->data);
        p = p->succ(); remove(p->pred);
    }
} // 就地算法

前缀总是保持有序且稳定
最好 $O(n)$ ，最坏 $O(n^2)$ ，平均（期望） $O(n^2)$
可在线执行

归并排序

template<typename T> ListNodePosi<T> List<T>::merge(ListNodePosi<T> p, Rank n, List<T> &L, ListNodePosi<T> q, Rank m) {
    ListNodePosi<T> pp = p->pred;
    while (m > 0 && p != q) {
        if (n > 0 && p->data <= q->data) {
            p = p->succ; n--;
        } else {
            insert(L.remove((q = q->succ)->pred), p); m--;
        }
    }
    return pp->succ;
}

template<typename T> void List<T>::mergeSort(ListNodePosi<T> &p, Rank n) {
    if (n < 2) return;
    ListNodePosi<T> q = p; Rank m = n >> 1;
    for (Rank i = 0; i < m; i++) q = q->succ;
    mergeSort(p, m); mergeSort(q, n - m);
    p = merge(p, m, *this, q, n - m);
} // O(nlogn)

逆序对

$\mathcal{I}(j) = \lVert \{ 0 \le i < j \, | \, A[i] > A[j]\} \rVert$
逆序对总数 $\mathcal{I} = \sum \mathcal{I}(j) \le \binom{n}{2} = O(n^2)$

BubbleSort

在序列中交换一对紧邻的逆序元素，逆序对总数恰好减一
对于起泡排序而言，交换操作的次数恰等于输入序列所含逆序对总数

InsertionSort

每次迭代查找插入位置，恰好需要做 $\mathcal{I}(r)$ 次比较
若序列共含 $\mathcal{I}$ $I$ 个逆序对，则
- 关键码比较次数为 $O(\mathcal{I})$
- 运行时间为 $O(n + \mathcal{I})$
若任意逆序对距离不超过 $k$ ，则复杂度为 $O(k \cdot n)$

计数

朴素算法需要 $\Omega(n^2)$ ，借助归并排序仅需 $O(n \log n)$

游标实现

在一块连续的静态内存（数组）中，模拟出链表的动态链接特性
所需结构如下：
- 一个结构数组或两个独立数组
  - elem[] ：存放数据元素的数组
  - link[] ：存放“指针”的数组，称之为游标
    - link[i] 的值是 elem[i] 的后继元素所在的 elem[] 下标
- 两个逻辑上互补的链表
  - data ：存放当前存在的所有数据
  - free ：存放所有当前空闲、可被分配的数组槽位
- 两个“头指针”（头游标）
  - dataHead ：存储 data 链表的第一个元素所在的数组下标
  - freeHead ：存储 free 链表的第一个可用槽位所在的数组下标
- 空指针标记
  - 需要一个特殊值来表示链表的末尾（相当于 NULL），约定使用 -1 来表示

const int N = 1000;
int elem[N], link[N], data, free;

void init() {
    free = 0, data = -1;
    for (int i = 0; i < N - 1; i++) link[i] = i + 1;
    link[N - 1] = -1;
}

核心操作

int allocNode() {
    if (free == -1) return -1;
    int nw = free; free = link[free];
    return nw;
}
void freeNode(int index) {
    link[index] = free; free = index;
} // 将被释放的节点放入 free 链表头部

int insert(int value) { // 相当于在 data 链表头部插入
    int newIndex = allocNode();
    if (newIndex == -1) return -1;
    elem[newIndex] = value;
    link[newIndex] = data;
    data = newIndex;
    return newIndex;
}

int find(int value) {
    int r;
    for (r = data; r != -1; r = link[r]) {
        if (elem[r] == value) return r;
    }
    return -1;
}

bool remove(int pos) { // 删除下标为 pos 的节点的后继节点
    int idx = link[pos];
    if (idx == -1) return false;
    link[pos] = link[idx]; // 绕过删除目标
    freeNode(idx);
    return true;
}

栈和队列

栈

接口与实现

栈（stack）是受限的序列
- 只能在栈顶（top）插入和删除，栈底为盲端
- 后进先出（LIFO）
可直接基于向量或者列表派生

template<typename T> class Stack : public Vector<T> {
public:
    void push(T const &e) { insert(e); }
    T pop() { return remove(size() - 1); }
    T &top() { return (*this)[size() - 1]; }
};

以向量首端为栈底，末端为栈顶，由此实现的栈接口，均只需 $O(1)$ $O (1)$
- 基于列表派生，也可只需 $O(1)$

调用栈

递归算法所需的空间主要取决于递归深度，而非递归实例总数

消除递归

隐式地维护调用栈，需要花费额外的空间、时间；为此可
- 显示地维护调用栈
- 将递归算法改写为迭代版本（改写尾递归）
时间复杂度有常系数改进，空间复杂度或有渐近改进

进制转换

短除法：对进制 $\lambda$ $λ$ 反复整除、留余，即可自低而高得出 $\lambda$ $λ$ 进制的各位
- 位数 $m + 1 = \left \lfloor \log_\lambda n \right \rfloor + 1$

void convert(Stack<char> &S, unsigned long long n, int base) {
    char digit[] = "0123456789ABCDEF";
    while (n > 0) {
        S.push(digit[n % base]);
        n /= base;
    }
}
main() {
    Stack<char> S;
    (n > 0) ? convert(S, n, base) : S.push('0');
    while (!S.empty()) S.pop();
}

括号匹配

平凡：无括号的表达式是匹配的
为有效简化问题，需发现和借助 必要性
- 消去一对紧邻的左右括号，不影响全局的匹配判断
  - 顺序扫描表达式，用栈记录已扫描的部分
  - 反复迭代：凡遇 ( ，则进栈；凡遇 ) ，则出栈

bool paren(const char exp[], Rank lo, Rank hi) {
    Stack<char> S;
    for (Rank i = lo; i < hi; i++) {
        if (exp[i] != '(') S.push(exp[i]);
        else if (!S.empty()) S.pop();
        else return false;
    }
    return S.empty();
}

可推广至多种括号的情况

中缀表达式求值

给定语法正确的算数表达式 $\mathcal{S}$ ，计算与之对应的数值

减而治之：优先级高的局部表达式执行计算，并被代以其数值，运算符减少，直至得到最终结果
但仅根据表达式的前缀，不足以确定各运算符的计算次序
- 为处理某一前缀，必须提前 预读并分析更长的前缀
- 需借助某种支持延迟缓冲的机制
求值算法 = 栈 + 线性扫描

const char pri[N_OPTR][N_OPTR] = {
	// 运算法优先等级 [栈顶][当前]
    // '<': 栈顶运算符优先级更低, 当前运算符进栈
    // '>': 时机已到, 可以进行计算
    // '~': 部分计算结束
    // ' ': padding
};
double evaluate(char *S, char *RPN) {
    Stack<double> opnd; Stack<char> optr; // 运算数栈和运算符栈
    optr.push('\0'); // 哨兵
    while (!optr.empty()) {
        if (isdigit(*S)) {
            readNumber(S, opnd);
        } else { // 若为运算符
            // 视其与栈顶运算符之间优先级的高低分别处理
            switch(priority(optr.top(), *S)) {
                case '<':
                    optr.push(*S);
                    S++;
                    break;
                case '>':
                    char op = optr.pop();
                    if (op != '!') { // 一元运算符
                        opnd.push(calcu(op, opnd.pop()));
                    } else {
                        double opnd2 = opnd.pop(), opnd1 = opnd.pop();
                        opnd.push(calcu(opnd1, op, opnd2));
                    }
                    break;
                case '~':
                    // pri ['('][')'] = pri ['\0']['\0'] = '~'
                    optr.pop();
                    S++;
                    break;
                default: exit(-1);
            }
        }
    }
    return opnd.pop();
}

逆波兰表达式

定义和求值

Reverse Polish Notation，在由运算符（operator）和操作数（operand）组成的表达式中，不使用括号，即可表示带优先级的运算关系
相较于日常使用的中缀式（infix），RPN 亦称作后缀式（postfix）
作为补偿，须额外引入一个起分隔作用的原字符（如空格）
- 相较原表达式，长度未必更短
栈式求值（不会检查式子合法性）
- 引入栈 $\mathcal{S}$ （存放操作数）
- 逐个处理下一元素 x
  - 若 x 是操作数，则将其压入 S
  - 否则（运算符无序缓冲）
    - 从 S 中弹出 x 所需数目的操作数
    - 进行运算，结果压入 S
- 返回栈顶结果

转换

手工转换
- 为每一个运算添加括号
- 以运算符替换右括号，并清除对应左括号

自动转换

double evaluate(char *S, char *RPN) {
    /* ... */
    while (!optr.empty()) {
        if (isdigit(*S)) {
            readNumber(S, pond);
            append(RPN, opnd.top());
        } else {
            switch(priority(optr.top(), *S)) {
                case '>':
                    // 若可立即计算, 则在执行计算同时将其接入 RPN
                    char op = optr.pop();
                    append(RPN, op);
            }
            /* ... */
        }
    }
    /* ... */
}

栈混洗

考察栈 $\mathcal{A} = \left \langle a_1, a_2, \dots, a_n \right.], \quad \mathcal{B} = \mathcal{S} = \varnothing$

只允许

将 A 的顶元素弹出并压入 S

将 S 的顶元素弹出并压入 B

经一系列上述操作，A 中元素全部转入 B 中

$\mathcal{B} = [\left. a_{k_1}, a_{k_2}, \dots, a_{k_n} \right \rangle$ 则称为 A 的一个栈混洗

计数

同一输入序列，可有多种栈混洗
- 对于长度为 $n$ 的序列，混洗总数 $SP(n) \le n!$
$SP(1) = 1$
考查 S 再度变空（A 首元素从 S 中弹出）的时刻，无非 $n$ 种情况

$\begin{aligned} SP(n) &= \sum_{k = 1}^n SP(k - 1) \cdot SP(n - k) \\ &=\text{Catalan}(n) = \frac{(2n)!}{(n + 1)! \cdot n!} \end{aligned}$

甄别

输入序列 $\left \langle 1, 2, 3, \dots, n \right.]$ 的任一排列 $[\left. p_1, p_2, p_3, \dots, p_n \right \rangle$ 是否为栈混洗？

禁形：对任何 $1 \le i < j < k \le n, \quad [\left. \dots, k, \dots, i, \dots, j, \dots \right \rangle$ 必非栈混洗
不存在 “312(915)” 模式的序列 $\iff$ 是栈混洗，可得 $O(n^3)$ 的甄别算法
进一步， $[\left. p_1, p_2, \dots, p_n \right \rangle$ 是 $\left \langle 1, 2, \dots, n \right.]$ 的栈混洗，当且仅当

对于任意 $i < j$ ，不含模式 $[\left. \dots, j + 1, \dots, i, \dots, j, \dots \right \rangle$ （615）
- 如此可得 $O(n^2)$
$O(n)$ 算法：借助栈 A、B 和 S，直接模拟栈混洗过程
- 逐个检视各目标元素
  - 若在（或能腾挪至）S 顶部，则继续
  - 否则（在 S 中，却非栈顶，无法洗出）失败

总结

$\text{Catalan}(n)$ 的情况总结

$n$ 个元素栈混洗（ $n$ 次 push 和 $n$ 次 pop 对应的合法操作序列数）
$n$ 对匹配的括号的可能情况数
$n$ 个节点二叉树的形态
$n$ 个节点互异的 BST 的种类
$n + 1$ 个 叶节点（ $n$ 个内部节点）的真二叉树的形态
中序遍历是 $1\sim n$ 的二叉树的全部后序遍历序列数（先序遍历是入栈序列，后序遍历是出栈序列）
$n + 1$ 个节点的有序多叉树（对应一棵唯一的 $n$ 节点二叉树）采用“长子-兄弟表示法”得到二叉树形态数
$n + 2$ 个顶点的凸多边形进行三角剖分的方案数
圆上 $2n$ 个点连接 $n$ 条不相交弦的方法数
$n \times n$ 网格中不越过对角线的 Dyck 路径数

队列

接口与实现

队列（queue）也是受限的序列
只能在队尾插入（查询）
- enqueue() / rear()
只能在队头删除（查询）
- dequeue() / front()
先进先出（FIFO）

template<typename T> class Queue : public List<T> {
public:
    void enqueue(T const &e) { insertLast(e); }
    T dequeue() { return remove(first()); }
    T &front() { return first()->data; }
}

如此实现的队列接口，均只需 $O(1)$ $O (1)$ 时间
- 基于向量派生也是如此

队列应用

资源循环分配
银行服务模拟

直方图内最大矩形

对每个位置 $r$ $r$ ，计算
- $s(r) = \max\{k \, | \, 0 \le k \le r \cap H[k - 1] < H[r]\}$
- $t(r) = \min\{k \, | \, r < k \le n \cap H[r] > H[k]\}$
- $answer = \max\{H[r] \cdot (t(r) - s(r))\}$
- 可以 $O(n^2)$ 暴力计算，也可使用 单调栈 通过两次线性扫描得出
若要优化至一次扫描，则可使用单调栈 S 维持高度 H 的单调递增
- 若栈空或 H[t] < H[S.top()] ，则直接压栈
- 否则，不断弹栈，直到将当前高度压栈后可保持单调性；同时在这过程中不断计算更新面积最大值

Stack<Rank> SR; unsigned long long maxRect = 0;
for (Rank t = 0; t <= n; t++) { // 循环到 n(哨兵)
    while (!SR.empty() && (t == n || H[SR.top()] > H[t])) {
        Rank r = SR.pop(), s = SR.empty() ? 0 : SR.top() + 1;
        maxRect =  max(maxRect, (t - s) * H[r]);
    }
    if (t < n) SR.push(t);
}
return maxRect;

Steap

Steap = Stack + Heap = push + pop +getMax = S + P
P 中每个元素，都是 S 中对应前缀的最大者

1
2
3

Steap::getMax() { return P.top(); }
Steap::pop() { P.pop(); return S.pop(); }
Steap::push() { P.push(max(e, P.top())); S.push(e); }

可对 P 升级：使用计数器而不用保存过多重复元素

Queap

Queap = Queue + Heap = enqueue + dequeue + getMax = Q + P

Queap::dequeue() { P.dequeue(); return Q.dequeue(); }
Queap::enqueue() { // 最坏 O(n)
    Q.enqueue(e); P.enqueue(e);
    for (auto x = P.rear(); x && (e >= x->key); x = x->pred) {
        x->key = e;
    }
}

同样可对 P 维护一个计数器

双栈当队

def Q.enqueue(e):
    R.push(e)
    
def Q.dequeue():
    if F.empty():
        while !R.empty():
            F.push(R.pop())
    return F.pop()

均摊复杂度为 $O(1) / O(1)$

二叉树

概述

动机
- 层次结构的表示
- 兼具 Vector 和 List 的优点，兼顾高效的查找、插入、删除
- 不再是简单的线性结构，
  - 但确定某种次序后，具有线性特征

有根树

树是极小连通图、极大无环图 $\mathcal{T} = (V; \, E)$

节点数 $n = \left\vert V \right\vert$ ，边数 $e = \left\vert E \right\vert$

删边不连通，加边必成环

指定任一节点 $r \in V$ 作为根后， $\mathcal{T}$ 即称作有根树
相对于 $\mathcal{T}$ ， $\mathcal{T}_i$ 称作以 $r_i$ 为根的子树，记作 $\mathcal{T}_i = \text{subtree}(r_i)$

有序树

$r_i$ 称作 $r$ 的孩子， $r_i$ 之间互称兄弟
$d = \text{degree}(r)$ $d = degree (r)$ 为 $r$ $r$ 的（出）度
- $e = \sum_{v \in V} \text{degree}(v) = n - 1 = \Theta(n)$
若指定 $\mathcal{T}_i$ 为 $\mathcal{T}$ 的第 $i$ 棵子树， $r_i$ 为 $r$ 的第 $i$ 个孩子，则 $\mathcal{T}$ 称作有序树

深度

路径长度即为所含边数
- $\left\vert \pi \right\vert = \left\vert \{(v_0, v_1), (v_1, v_2), \dots, (v_{k - 1}, v_k)\} \right\vert = k$
- 环路： $v_0 = v_k$
任一节点 $v$ $v$ 与根之间存在唯一路径
- $\text{path}(v, r) = \text{path}(v)$
- 该路径上节点，均为 $v$ 的祖先
$v$ $v$ 的深度： $\text{depth}(v) = \left\vert \text{path}(v) \right\vert$ $depth (v) = ∣ path (v) ∣$
- 根节点是所有节点的公共祖先，深度为 0
没有后代的节点称作叶子节点
- 所有叶子深度中的最大者称作（子）树的高度
  - $\text{height}(v) = \text{height}(\text{subtree}(v))$
  - 空树高度为-1
  - $\text{depth}(v) + \text{height}(v) \le \text{height}(\mathcal{T})$

二叉树

节点度数不超过 2，孩子可以左、右区分（隐含有序）

有根且有序的多叉树，可以转化表示为二叉树
- 长子 $\sim$ 左孩子
- 兄弟 $\sim$ 右孩子

基数

设度数为 0、1 和 2 的节点，各有 $n_0$ 、 $n_1$ 和 $n_2$ 个

边数 $e = n - 1 = n_1 + 2 n_2$
叶节点数 $n_0 = n_2 + 1$

真二叉树

所有节点度数均为偶数（ $n_1 = 0$ ）

所有二叉树均可通过引入 $2 n_0 + n_1$ $2 n_{0} + n_{1}$ 个 外部节点 转换为二叉树
- 原有节点度数统一为 2
转换之后，全树复杂度 $\Theta(n)$ $Θ (n)$ 并未实质增加
- 但简化了描述、实现、分析
节点总数为奇数，树的最大高度为 $\frac{n - 1}{2}$

满树

深度为 $k$ 的节点，至多 $2^k$ 个
$n$ $n$ 个节点、高 $h$ $h$ 的二叉树满足： $h + 1 \le n \le 2^{h + 1} - 1$ $h + 1 \leq n \leq 2^{h + 1} - 1$
- $n = h + 1$ ：退化为单链
- $n = 2^{h + 1} - 1$ ：即为满二叉树

模版类和实现

template<typename T> using BinNodePosi = BinNode<T>*;
template<typename T> struct BinNode {
    BinNodePosi<T> parent, lc, rc;
    T data; Rank height, npl; RBColor color; // 数据, 高度, null path length, 颜色
    Rank size(); Rank updateHeight(); void updateHeightAbove(); // 更新规模, 高度
    
    BinNodePosi<T> insertLc(T const &);
    BinNodePosi<T> insertRc(T const &);
    BinNodePosi<T> succ(); // (中序遍历意义下)当前节点的直接后继
    /* ... */
}

先序遍历

遍历：按照某种次序访问树中各节点，每个节点被访问恰好一次

递归实现

template<typename T, typename VST> void traverse(BinNodePosi<T> x, VST &visit) {
    if (!x) return;
    visit(x->data);
    traverse(x->lc, visit);
    traverse(x->rc, visit);
} // O(n)

迭代实现

藤 = 起始于根的左侧通路 = 长子通路
- 沿着藤，整个遍历过程可被分为
  - 自上而下访问藤上节点
  - 再自下而上遍历各右子树
- 各右子树的遍历彼此独立，自成一个子任务

template<typename T, typename VST> static void visitAlongVine(BinNodePosi<T> x, VST &visit, Stack<BinNodePosi<T>> &S) {
    while (x) {
        visit(x->data);
        if (x->rc) S.push(x->rc);
        x = x->lc;
    }
}

template<typename T, typename VST> void travPre_I2(BinNodePosi<T> x, VST &visit) {
    Stack<BinNodePosi> S;
    while (true) {
        visitAlongVine(x, visit, S);
        // 访问子树 x 的藤蔓, 各右子树(根)入栈缓冲
        if (S.empty()) break;
        x = S.pop();
    }
}

中序遍历

整个树结构向下投影即为中序遍历序列

递归实现

template<typename T, typename VST>
void traverse(BinNodePosi<T> x, VST &visit) {
    if (!x) return;
    traverse(x->lc, visit);
    visit(x->data);
    traverse(x->rc, visit);
}

迭代实现

沿藤分解，遍历过程可 自底向上 分解为 $d+1$ $d + 1$ 步迭代
- 访问藤上节点，再遍历其右子树
各右子树的遍历彼此独立，自成一个 子任务

template<typename T> static void goAloneVine(BinNodePosi<T> x, Stack<BinNodePosi<T>> &S) {
    while (x) {
        S.push(x);
        x = x->lc;
    }
}

template<typename T, typename VST> void travIn_I1(BinNodePosi<T> x, V &visit) {
    Stack<BinNodePosi<T>> S;
    while (true) {
        goAloneVine(x, S);
        if (S.empty()) break;
        x = S.pop(); // 此时 x 的左子树为空, 或已遍历
        visit(x->data);
        x = x->rc;
    }
}

直接后继

简明遍历
1
for (BinNodePosi<T> t = first(); t; t = t->succ()) { /* ... */ }
- 若节点有右孩子，则直接后继为最靠左的右后代
- 否则，其直接后继为最低的左祖先

template<typename T> BinNodePosi<T> BinNode<T>::succ() {
    BinNodePosi<T> s = this;
    if (rc) {
        s = rc;
        while (HasLChild(s)) s = s->lc;
    } else {
        while (isRChild(s)) s = s->parent;
        s = s->parent;
    } // 两种情况均为 O(h)
    return s;
}

template<typename T, typename VST> void travIn_I4(BinNodePosi<T> x, VST &visit) {
    while (true) {
        if (HasLChild(x)) x = x->lc;
        else {
            visit(x->data);
            while (!HasRChild(x)) { // 不断在无右分支处回溯到直接后继
                if (!(x = x->succ())) return;
                visit(x->data);
            }
            x = x->rc;
        }
    }
} // O(n), 每条边被经过的次数 <= 2

实际上，在由 $n$ 个节点构成的二叉树中，将任意节点 $u$ 和 $v$ 之间的距离取作二者之间那条唯一通路的长度，记作 $\left\vert uv \right\vert$ 。若二叉树的先序/中序/后序遍历序列为 $\{v_0,v_1,v_2,\dots,v_{n-1}\}$ ，则有： $\left\vert v_0v_1 \right\vert + \left\vert v_1v_2 \right\vert + \dots + \left\vert v_{n-2}v_{n-1} \right\vert + \left\vert v_{n-1}v_0 \right\vert = 2(n-1)$

后序遍历

递归实现

template<typename T, typename VST>
void traverse(BinNodePosi<T> x, VST &visit) {
    if (!x) return;
    traverse(x->lc, visit);
    traverse(x->rc, visit);
    visit(x->data);
}

迭代实现

目标是逐次访问当前的最靠左的叶子节点
沿藤分解，从根出发下行 尽可能沿左分支，实不得已才沿右分支
- 最后一个节点必是叶子，也是中序次序中最靠左的叶子

template<typename T> static void gotoLeftmostLeaf(Stack<BinNodePosi<T>> &S) {
    while (BinNodePosi<T> x = S.top()) {
        if (HasLChild(x)) {
            if (HasRChild(x)) {
                S.push(x->rc); // 若有右孩子, 优先入栈
            }
            S.push(x->lc);
        } else {
            S.push(x->rc); // 转向右分支
        }
    }
    S.pop(); // 返回之前，弹出栈顶的空节点
}

template<typename T, typename VST>
void travPost_I(BinNodePosi<T> x, V &visit) {
    Stack<BinNodePosi<T>> S;
    if (x) S.push(x); // 根节点最后访问
    while (!S.empty()) {
        if (S.top() != x->parent) {
            gotoLeftmostLeaf(S); // 寻找右兄子树中的左叶子
        }
        x = S.pop(); // 此时以 x 为根的子树仅剩 x 还未访问
        visit(x->data);
    }
}

表达式树

Expression Tree $\sim$ Postorder $\sim$ RPN

由 RPN 转表达式树：

从左至右依次遍历

操作数则形成叶子节点压入栈中

操作符则弹出相应数目节点组成子树，再入栈

层次遍历

实现

template<typename T, typename VST>
void BinNode<T>::travLevel(VST &visit) {
    // 使用辅助队列
    Queue<BinNodePosi<T>> Q; Q.enqueue(this);
    while (!Q.empty()) {
        BinNodePosi<T> x = Q.dequeue();
        visit(x->data);
        if (HasLChild(x)) Q.enqueue(x->lc);
        if (HasRChild(x)) Q.enqueue(x->rc);
    }
}

完全二叉树

叶节点仅限于最低两层
- $2^h \le n < 2^{h + 1}$
- 底层叶子，均居于次底层叶子左侧（相较于它们的 LCA）
- 除末节点的父亲，其余 内部节点 均有两个孩子
叶节点数目不致少于内部节点，且至多多出一个
此时考察层次遍历的迭代过程
- 前 $\left \lceil n / 2 \right \rceil - 1$ 步迭代中，均有右孩子入队
  
  前 $\left \lfloor n / 2 \right \rfloor$ 步迭代中，均有左孩子入队
  
  累计至少 $n-1$ 次入队
- 辅助队列规模先增后减，单峰且对称
  - 最大规模 = $\left \lceil n / 2 \right \rceil$ ，可能出现两次
一棵完全二叉树 = 根 + 一棵完全二叉（子）树 + 一棵满二叉（子）树
- 可借助向量结构，实现紧凑存储和高效访问

重构

由 [ 先序 | 后序 | 层次 ] + 中序可确定一棵树的形态
- 原理在于前者可以确定根，后者可以由根将左右子树区分开
由 [ 先序 + 后序 ] 则无法确定形态
- 但如果二叉树是真二叉树，则可以
在无法确定树的几何结构的情况下
- [ 后序 + 层次 ] 可以得出唯一的先序遍历序列
- [ 先序 + 后序 ] 可以得出唯一的层次遍历序列

增强序列

将每个 NULL 也看作真实节点，并在遍历时输出约定的元字符（如“^”）
- 可归纳证明，在增强的先序、后序遍历序列中
  - 任一子树依然对应一个子序列，并且
  - 其中 NULL 节点恰好比非 NULL 节点多一（ $n_0 = n_2 + 1$ ）
- 可以对增强序列分而治之，重构出原树
  - 但是增强的中序遍历序列无法重构
  - 增强的层次遍历序列可以重构

Huffman 编码树

二进制编码

组成数据文件的字符来自字符集 $\Sigma$
字符被赋予互异的二进制串

PFC 编码

Prefix-Free Code，为了避免某字符的编码恰是另一字符编码的前缀
二叉编码树
- $\Sigma$ 中的每个字符 $x$ ，对应于二叉树的叶节点 $v(x)$
- x 的编码串由根到 $v(x)$ 的通路决定，向左、向右分别对应 0、1
- 如此自然保证了 Prefix-Free
效率度量：平均编码长度
- $\text{ald}(T) = \sum_{x \in \Sigma} \text{depth}(v(x)) / \left\vert \Sigma \right\vert$

最优编码树

叶子只能出现在倒数两层以内——否则，通过节点交换一定可以更优
- 真完全树即为最优编码树

带权编码

各字符的期望频率已知，则
- 文件长度 $\propto$ 平均带权深度 $\text{wald}(T) = \sum_x rps(x) \times w(x)$
- 此时完全树 未必就是 最优编码树
最优带权编码树
- 仍具有双子性
- 频率高/低的字符，应尽可能放在高/低处
  - 通过适当交换，可以缩短 $\text{wald}(T)$
- 出现频率最低的字符 $x$ $x$ 和 $y$ $y$ ，必在某棵最优编码树中处于最底层，且互为兄弟
  - 否则，进行适当交换后， $\text{wald}$ 不致增加

Huffman 编码树

贪心策略

频率低的字符优先引入，其位置亦更低

为每个字符创建一棵单节点的树, 组成森林F
按照出现频率对所有树排序
while F中的树不止一棵
	取出频率最小的两棵树: T1, T2
	将他们合并成一棵新树T, 并令
		lc(T) = T1, rc(T) = T2
		w(root(T)) = w(root(T1)) + w(root(T2))

如此的贪心算法可以得到最优编码树之一
- 可由数学归纳证明

实现与改进

使用向量或列表， $O(n^2)$
使用优先级队列， $O(n\log n)$
使用预排序 + 栈 + 队列， $O(n\log n)$ $O (n lo g n)$
- 所有字符按频率非升序入栈（也可使用队列）
- 维护另一队列有序， $O(n)$
- 过程类似于二路归并

二叉搜索树

概述

向量、列表并不能兼顾静态查找与动态修改
综合二者优点，各数据项依所持关键码而彼此区分
- call-by-key
- 关键码之间必须支持比较（大小）和比对（相等）（全序）
二叉搜索树
- 顺序性：任一节点均不小/大于其左/右后代
- BST 的中序遍历序列，必然单调非降

算法及实现

查找

从根节点出发，逐步地缩小查找范围，直到
- 发现目标（成功），或抵达空树（失败）
- 整个过程仿效有序向量的二分查找

template<typename T> BinNodePosi<T>& BST::search(const T &e) {
    if (!_root || e == _root->data) {
        _hot = NULL; return _root;
    }
    for (_hot = _root; ; ) {
        BinNodePosi<T> &v = (e < _hot->data) ? _hot->lc : _hot->rc;
        if (!v || e == v->data) return v;
        _hot = v;
    }
} // 无论命中或失败, _hot 均指向 v 之父亲(v 是根时, hot 为 NULL)

可将失败的情况假想为，将该空节点转换为一个数值为 $e$ 的哨兵节点（随后可视需要进行修改）

插入

template<typename T> BinNodePosi<T> BST::<T>insert(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (x) return x; // 简化, 禁止词条关键码相等(实际不必要)
    x = new BinNode<T>(e, _hot); // _hot 为父亲
    _size++; x->updateHeightAbove();
    return x;
}

时间主要消耗于 search(e) 和 updateHeightAbove(x)
- 均线性正比于 $x$ 的深度，不超过树高

删除

template<typename T> bool BST<T>::remove(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (!x) return false;
    removeAt(x, _hot); // 分两类情况进行删除
    _size--; _hot->updateHeightAbove();
    return true;
} // 累计时间也为 O(h)

单分支
- 若 $x$ $x$ 的某一子树为空，则可 直接替换 为另一棵子树
  - 如此操作后，仍然满足 BST 的拓扑结构和顺序性
双分支
- 若 $x$ $x$ 左右孩子并存
  - 则找到 $x$ 的后继 w = x.succ()
  - 交换 $x$ 和 $w$ ，问题转化为删除 $w$ （必无左孩子）

template<typename T> static BinNodePosi<T> removeAt(BinNodePosi<T> &x, BinNodePosi<T> hot) {
    BinNodePosi<T> w = x, succ = NULL;
    if (!HasLChild(x)) succ = x = x->rc;
    else if (!HasRChild(x)) succ = x = x->lc;
    else {
        w = w->succ(); swap(x->data, w->data);
        BinNodePosi<T> u = w->parent;
        (u == x ? u->rc : u->lc) = succ = w->rc;
        // u 可能就是 x
    }
    hot = x->parent;
    if (succ) succ->parent = hot;
    delete w; return succ;
}

平衡

BST 的主要接口 search() 、insert() 、remove() 在最坏情况下，均线性正比于树高 $O(h)$ $O (h)$
- 若不能有效地控制树高，最（较）坏情况下 BST 将会退化为列表
随机生成分析
- $n$ 个词条 $\{e_1, e_2, \dots, e_n\}$ 按随机排列 $\sigma = \{e_{i1}, e_{i2}, \dots, e_{in}\}$
- 若各排列出现的概率均等，则 BST 平均高度为 $\Theta(\log n)$
- 计入 remove() ，则可通过随机使用 succ() 和 pred() ，避免逐渐倾侧
随机组成分析
- $n$ 个互异节点，在遵循顺序性的前提下，随机确定它们之间的 拓扑联接
- 由 $n$ $n$ 个互异节点随机组成的 BST，共计 $S(n)$ $S (n)$ 棵
  - $S(n) = \sum_{k = 1}^n S(k - 1) \cdot S(n - k) = \text{catalan}(n) = \frac{(2n)!}{n! \cdot (n + 1)!}$
- 假定所有 BST 等概率出现，则平均高度为 $\Theta(\sqrt{n})$ $Θ (n)$
  - 在 Huffman 编码等应用中，二叉树的确是逐渐拼合而成的

理想平衡

由 $n$ $n$ 个节点组成的二叉树，高度不致低于 $\left\lfloor \log_2 n \right\rfloor$ $⌊ lo g_{2} n ⌋$
- 达到这一下界时，为理想平衡
- 大致相当于完全二叉树甚至满树
维护成本过高
- 高度渐进地不超过 $O(\log n)$ ，即可接受
- 渐进平衡的 BST，简称为平衡二叉搜索树 BBST

等价变换

等价 BST
- 中序遍历序列相同
- 上下可变：联接关系不尽相同
- 左右不乱：保持中序遍历序列的单调非降
各种 BBST 都可视为 BST 的某一子集，相应地满足各自设计的 限制条件
- 单次动态修改后，至多 $O(\log n)$ 处局部不再满足限制条件（可能相继而非同时违反）
- 可在 $O(\log n)$ 时间内，使这些局部乃至全树重新满足

旋转调整

刚刚失衡的 BBST，必可迅速转换为一棵等价的 BBST
- 为此只需 $O(\log n)$ $O (lo g n)$ 甚至 $O(1)$ $O (1)$ 次旋转
  - 旋转可在常数时间内完成

实际上，经过不超过 $O(n)$ $O (n)$ 次旋转，等价的 BST 均可互相转化
- 规模为 $n$ $n$ 的任何 BST ，经过不超过 $n - 1$ $n - 1$ 次旋转调整，都可等价变换为向左倾斜的单链
  - 考虑 BST 的最左侧通路，从该通路的末端节点 $L_d$ $L_{d}$ 开始逐步迭代地延长该路径，直至不能继续延长
    - 若 $L_d$ 右子树不为空，则进行 zag 调整，否则上升至父节点继续
  - 任一节点需要通过旋转归入最左侧通路，当且仅当它最初不在该通路上

AVL 树

渐进平衡

平衡因子 $balFac(v) = height(lc(v)) - height(rc(v))$ $b a l F a c (v) = h e i g h t (l c (v)) - h e i g h t (r c (v))$
- $\forall v \in \text{AVL}, \, \left\vert balFac(v) \right\vert \le 1$
高度为 $h$ $h$ 的 AVL 树，至少包含 $S(h) = fib(h + 3) - 1$ $S (h) = f i b (h + 3) - 1$ 个节点
- $S(h) = 1 + S(h - 1) + S(h - 2)$
- 反过来，由 $n$ 个节点构成的 AVL 树，高度不超过 $O(\log n)$
- 高度为 $h$ 的 AVL 树中，任一叶节点的深度不小于 $\lceil h / 2 \rceil$

失衡和恢复

按 BST 规则动态修改后，AVL 平衡性可能被破坏（只涉及祖先）
- 插入：从祖父开始，每个祖先都可能失衡，且可能同时
- 删除：从父亲开始，每个祖先都可能失衡，但 至多一个
借助等价变换进行重平衡
- 所有旋转都在局部进行，每次 $O(1)$
- 每个深度只需检查并旋转至多一次，共 $O(\log n)$

插入

黄色节点恰好存在其一
可能有多个失衡节点，最低者 $g$ $g$ 不低于 $x$ $x$ 的祖父
- $g$ 经单旋调整后恢复平衡，子树 高度复原
- 更高祖先也必平衡，全树复衡
逐层上溯，即可找到 $g$ $g$
- p = tallerChild(g) ，v = tallerChild(p)
p、v 方向一致则单旋，否则双旋，至多 $O(1)$ 次调整

template<typename T> BinNodePosi<T> AVL<T>::insert(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (x) return x;
    BinNodePosi<T> xx = x = new BinNode<T>(e, _hot); _size++;
    for (BinNodePosi<T> g = _hot; g; g->updateHeight(), g = g->parent) {
        if (!AvlBalanced(g)) {
            rotateAt(tallerChild(tallerChild(g)));
            break;
        }
    }
}

删除

黄色节点至少存在其一，红色节点可有可无
瞬时至多一个失衡节点 $g$ $g$ ，可能就是 $x$ $x$ 的父亲 _hot
- 复衡后子树高度 未必复原
- 故失衡可能持续向上传播，最多需要做 $O(\log n)$ 次调整
逐层上溯，找到 $g$ $g$
- p = tallerChild(g) ，v = tallerChild(p)
p、v 方向一致则单旋，否则双旋

template<typename T> bool AVL<T>::remove(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (!x) return false;
    removeAt(x, _hot); _size--;
    for (BinNodePosi<T> g = _hot; g; g->updateHeight(), g = g->parent) {
        if (!AvlBalanced(g)) { // 一直检查到根
            rotateAt(tallerChild(tallerChild(g)));
        }
    }
    return true;
}

(3+4)-重构

设 $g$ 为最低的失衡节点，沿 最长分支 考察祖孙三代 $g \sim p \sim v$

按中序遍历次序，重命名为 $a < b < c$
四棵子树（可能空），按中序遍历次序，重命名为 $T_0 < T_1 < T_2 < T_3$
将原先以 $g$ 为根的子树，替换为以 $b$ 为根的新子树

等价代换，保持中序遍历次序 $ T_0 < a < T_1 < b < T_2 < c < T_3$

template<typename T> BinNodePosi<T> BST<T>::connect34(
	BinNodePosi<T> a, BinNodePosi<T> b, BinNodePosi<T> c,
    BinNodePosi<T> T0, BinNodePosi<T> T1, 
    BinNodePosi<T> T2, BinNodePosi<T> T3
) {
    a->lc = T0; if (T0) T0->parent = a;
    a->rc = T1; if (T1) T1->parent = a;
    c->lc = T2; if (T2) T2->parent = c;
    c->rc = T3; if (T3) T3->parent = c;
    b->lc = a, a->parent = b; b->rc = c, c->parent = b;
    a->updateHeight(); c->updateHeight(); b->updateHeight(); return b;
}

视 p、v 的拐向，无非四种情况

template<typename T> BinNodePosi<T> BST<T>::rotateAt(BinNodePosi<T> v) {
    BinNodePosi<T> p = v->parent; int TurnV = IsRChild(v);
    BinNodePosi<T> g = p->parent; int TurnP = IsRChild(p);
    BinNodePosi<T> r = (TurnP == TurnV) ? p : v; // 子树新根节点
    (FromParentTo(g) = r)->parent = g->parent;
    switch((TurnP << 1) | TurnV) {
        case 0b00: return connect34(v, p, g, v->lc, v->rc, p->rc, g->rc);
        case 0b01: return connect34(p, v, g, p->lc, v->lc, v->rc, g->rc);
        case 0b10: return connect34(g, v, p, g->lc, v->lc, v->rc, p->rc);
        default: return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
    }
}

总结

优点
- 无论查找、插入或删除，最坏情况下的复杂度均为 $O(\log n)$ $O (lo g n)$
  - 存储空间 $O(n)$
缺点
- 借助高度或平衡因子，为此需改造元素结构，或额外封装
- 实测复杂度与理论值尚有差距
  - 插入/删除后的旋转，成本不菲
  - 删除操作后，最多旋转 $\Omega(\log n)$ 次（平均仅 0.21 次）
- 单次动态调整后，全树 拓扑结构的变化量 可能高达 $\Omega(\log n)$

高级搜索树

伸展树

局部性：刚被访问过的数据，极有可能很快地再次被访问
BST 的局部性
- 时间：刚被访问过的节点，极有可能很快地再次被访问
- 空间：下一将要访问的节点，极有可能就在刚被访问过节点的附近
对于 AVL 的连续 $m \gg n$ $m ≫ n$ 次查找，共需 $O(m\log n)$ $O (m lo g n)$
- 利用局部性加速：BST 的节点一旦被访问，随即调整到树根

单层伸展

节点 v 一旦被访问，随即被推送至根
- 自下而上，逐层旋转
旋转次数呈周期性的算术级数（周期访问所有节点）
- 每一周期结构会复原，累计 $\Omega(n^2)$ ，分摊 $\Omega(n)$

双层伸展

反复考察祖孙三代
- g = parent(p), p = parent(v), v
- 根据他们的相对位置，经 两次旋转，使 v 上升两层，成为子树根
  - zig-zag 操作本身就是平衡的，效果很好
  - 对于 zig-zig，先 p 后 g 只会拉长和移动访问路径，无法改善树的整体结构；而先 g 后 p 则能够“折叠”和“打散”访问路径
- zig 和 zag 不同组合，共计 4 种
  - 可能会在最后进行一次单次旋转
节点访问之后，对应路径的长度随即折半
- 最坏情况显然 $O(n)$ $O (n)$ ，但最坏情况不致持续发生
  - 分摊仅需 $O(\log n)$

算法实现

template<typename T> BinNodeposi<T> Splay<T>::splay(BinNodePosi<T> v) {
    BinNodePosi<T> p, q;
    while ((p = v->parent) && (g = p->parent)) {
        BinNodePosi<T> gg = g->parent;
        switch ((IsLChild(p) << 1) | IsLChild(v)) {
            case 0b00: /* zig-zig */;
            case 0b01: /* zig-zag */;
            case 0b10: /* zag-zig */;
            default:   /* zag-zag */;
        }
        if (!gg) v->parent = NULL;
        else (g == gg->lc) ? gg->attachLc(v) : gg->attachRc(v);
        g->updateHeight(); p->updateHeight(); v->updateHeight();
    }
    if (p = v->parent) {
        if (IsLChild(v)) { // zig
            p->attachLc(v->rc);
            v->attachRc(p);
        } else { // zag
            p->attachRc(v->lc);
            v->attachLc(p);
        }
        p->updateHeight(); v->updateHeight();
    }
    v->parent = NULL; return v; // 伸展完成, v 抵达树根
}

查找

与常规 BST::search() 不同，很可能会改变树的拓扑结构， 不再属于静态操作

template<typename T> BinNodePosi<T>& Splay<T>::search(const T &e) {
    BinNodePosi<T> p = BST<T>::search(e);
    _root = p ? splay(p) : _hot ? splay(_hot) : NULL; // 成功、失败、空树
    return _root;
}

插入

Splay::search() 查找失败后，_hot 即为根
- 直接在树根附近接入新节点

template<typename T> BinNodePosi<T> Splay<T>::insert(T const &e) {
    if (_root) { _size = 1; return _root = new BinNode<T>(e); }
    BinNodePosi<T> t = search(e);
    if (t->data == e) return t;
    if (t->data < e) {
        _root = new BinNode<T>(e, NULL, t, t->rc);
        t->rc = NULL;
    } else {
        _root = new BinNode<T>(e, NULL, t->lc, t);
        t->lc = NULL;
    }
    _size++; t->updateHeightAbove(); return _root;
} // 无论何时, 总有 _root-> data == e

删除

同插入，search() 后可直接在树根附近摘除节点

template<typename T> bool Splay<T>::remove(T const &e) {
    if (!root || e != search(e)->data) return false;
    BinNodePosi<T> L = _root->lc, R = _root->rc;
    delete _root;
    if (!R) {
        if (L) L->parent = NULL;
        _root = L;
    } else {
        _root = R; R->parent = NULL;
        search(e); // 查找必败, 是为了伸展最小节点作为新的根
        _root->attachLc(L);
    }
    _size--; if (_root) _root->updateHeight();
    return true;
}

总结

无需记录高度或平衡因子，编程实现简单，分摊复杂度 $O(\log n)$
局部性强，缓存命中率极高时（ $k \ll n \ll m$ $k ≪ n ≪ m$ ）（ $k$ $k$ 为访问范围）
- 效率甚至可以更高，自适应的 $O(\log k)$
- 任何连续的 $m$ 次查找，仅需 $O(m\log k + n\log n)$
若 反复地顺序 访问任意子集，分摊成本仅为常数
不能杜绝 单次最坏 情况，不适用于对效率敏感的场合

分摊分析

势能

任何一棵伸展树在任何时刻，都可假想地视作具有势能
- $\Phi(S) = \log(\prod_{v \in S} size(v)) = \sum_{v \in S} \log(size(v)) = \sum_{v \in S} rank(v) = \sum_{v \in S} \log V$
越平衡/倾侧的树，势能越小/大
- 单链
  
  $\Phi(S) = \log n! = O(n \log n)$
- 满树
  
  $\begin{aligned}\Phi(S) &= \log \prod_{d = 0}^h (2^{h - d + 1} - 1)^{2^d} \le \log \prod_{d = 0}^k 2^{(h - d + 1) \cdot 2^d} \\ &= \sum_{d = 0}^h (h - d + 1) \cdot 2^d = (h + 1) \cdot (2^{h + 1} - 1) - [(h - 1)\cdot 2^{h + 1} + 2] \\ &= 2^{h + 2} - h - 3 = O(n) \end{aligned}$

总体关系推导

考察对伸展树 $S$ 的 $m \gg n$ 次连续访问（不妨仅考察 search() ）
记 $A^{(k)} = T^{(k)} + \Delta \Phi^{(k)}$ $A^{(k)} = T^{(k)} + Δ Φ^{(k)}$ ，其中
- $T^{(k)}$ ：第 $k$ 次操作的实际时间复杂度
- $\Delta \Phi^{(k)} = \Phi_{after} - \Phi_{before}$ ：第 $k$ 次操作后势能函数的变化
则有 $T = \sum_{k = 1}^m T^{(k)} = \sum_{k = 1}^m (A^{(k)} - \Delta \Phi^{(k)}) = A - \Delta \Phi$ $T = \sum_{k = 1}^{m} T^{(k)} = \sum_{k = 1}^{m} (A^{(k)} - Δ Φ^{(k)}) = A - Δ Φ$
- 其中 $\left\vert \Delta\Phi \right\vert \le O(n \log n)$
- 故 $T = A \pm O(n \log n)$
$T^{(k)}$ $T^{(k)}$ 的变化幅度可能很大，但可以证明 $A^{(k)}$ $A^{(k)}$ 都不致超过节点 $v$ $v$ 的势能变化量
- $A^{(k)} = O(rank^{(k)}(v) - rank^{(k - 1)}(v)) = O(\log n)$

伸展操作分析

单旋到根（zig / zag）

$\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 1 + \Delta rank_i(v) + \Delta rank_i(r) \\ &= 1 + [rank_i(v) - rank_{i - 1}(v)] + [rank_i(r) - rank_{i - 1}(r)] \\ &< 1 + [rank_i(v) - rank_{i - 1}(v)] \end{aligned}$

反向双旋（zig-zag / zag-zig）， $(\log G_i + \log P_i) / 2\le \log ((G_i + P_i) / 2) < \log (V_i / 2)$

$\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 2 + \Delta rank_i(g) + \Delta rank_i(p) + \Delta rank_i(v) \\ &= 2 + [rank_i(g) - \cancel{rank_{i - 1}(g)}] + [rank_i(p) - rank_{i - 1}(p)] + [\cancel{rank_i(v)} - rank_{i - 1}(v)] \\ &< 2 + rank_i(g) + rank_i(p) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + 2 \cdot rank_i(v) - 2 - 2 \cdot rank_{i - 1}(v) \\ &= 2 \cdot(rank_i(v) - rank_{i - 1}(v)) \end{aligned}$

同向双旋（zig-zig / zag-zag）， $(\log G_i + \log V_{i - 1}) / 2 \le \log ((G_i + V_{i - 1}) / 2) < \log (V_i / 2)$

$\begin{aligned} A^{(k)}_i &= T^{(k)}_i + \Delta\Phi^{(k)}_i = 2 + \Delta rank_i(g) + \Delta rank_i(p) + \Delta rank_i(v) \\ &= 2 + [rank_i(g) - \cancel{rank_{i - 1}(g)}] + [rank_i(p) - rank_{i - 1}(p)] + [\cancel{rank_i(v)} - rank_{i - 1}(v)] \\ &< 2 + rank_i(g) + rank_i(p) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + rank_i(g) + rank_i(v) - 2 \cdot rank_{i - 1}(v) \\ &< 2 + 2 \cdot rank_i(v) - rank_{i - 1}(v) - 2 + rank_i(v) - 2 \cdot rank_{i - 1}(v) \\ &= 3 \cdot(rank_i(v) - rank_{i - 1}(v)) \end{aligned}$
单次伸展总复杂度为

$\begin{aligned} A^{(k)} &= \sum_i A^{(k)}_i \le 3 \cdot \sum_i (rank_i(v) - rank_{i - 1}(v)) \\ &= 3 \cdot (rank(root) - rank(v)) \le 3 \cdot \log n = O(\log n) \end{aligned}$

B-树

分级存储：利用数据访问的局部性
- 常用的数据，复制到更高层、更小的存储器中
- 找不到，才向更低层、更大的存储器索取

缓存的体现：就地循环位移的倒置版本

void shift(int *A, int n, int k) {
    reverse(A, k);
    reverse(A + k, n - k);
    reverse(A, n);
} // O(3n)

结构

等价变换：平衡的多路搜索树
- 每 $d$ $d$ 代合并为超级节点
  - $m = 2^d$ 路， $m - 1$ 个关键码
- 逻辑上与 BBST 完全等价
IO 优化：多级存储系统中使用 B-树，可针对外部查找，大大减少 I/O 次数
- 利用外存的 批量访问，每下降一层，都以超级节点为单位，读入一组关键码
  - 适宜于在相对更小的内存中，实现对大规模数据的高效操作
- $m = \left\vert page \right\vert / \left\vert key \right\vert$

外部节点+叶子

$m$ 阶 B-树，即为 $m$ 路完全平衡搜索树（ $m \ge 3$ ）
外部节点的深度 统一相等，并以此深度作为树高 $h$ $h$
- 外部节点可看作 “可被插入的空隙”
- 叶节点的深度统一相等（ $h - 1$ ）

内部节点

各含有 $n \le m - 1$ 个关键码
各有 $n + 1 \le m$ $n + 1 \leq m$ 个分支
- 反过来，分支数也不能太少
  - 树根： $2 \le n + 1$
  - 其余： $\lceil m / 2 \rceil \le n + 1 \le m$
- 故亦称作 $(\lceil m / 2 \rceil, m)$ -树

查找

算法

从（常驻 RAM 的）根节点开始
只要当前节点不是外部节点
- 在当前节点中顺序查找（RAM 内部）
- 若找到目标关键码，则返回查找成功
- 否则，沿引用找到孩子节点，将其 读入内存
  - 外部节点不需要 IO
返回查找失败

实现

template<typename T> BTNodePosi<T> BTree<T>::search(T const &e) {
    _hot = NULL;
    for (BTNodePosi<T> v = _root; v; ) {
        Rank r = v->key.search(e); // 在当前节点中, 找到不大于 e 的最大关键码
        // 对通常的_m, 顺序查找效率比二分高
        if (r != -1 && (e == v->key[r])) return v;
        _hot = v; v = v->child[r + 1]; // 沿引用转至对应的孩子节点(I/O)
    }
    return NULL;
}

性能

忽略内存中的查找，运行时间主要取决于 I/O 次数
在每一深度至多一次 I/O，故运行时间为 $O(\log n)$
$\log_m (N + 1) \le h \le 1 + \lfloor \log_{\lceil m / 2 \rceil} \frac{N + 1}{2} \rfloor$ $lo g_{m} (N + 1) \leq h \leq 1 + ⌊ lo g_{⌈ m / 2 ⌉} \frac{N + 1}{2} ⌋$
- 树最高的情况
  - 对于内部节点， $n_k \ge 2 \times \lceil m / 2 \rceil ^{k - 1}, \quad \forall k > 0$
  - 考察外部节点所在高度 $h$ ， $N + 1 = n_h \ge 2 \times \lceil m / 2 \rceil ^{h - 1}$
  - $h \le 1 + \lfloor \log_{\lceil m / 2 \rceil} \frac{N + 1}{2} \rfloor = O(\log_m N)$

插入

template<typename T> bool BTree<T>::insert(const T &e) {
    BTNodePosi<T> v = search(e);
    if (v) return false;
    Rank r = _hot->key.search(e); // 在_hot 节点(叶子)中确定插入位置
    _hot->key.insert(r + 1, e);
    _hot->child.insert(r + 2, NULL); // 创建一个空子树
    _size++; solveOverflow(_hot); // 若上溢, 则分裂
    return true;
}

上溢修复

设上溢节点中的关键码依次为 $\{k_0, k_1, \dots, k_{m - 1}\}$ ${k_{0}, k_{1}, \dots, k_{m - 1}}$
- 取中位数 $s = \lfloor m / 2 \rfloor$ ，划分为 $\{k_0, \dots, k_{s - 1}\}$ 、 $\{k_s\}$ 、 $\{k_{s + 1}, \dots, k_{m - 1}\}$
- 关键码分裂， $k_s$ 上升成为父节点的孩子，其余两部分成为它的左、右孩子
- 此时左、右孩子的关键码数目，均满足 $m$ 阶 B-树条件
若父节点本已饱和，则继续上溢
- 最坏情况 上溢持续 向上传播到根
  - 此时可令最后被提升的关键码自成节点，作为新的根
  - B-树因此增高
总体执行时间正比于分裂次数， $O(h)$
上溢也可采用旋转来修复

template<typename T> void BTree<T>::solveOverflow(BTNodePosi<T> v) {
    while (_m <= v->key.size()) {
        Rank s = _m / 2;
        BTNodePosi<T> u = new BTNode<T>();
        for (Rank j = 0; j < _m - s - 1; j++) {
            // 分裂出右侧节点 u
            u->child.insert(j, v->child.remove(s + 1));
            u->key.insert(j, v->key.remove(s + 1));
        }
        u->child.insert[_m - s - 1] = v->child.remove(s + 1); // 此时 v 最靠右的孩子
        if (u->child[0]) {
            for (Rank j = 0; j < _m - s; j++)
                u->child[j]->parent = u;
        }
        BTNodePosi<T> p = v->parent;
        if (!p) {
            _root = p = new BTNode<T>();
            p->child[0] = v, v->parent = p;
        }
        Rank r = 1 + p->key.search(v->key[0]); // p 中指向 u 的节点的指针的秩
        p->key.insert(r, v->key.remove(s));
        p->child.insert(r + 1, u); u->parent = p;
        v = p; // 如有必要继续分裂
    }
}

一棵存有 $N$ 个关键码的 $m$ 阶 B-树插入特定关键码后，引发 $\Theta(\log_m N)$ 次分裂的情况：

全树总规模为 $\hat{N} = \lceil m / 2 \rceil^{h - 1} + (m - 1) \cdot (\lceil m / 2 \rceil ^{h - 2} + \lceil m / 2 \rceil^{h-3} + \dots + \lceil m / 2 \rceil^{0})$ $\hat{N} = ⌈ m / 2 ⌉^{h - 1} + (m - 1) \cdot (⌈ m / 2 ⌉^{h - 2} + ⌈ m / 2 ⌉^{h - 3} + \dots + ⌈ m / 2 ⌉^{0})$
- 对应高度可取为 $\begin{aligned}h = 1 + \log_{\lceil m / 2 \rceil}((\hat{N} \cdot (\lceil m / 2 \rceil - 1) + m - 1) / (m + \lceil m / 2 \rceil - 2)) =\Theta(\log_{\lceil m / 2 \rceil} \hat{N}) = \Theta(\log_{m} \hat{N})\end{aligned}$
- 对于给定的 $N$ ，可由代入上式计算出 $h$ 进而估算出 $\hat{N} \le N$ （多余的关键码散布至其他子树中）

PixPin_2025-12-03_16-32-29

图示某一黑关键码和对应白关键码构成的高度为 $k$ 的子树规模为 $\lceil m / 2 \rceil^k$

删除

若被删除元素非叶子，则先通过旋转腾挪（与后继交换），使其位于最底层

template<typename T> bool BTree<T>::remove(const T &e) {
    BTNodePosi<T> v = search(e);
    if (!v) return false;
    Rank r = v->key.search(e);
    if (v->child[0]) { //非叶子
    	BTNodePosi<T> u = v->child[r + 1]; // 后继在右子树中
        while (u->child[0]) u = u->child[0];
        v->key[r] = u->key[0]; v = u, r = 0; // 交换
    }
    v->key.remove(r); v->child.remove(r + 1);
    _size--; solveUnderflow(); // 下溢, 需做旋转或合并
    return true;
}

下溢修复

非根节点 $v$ $v$ 下溢时，必恰有 $\lceil m / 2 \rceil - 2$ $⌈ m / 2 ⌉ - 2$ 个关键码和 $\lceil m / 2 \rceil - 1$ $⌈ m / 2 ⌉ - 1$ 个分支
- 若左兄弟 L 存在，且至少包含 $\lceil m / 2 \rceil$ $⌈ m / 2 ⌉$ 个关键码（够借）
  - 将 P 中分界关键码 $y$ 移至 V 中（作为最小关键码）
  - 将 L 中最大关键码 $x$ 移至 P 中（取代 $y$ ）
  - 修复完成
- 若右兄弟 R 存在，且至少包含 $\lceil m / 2 \rceil$ $⌈ m / 2 ⌉$ 个关键码
  - 同上处理
- 若 L 和 R 或不存在，或均不足 $\lceil m / 2\rceil$ $⌈ m / 2 ⌉$ 个关键码
  - 即便如此 L 和 R 必有其一，且恰含有 $\lceil m / 2 \rceil -1$ 个关键码
  - 从 P 中抽出介于 L（R）和 V 之间的关键码 $y$ ，三者合成一个新的节点，同时合并此前 $y$ 的孩子引用
  - 这可能导致 P 继续下溢，重复整个过程即可

template<typename T> void BTree<T>::solveUnderflow(BTNodePosi<T> v) {
    while ((_m + 1) / 2 > v->child.size()) {
        BTNodePosi<T> p = v->parent;
        if (!p) { /* 已到根节点 */ }
        Rank r = 0; while (p->child[r] != v) r++; // 确定 v 是 p 的第 r 个孩子
        if (r > 0 && (_m + 1) / 2 < p->child[r - 1]->child.size()) {
            /* 情况 1 */
        } else if (r < p->child.size() - 1 && (_m + 1) / 2 < p->child[r + 1]->child.size()) {
            /* 情况 2 */
        } else { /* 情况 3 */
            if (r > 0) { /* 与左兄弟合并 */ }
            else { /* 与右兄弟合并 */ }
        }
        v = p; // 如有必要继续旋转或合并
    }
}

红黑树

动机

并发性：对于 BST 而言，结构变化处需要加锁（产生访问延迟）
- Splay 结构变化剧烈，最差 $O(n)$
- AVL 插入 $O(1)$ 但删除 $O(\log n)$
持久性：支持对历史版本的访问
- 蛮力保存，单次操作 $O(\log h + \log n)$ ，累计 $O(n \cdot h)$ 时间/空间
- 压缩更新：大量共享，少量更新（仅支持对历史版本的读取）
  - 每个版本的新增复杂度，仅为 $O(\log n)$
  - 可进一步提高至总体 $O(n + h)$ $O (n + h)$ 、单版本 $O(1)$ $O (1)$
    - 为此，就树的 代数结构 而言，相邻版本之间的差异不能超过 $O(1)$

结构

红黑树：由红、黑两类节点组成的 BST；统一引入外部节点 NULL，形成 真二叉树。规则如下
- 树根：必为黑色
- 外部节点：必为黑色
- 红节点：只能有黑孩子以及黑父亲
- 外部节点：黑深度（黑的真祖先数目）相等
  - 亦即根（全树）的黑高度
  - 子树的黑高度，即为后代 NULL 的相对黑深度
红黑树 = （2,4）B-树
- 将红节点提升至与其黑父亲等高，则可对应一棵 $(2, 4)$ $(2, 4)$ -树
  - 将黑节点和其红孩子视作关键码，合并为 B-树的超级节点
红黑树 $\in$ BBST
- 设红/黑高度为 R/H，则
  - $H \le h \le H + R \le 2 \cdot H$
  - $H$ $H$ 即为对应 B-树 $T_B$ $T_{B}$ 的树高，而 $T_B$ $T_{B}$ 中的每个节点都恰好包含一个 $T$ $T$ 的黑节点
    - $H \le 1 + \log_{\lceil m / 2 \rceil} \frac{n + 1}{2} = \log_2(n + 1)$
- 包含 $n$ 个内部节点的红黑树，高度 $h = O(\log n)$
  - $\log_2(n + 1) \le h \le 2 \cdot \log_2(n + 1)$
  - 若 $h$ 为偶数，则对应 B-树高度至少为 $h / 2$
    - 至少包含 $N_{\min} = 2 \times (1 + 2 + 4 + \dots + 2^{h / 2 - 1}) = 2^{h / 2 + 1} - 2$ 个节点
      
      故 $h_{\max} = 2 \times (\lfloor \log_2(N + 2) \rfloor - 1)$
  - 若 $h$ 为奇数，则对应 B-树高度至少为 $(h + 1) / 2$
    - 至少包含 $N_{\min} = 2 \times (1 + 2 + 4 + \dots + 2^{(h - 1) / 2 - 1}) + 2^{(h + 1) / 2 - 1} = 3 \cdot 2^{(h - 1) / 2} - 2$ 个节点
      
      故 $h_{\max} = 2 \times \lfloor \log_2 (\frac{N + 2}{3}) \rfloor + 1$

插入

按 BST 规则插入新关键码 $e$ $e$
- 除非是首个节点，否则 $x$ 的父亲 $p$ 必存在
- 先将 $x$ 染红，条件 1、2、4 依然满足
- 但可能出现双红，此时考查
  - 祖父 g = p->parent 必存在且为黑
  - 叔父 u = uncle(x) = sibling(p) ，无非两种情况

template<typename T> BinNodePosi<T> RedBlack<T>::insert(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (x) return x;
    // 创建红节点 x, 以_hot 为父, 黑高度 = 0
    x = new BinNode<T>(e, _hot, NULL, NULL, 0); _size++;
    BinNodePosi<T> xOld = x;
    solveDoubleRed(x); return xOld;
}

双红修正

RR-1: `u->color = B`

此时，x、p、g 的四个孩子（可能是外部节点）全黑，且黑高度相同
可进行局部“3+4”重构，b 转黑，a 或 c 转红
- 从 B-树的角度，相当于原三叉节点插入红关键码后，原黑关键码不再居中

RR-2: `u->color = R`

等效于在 B-树中，超级节点发生上溢
故可以让 p 和 u 转黑，g 转红
- 等效于 节点分裂，关键码 g 上升一层
- 所以可能将双红向上传播
  - 继续如法炮制即可
  - 直至不再双红，或抵达树根（整树黑高度+1）

复杂度

重构、染色均只需常数时间
故 RedBlack::insert() 仅需 $O(\log n)$ $O (lo g n)$ 时间
- 期间至多 $O(\log n)$ 次重染色、 $O(1)$ 次旋转
- 分摊意义下，重染色次数为 $O(1)$

	旋转	染色	此后
u 为黑	1~2	2	调整随即完成
u 为红	0	3	可能再次双红，但必上升两层

删除

首先按 BST 常规算法进行删除 r = removeAt(x, _hot)
- 实际被摘除的可能是 x 的前驱或者后继
x 由其孩子 r 接替，此时另一孩子 k 必为 NULL
- 但实际调整过程中，x 可能逐层上升
- 故等效地理解为，k 是一棵 黑高度 与 r 相等的子树

此时条件 1、2 依然满足，但条件 3、4 未必
- 其一为红
  - 若 x 为红，则 3、4 自然满足
  - 若 r 为红，则令其与 x 交换颜色 即可
- 若 x 和 r 均黑，则此时全树黑深度不再统一
  - 等效于 B-树中 x 所属节点发生下溢
  - 在新树中，考查 r 的父亲，兄弟
    1
    2
    p = r->parent;
    s = sibling(r);
    无非四种情况，分别处理

template<typename T> bool RedBlack<T>::remove(const T &e) {
    BinNodePosi<T> &x = search(e);
    if (!x) return false;
    BinNodePosi<T> r = removeAt(x, _hot); // 删除_hot 的某孩子, r 指向其接替者
    if (!(--_size)) return true;
    if (!_hot) { // 删除的是根, 直接染黑
        _root->color = RB_BLACK; _root->updateHeight();
        return true;
    }
    if (BlackHeightUpdated(_hot)) return true;
    if (IsRed(r)) {
        r->color = RB_BLACK;
        r->height++; return true;
    }
    solveDoubleBlack(r); return true;
}

双黑修正

BB-1

s 为黑，且至少有一个红孩子 t
进行“3+4”重构，r 保持黑，a、c 染黑，b 继承 p 的原色
- 在 B-树中，等效于旋转修复下溢（够借）

BB-2R

s 为黑，且两个孩子均为黑；p 为红
r 保持黑，s 转红，p 转黑
- 等效于下溢节点与兄弟节点合并
- 同时因为 p 左右还有黑关键码，不会导致下溢传播

BB-2B

s 为黑，且两个孩子均为黑；p 为黑
r 保持黑，s 转红，p 转黑
- 也等效于下溢节点与兄弟节点合并
- 但合并前，p 和 s 均属于单关键码节点，故 父节点继续下溢
  - 继续处理即可，至多 $O(\log n)$ 步

BB-3

s 为红（其孩子均为黑）
绕 p 单旋，s 由红转黑，p 由黑转红
- 黑高度依然异常，但 r 有了新的（黑）兄弟
- 且由于 p 转红，接下来的情况变为 BB-1 或 BB-2R
- 再调整一轮，即可恢复
- 道理是“存在红色就可以在子树中腾挪”，但需要先调整一下形态
  - 想在红黑树的等效 B-树节点中交换节点颜色（即在 B-树中改变与上层节点的联接），需要进行旋转

复杂度

RedBlack<T>::remove 仅需 $O(\log n)$ $O (lo g n)$ 时间
- 期间至多 $O(\log n)$ 次重染色、 $O(1)$ 次旋转
- 分摊意义下，重染色次数为 $O(1)$

	旋转	染色	此后
（1）黑 s 有红子 t	1~2	3	调整随即完成
（2R）黑 s 无红子，p 红	0	2	调整随即完成
（2B）黑 s 无红子，p 黑	0	1	必再次双黑，但上升一层
（3）红 s	1	2	转为（1）或（2R）

词典

散列

循对象访问
- entry = (key, value)
- 关键码未必可定义大小（但可判等），查找对象不限于最大/最小词条

散列表/散列函数

桶（bucket）：直接存放或间接指向一个词条
- Bucket array $\sim$ $\sim$ Hash table
  - 容量： $\mathcal{M}$
  - 满足： $\mathcal{N} < \mathcal{M} \ll \mathcal{R}$ （所有可能的对象）
  - 空间： $\mathcal{O}(\mathcal{N} + \mathcal{M}) = \mathcal{O}(\mathcal{N})$
定址
- 根据词条的 key（未必可比较）， “直接”确定散列表入口 （无论表有多长）
  - 散列函数
    - hash(): $ key \rightarrow &entry$
    - 如 hash(key) = key % M
  - “直接”： $expected-O(1)$

冲突

同义词： $key_1 \ne key_2 \quad \text{but} \quad hash(key_1) = hash(key_2)$
装填因子 load factor $\sim$ 空间利用率 $\lambda = N / M$
- $\lambda$ $λ$ 越大/小
  - 空间利用率越高/低
  - 冲突的情况越严重/轻微
- 降低 $\lambda$ $λ$ ，冲突程度将会有所改善
  - 但只要数据集动态变化，就无法根除
完美散列：数据集已知且固定时，可实现完美散列
- 采用两级散列模式
- 仅需 $O(n)$ 空间
- 关键码之间互不冲突
- 最坏情况下的查找时间也不过 $O(1)$
基本任务
- 精心设计散列表及散列函数，尽可能降低冲突的概率
- 制定可行的预案，以便在发生冲突时，能够尽快予以排解

散列函数

评价和设计原则
- 确定：同一关键码总是被映射至同一位置
- 快速： $expected-O(1)$
- 满射：尽可能充分利用整个散列空间
- 均匀：关键码映射到散列表各位置的概率尽量接近
  - 避免聚集现象

基本

除余法

$hash(key) = key \, \% \, M$ $h a s h (k e y) = k e y % M$
- 据说 $M$ $M$ 为素数时，数据对散列表的覆盖最充分，分布最均匀
  - 但对于理想随机的序列，表长是否素数，无关紧要
- 序列的 $\text{Kolmogorov}$ 复杂度：生成该序列的算法，最短可用多少行代码实现？
- 实际应用中的数据序列 远非理想随机
  - 面对往往具有周期的词条，将 散列表长 取作素数，可将聚集之概率降至最低

MAD 法

除余法的缺陷
- 不动点：无论表长 $M$ 取值如何，总有 $hash(0) \equiv 0$
- 相关性：虽然 $[0, R)$ 的关键码平均分配至 $M$ 个桶，但相邻关键码的散列地址也必相邻
Multiply-Add-Divide
- $hash(key) = (a \times key + b) \% M, \, M \, \text{prime}, a > 1, b > 0, M \nmid a$

平方取中/mid-square
折叠法
位异或法
总之，越是随机，越是 没有规律，越好

随机数

（伪）随机数法

径取： $hash(key) = rand(key) = [rand(0) \times a^{key}] \% M$
种子： $rand(0)$

unsigned long int next = 1;
void srand(unsigned int seed) { next = seed; }
int rand(void) {
    next = next * 1103515425 + 12345;
    return (unsigned int) (M / 65536) % 32768;
}

创建的散列表可移植性差

就地随机置乱

任给一个数组 $A[0, n)$ ，理想地将其中元素的次序随机打乱

void shuffle(int A[], int n) {
    for (; n > 1; n--)
        swap(A[rand() % M], A[n - 1]);
} // 20! < 2^64 < 21!

hashCode 与多项式法

static Rank hashCode(char s[]) {
    Rank n = strlen(s); Rank h = 0;
    for (Rank i = 0; i < n; i++) {
        h = (h << 5) | (h >> 27);
        h += s[i];
    }
    return h;
}

排解冲突

开放散列

多槽位

桶单元细分成若干槽位，存放（与同一单元）冲突的词条
只要槽位数目不太多，可以保证 $O(1)$ 的时间效率
但可能导致空间浪费，或极端情况下始终不够

独立链

每个桶拥有一个列表，存放对应的一组同义词
优点
- 无需为每个桶预备多个槽位
- 任意多次的冲突都可解决
缺点
- 耗费更多空间和时间
- 空间未必连续分布，缓存难以生效

两个结论

在 简单均匀 散列的假设下，对于使用 独立链 法解决冲突的散列表

一次不成功查找的平均时间为 $\Theta(1+\lambda)$

一次成功查找的平均时间为 $\Theta(1+\lambda)$

装填因子 $\lambda = \frac{n}{m}$ ，在简单均匀散列的假设下，意味着每条独立链的期望长度即为 $\lambda$

故一次不成功的查找平均要检查 $\lambda$ 个元素，总平均时间（包括计算 hash 的时间）为 $\Theta(1 + \lambda)$

而对于成功查找，考虑顺序插入的 $n$ 个关键字 $k_1, k_2, \dots, k_n$

根据简单均匀散列假设，任意两个关键字被插入同一链条的概率为 $\frac{1}{m}$

对于 $k_i$ ，其所在链条中排在 $k_i$ 之前的元素数量期望为 $\frac{n - i}{m}$

故总期望查找时间为 $\begin{aligned} \frac{1}{n}\sum_{i = 1}^n(1 + \frac{n - i}{m}) &= 1 + \frac{1}{nm} \sum_{i = 1}^n (n - i) \\ &= 1 + \frac{1}{nm}[n^2 - \frac{n(n + 1)}{2}] \\ &= 1 + \frac{n - 1}{2m} = 1 + \frac{\lambda}{2} - \frac{\lambda}{2n} \end{aligned}$

因此总平均时间（包括计算散列函数的时间）为 $\Theta(2 + \frac{\lambda}{2} - \frac{\lambda}{2n}) = \Theta(1 + \lambda)$

公共溢出区

单独开辟一块连续空间，发生冲突的词条，顺序存入此区域
结构简单易于实现
一旦发生冲突，最坏情况下，处理冲突的时间将正比于溢出区的规模

封闭散列

封闭散列：散列表的物理空间相对固定，所有冲突都在内部寻求解决
开放定址（ $\ne$ 开放散列）：只要有必要，任何散列桶都可以接纳任何词条
试探链（Probe Chain）：为每一组同义词，都 事先约定了若干备用桶，一次串接成序列/链
- 查找算法：沿试探链逐个检视，直到命中成功，或抵达空桶而失败
相对于开放散列，整体结构更加整饬，cache 机制易生效

给定一个装填因子 $\lambda = \frac{n}{m} < 1$ 的开放寻址散列表，假设是均匀散列且各关键字被查找可能性相同，则

一次不成功的查找，期望探查次数至多为 $\frac{1}{1 - \lambda}$

一次成功的查找，期望探查次数至多为 $\frac{1}{\lambda} \ln \frac{1}{1 - \lambda}$

在一次不成功的查找（最后一次槽为空）中，令 $X$ $X$ 为探查次数
- 对于 $i > 1$ ，在前 $i - 1$ 次探查都是已占用槽的前提下，第 $i$ 次探查且探查到的仍是占用槽的概率为 $\frac{n - i + 1}{m - i + 1}$
- 则 $\Pr\{X \ge i\} = \frac{n}{m} \cdot \frac{n - 1}{m - 1} \cdot \frac{n - 2}{m - 2} \cdots \frac{n - i + 2}{m - i + 2} \le (\frac{n}{m})^{i - 1}$
- $\begin{aligned}E[X] = \sum_{i=1}^\infty i \cdot \Pr\{X = i\} = \sum_{i = 1}^\infty \Pr\{X \ge i\} \le \sum_{i = 1}^\infty \lambda^{i - 1} = \frac{1}{1 -\lambda} \end{aligned}$
对第 $i + 1$ $i + 1$ 个被插入表中的关键字 $k$ $k$ 的一次查找，探查的期望次数至多为 $\frac{1}{1 - i / m} = \frac{m}{m - i}$ $\frac{1}{1 - i / m} = \frac{m}{m - i}$ ，故一次成功查找的期望探查次数至多为
- $\begin{aligned}\frac{1}{n}\sum_{i = 0}^{n - 1}\frac{m}{m - i} = \frac{1}{\lambda} \sum_{k = m - n + 1}^m \frac{1}{k} \le \frac{1}{\lambda} \int_{m-n}^{m} (1/x)\, {\rm d}x = \frac{1}{\lambda} \ln \frac{1}{1 - \lambda} \end{aligned}$

线性试探

$r_i(key) = (\text{hash}(key) + i) \, \text{mod} \, \mathcal{M}, \quad i = 0, 1, 2, 3, \dots$
只要还有空桶，试探链就不会循环，查找也能终止
试探链会相互重叠，非同义词会彼此堆积
- 控制好装填因子，冲突和堆积都不致太严重： $E(probes) = \frac{1}{1 - \lambda}$
数据局部性极佳，系统缓存的作用发挥极致

对于一个装填因子为 $\lambda = \frac{n}{m}$ 的采用线性试探的散列表，平均成功探查次数 $ASL_{succ}\sim \frac{1}{2}(1 + \frac{1}{1 - \lambda})$ ，平均失败探查次数 $ASL_{fail}\sim \frac{1}{2}(1 + \frac{1}{(1 - \lambda)^2})$

对于一组固定的键，它们的总探查次数是一个固定值，与插入顺序无关

懒惰删除

仅做标记，不对试探链做更多调整
- Bitmap *removed;
- 查找时，被视为“必不匹配的非空桶”，使得试探链可以在此延续
- 插入时，被视作“总是匹配的空闲桶”，以存放新词条
- 装填因子的计算口径有变
试探链因此可能彼此有所重叠
- 任何一个带有懒惰删除标记的桶，都可能同时属于多个试探链

template<typename K, typename V> Rank Hashtable<K, V>::probe4Hit(const K &k) {
    for (Rank r = hashCode(k) % M; ; r = (r + 1) % M)
        if (ht[r] && (k == ht[r]->key) ||
           !ht[r] && !removed->test(r)) { // 跳过被删除的桶
            return r;
        }
}
template<typename K, typename V> Rank Hashtable<K, V>::probe4Free(const K &k) {
    for (Rank r = hashCode(k) % M; ; r = (r + 1) % M)
        if (!ht[r]) return r;
}

重散列

template<typename K, typename V> bool Hashtable<K, V>::remove(K k) {
    Rank r = prob4Hit(k);
    if (!ht[r]) return false;
    delete ht[r]; ht[r] = NULL; --N;
    removed->set(r);
    return true;
}

template<typename K, typename V> bool Hashtable<K, V>::put(K k, V v) {
    if (ht[probe4Hit(k)]) return false;
    Rank r = probe4Free(k);
    ht[r] = new Entry<K, V>(k, v); ++N;
    removed->clear(r); // 清除懒惰标记
    if ((N + removed->size()) * 2 > M)
        rehash(); // 装填因子计入懒惰标记位, 且达到阈值进行重散列
    return true;
}

Rehashing：随着装填因子攀升，冲突激增；超过阈值后，便需要扩容

template<typename K, typename V> void Hashtable<K, V>::rehash() {
    Rank oldM = M; Entry<K, V> **oldHt = ht;
    ht = new Entry<K, V> *[M = primeNLT(4 * N)]; N = 0;
    memset(ht, 0, sizeof(Entry<K,V>*) * M);
    // 新表扩容并初始化各桶
    delete removed; removed = new Bitmap(M);
    for (Rank i = 0; i < oldM; i++)
        if (oldHt[i]) // 不能直接复制, 逐个转入新表
            put(oldHt[i]->key, oldHt[i]->value);
    delete[] oldHt;
}

平方试探

$r_i(key) = ({\rm hash}(key) + i^2) \, {\rm mod} \, M, \quad i = 0, 1, 2, 3, \dots$ $r_{i} (k e y) = (h a s h (k e y) + i^{2}) m o d M, i = 0, 1, 2, 3, \dots$
- 沿着试探链，各桶的间距线性递增
数据堆积现象改善，cache 利用率下降但依旧够用
表长为素数（不仅限于）时，只要 $\lambda < 0.5$ $λ < 0.5$ 就一定可以找到空桶
- 若 $M$ $M$ 为素数，则 $n^2 \, \% \,M$ $n^{2} % M$ 恰有 $\lceil M / 2 \rceil$ $⌈ M / 2 ⌉$ 种取值，且由试探链的 前 $\lceil M / 2 \rceil$ 项取遍
  - 反证，假设存在 $0 \le a < b < \lceil M / 2 \rceil$ ，使得第 $a$ 、 $b$ 项冲突
  - 则有 $a^2 \equiv b^2 \quad({\rm mod} \, M)$ ，即 $(b + a) \cdot (b - a) \equiv 0 \quad ({\rm mod} \, M)$
  - 然而， $0 < b - a \le b + a < \lceil M / 2 \rceil + (\lceil M / 2 \rceil - 1) \le \lceil M / 2 \rceil + \lfloor M / 2 \rfloor = M$
  - 无论 $b - a$ 还是 $b + a$ 都不可能整除 $M$

双向平方试探

$r_i(key) = ({\rm hash}(key) + (-1)^{i + 1} \cdot (\lceil i / 2 \rceil)^2) \, {\rm mod} \, M, \quad i = 0, 1, 2, 3, \dots$
正向和反向的子试探链，各自包含 $\lceil M / 2 \rceil$ $⌈ M / 2 ⌉$ 个互异的桶
- $-\lfloor M / 2 \rfloor, \dots, -2, -1, 0, 1, 2, \dots, \lfloor M / 2 \rfloor$
- 表长取 素数 $\mathcal{M} = 4 \cdot k + 3$ （但不仅限于这些数），则必然可以保证试探链的前 $M$ $M$ 项互异
  - 原理：素数 $p$ 不能表示为一对整数的平方和，当且仅当 $p \equiv 3 ({\rm mod} \, 4)$

双散列

预先约定第二散列函数： $hash_2(key, i)$
- 冲突时，由其确定偏移增量，确定下一试探位置
  
  $\begin{aligned}(hash(key) + \sum_{i = 1}^k hash_2(key, i)) \, \% \, M\end{aligned}$
线性试探： $hash_2(key, i) \equiv 1$
平方试探： $hash_2(key, i) = 2i - 1$

桶排序

算法

简单情况
- 对 $[0, m)$ 内的 $n$ （ $<m$ ）个互异整数，借助散列表 H[] 进行排序
- 空间 $O(m)$ ，时间 $O(m)$
复杂情况
- 允许相等的元素（可能 $m \ll n$ ）
- 依然使用散列表，每一组同义词各成一个链表
  - 可稳定
- 空间 $O(n + m)$ ，时间 $O(n)$

Max Gap

任意 $n$ $n$ 个互异点均将实轴分为 $n - 1$ $n - 1$ 段有界区间，其中的哪一段最长？
- 排序再计算—— $O(n \log n)$
- 采用分桶策略，可改进至 $O(n)$
线性算法
- 一趟扫描找到最左、最右点
- 将有效范围均等划分为 $n - 1$ 段（ $n$ 个桶）
- 通过散列，将各点归入对应的桶
  - 各桶动态更新最左点、最右点
- 计算相邻非空桶之间的“距离”
- 最大距离即 Max Gap
正确性：由于有 $n$ 个数、 $n$ 个桶，Max Gap 至少跨越两个桶
对称的 Mini Gap 问题不能沿用该法突破 $\Omega(n \log n)$

基数排序

有时，关键码由多个域（字段）组合而成： $k_t, k_{t - 1}, \dots, k_1$ 。并采用字典序的确定大小次序
可以采用 低位优先的多趟桶排序 ——基数排序
- 自 $k_1$ $k_{1}$ 到 $k_t$ $k_{t}$ （低位优先），依次以各域为序做一趟桶排序
  - 正确性得益于桶排序的稳定性
- 总时间为 $O(n + M_1) + O(n + M_2) + \dots + O(n + M_t) = O(t \times (n + M))$

常对数密度整数集

考查取自 $[0, n^d)$ $[0, n^{d})$ 内的 $n$ $n$ 个整数，对数密度 = $\frac{\ln n}{\ln n^d} = \frac{1}{d} = O(1)$ $\frac{l n n}{l n n ^{d}} = \frac{1}{d} = O (1)$
- 这类整数集的对数密度不超过常数
此时可将所有元素预处理为 $n$ $n$ 进制形式
- $x = (x_d, \dots, x_3, x_2, x_1)$
- 每个元素均转化为 $d$ 个域，然后套用基数排序
- 排序时间为 $d \cdot (n + n) = O(n) = o(n \log n)$

计数排序

原理
- 统计每个数出现次数
- 自前向后扫描各桶，依次累加
  - 如此可确定各元素所处的 秩区间
- 自后向前 计算每个数的排名
  - 对应桶的计数减一，即是其在最终有序序列中对应的秩
  - 不可改为从前向后扫描，否则稳定性无法保证
时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ ，稳定

跳转表

基于朴素的 List 结构，采取随机策略
- 从 数学期望 的角度控制查找长度

结构

逐层 折半稀疏 的列表： $S_0, S_1, \dots, S_h$ $S_{0}, S_{1}, \dots, S_{h}$
- 依次叠放耦合， $S_0$ / $S_h$ 称作底/顶层
横向为层 level ：prev() 、next() 、哨兵
纵向成塔 tower ：above() 、below()
四联节点

空间性能 ${\rm expected}$ $e x p e c t e d$ - $O(n)$ $O (n)$
- $S_0$ 中任一关键码在 $S_k$ 中依然出现的概率为 $p^{k}$
- 第 $k$ 层节点数的期望值 $E(\left\vert S_k \right\vert) = n \cdot p^{k}$
- 所有节点期望总数为 $E(\sum_k \left\vert S_k \right\vert) = n \times \sum_k p^{k} = \frac{n}{1 - p} = O(n)$

查找、插入和删除

template<typename K, typename V> // 关键码不大于 k 的最后一个词条(所对应塔的基座)
QNodePosi<Entry<K, V>> Skiplist<K, V>::search(K k) {
    for (QNodePosi<Entry<K, V>> p = first()->data->head; ; ) {
        if (p->succ->succ && (p->succ->entry.key <= k)) p = p->succ; // 尽可能右移
        else if (p->below) p = p->below; // 水平越界时, 下移
        else return p;
    }
}

template<typename K, typename V> bool Skiplist<K, V>::put(K k, V v) {
    Entry<K, V> e = Entry<K, V>(k, v);
    QNodePosi<Entry<K, V>> p = search(k);
    ListNodePosi<Quadlist<Entry<K, V>>* > qlist = last(); // 从底层开始
    QNodePosi<Entry<K, V>> b = qlist->data->insert(e, p); // 创建新塔的基座
    while (rand() & 1) { // 建塔
        while (p->pred && !p->above) p = p->pred; // 找出不低于此时高度的最近前驱
        if (!p->pred && !p->above) { // 需创建新的一层
            insertFirst(new Quadlist<Entry<K, V>>);
            first()->data->head()->below = qlist->data->head;
            qlist->data->head->above = first()=>data->head;
        }
        p = p->above; qlist = qlist->pred;
        b = qlist->data->insert(e, p, b);
    }
    return true;
}

template<typename K, typename V> bool Skiplist<K, V>::remove(K k) {
    QNodePosi<Entry<K, V>> p = search(k);
    if (!p->pred || (k != p->entry.key)) return false;
    ListNodePosi<Quadlist<Entry<K, V>> *> qlist = last();
    while (p->above) { qlist = qlist->pred; p = p->above; } // 先升至塔顶
    do {
        QNodePosi<Entry<K, V>> lower = p->below;
        qlist->data->remove(p);
        p = lower; qlist = qlist->succ;
    } while (qlist->succ); // 拆塔
    while (height() > 1 && first()->data->_size < 1) {
        List::remove(first());
        first()->data->head->above = NULL;
    } // 删除已不含词条的 Quadlist
    return true;
}

总览

纵向跳转 $\sim$ $\sim$ 层高
- 一座塔的高度不低于 $k$ $k$ 的概率为 $p^k$ $p^{k}$
  - $\Pr(\left\vert S_k \right\vert = 0) = (1 - p^k)^n \ge 1 - n \cdot p^k$
  - 跳转表高度 $h = \log_{1/p}(n) = O(\log n)$ 的概率极大
- 查找过程中，纵向跳转的次数，累计不过 ${\rm expected}$ $e x p e c t e d$ - $O(\log n)$ $O (lo g n)$
  - 单个塔高为 ${\rm expected}$ - $O(1)$
横向跳转 $\sim$ $\sim$ 紧邻塔顶
- 在同一水平列表中，横向跳转所经节点必然依次紧邻，而且每次抵达都是塔顶
- 将沿同一层列表跳转的次数记作 $Y$ $Y$ ，则它符合 几何分布（简化模型，最后一个也可能是塔顶）
  - $\Pr(Y=k) = (1 - p)^k \cdot p$ ， $E(Y) = (1 - p) / p$
- 因此，对于 $p = 1/2$ ，在同一层列表中连续跳转的期望时间成本 = 1 次跳转 + 1 次驻足 = 2
跳转表的每次查找，都可在 $\le expected-(2h) = expected-O(\log n)$ 时间内完成
通过维护每一个前向指针的长度，还可以将跳表的随机访问优化至 $O(\log n)$

图

概述

$G = (V; \, E)$ ， $n = \left\vert V \right\vert$ ， $e = \left\vert E \right\vert$
同一条边的两个顶点 $u、v$ $u 、 v$ 彼此邻接，若顶点次序无所谓，则 $(u, v)$ $(u, v)$ 为无向边
- 所有边均为方向的图为无向图
- 有向图中均为有向边 $u \rightarrow v$ $u \to v$
  - $u、v$ 分别称作边 $(u, v)$ 的尾、头
路径 $\pi = \left\langle v_0, v_1, \dots, v_k \right\rangle$ $π = ⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ ，长度 $\left\vert \pi \right\vert = k$ $∣ π ∣ = k$
- 简单路径： $v_i \ne v_j$ 除非 $i = j$
- 环路： $v_0 = v_k$
- 欧拉环路：各边恰好出现一次
- 哈密尔顿环路：各点恰好出现一次
- 有向无环图：Directed Acyclic Graph，DAG
图 $G = (V; \, E)$ $G = (V; E)$ 的子图 $T=(V; \, F)$ $T = (V; F)$ 若是树，则称其为 $G$ $G$ 的 支撑树
- 各边 $e$ 均有对应的权值 ${\rm wt}(e)$ ，则为带权网络
- 同一网络的支撑树中，总权重最小者为最小支撑树（MST）

图的存储

模板类

template<typename Tv, typename Te> class Graph {
private:
    void reset() {
        for (Rank v = 0; v < n; v++) {
            status(v) = UNDISCOVERD; dTime(v) = fTime(v) = -1;
            parent(v) = -1; priority(v) = INT_MAX;
            for (Rank u = 0; u < n; u++)
                if (exists(v, u)) type(v, u) = UNDETERMINED;
        }
    }
public:
    Rank n, e;
}

using VStatus = enum { UNDISCOVERED, DISCOVERED, VISITED };
template<typename Tv> struct Vertex {
    Tv data; int inDegree, outDegree;
    VStatus status; int dTime, fTime;
    Rank parent; int priority;
    Vertex(Tv const &d) :
    	data(d), inDegree(0), outDegree(0), status(UNDISCOVERED),
    	dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
};

using EType = enum { UNDETERMINED, TREE, CROSS, BACKWARD };
template<typename Te> struct Edge {
    Te data; int weight;
    Etype type;
    Edge(Te const &d, int w) : 
    	data(d), weight(w), type(UNDETERMINED) {}
};

邻接矩阵

Adjacency Matrix：记录顶点之间的邻接关系
- 矩阵元素 $\Leftrightarrow$ $\Leftrightarrow$ 图中可能存在的边
  - 若 $v、u$ 之间存在一条边，则 $A(v, u) = 1$
- 空间复杂度 $\Theta(n^2)$ ，与实际边数无关
优点
- 直观，易于理解实现
- 尤其适用于稠密图
- 一些操作只需 $O(1)$ $O (1)$
  - 包括：判断两点之间是否联边、获取/维护顶点度数等
缺点
- $\Theta(n^2)$ $Θ (n^{2})$ 空间，与边数无关
  - 对于平面图 planar graph ：可嵌入于平面的图
  - $v - e + f - c = 1, \quad {\rm for \,\, any \,\, pg}$ $v - e + f - c = 1, f o r a n y p g$
    - 分别代表点数、边数、将平面分割成的区域数、联通分量
  - $e \le 3n - 6 =O(n) \ll n^2$
Incidence Matrix：记录顶点与边之间的关联关系
- 空间复杂度 $\Theta(n \cdot e) = O(n^3)$ ，利用率 $\frac{2e}{ne} = \frac{2}{n} \rightarrow 0$

邻接表

将邻接矩阵的各行组织为列表，只记录存在的边
- 等效于，每一顶点 $v$ 对应于列表： $L_v = \{u\, | \,\left\langle v, u \right\rangle \, \in E\}$
- 有向图 $O(n + e)$ ，无向图 $O(n + e)$
- 适用于稀疏图

// 链式前向星, 最新的边插入表头
void add(int u, int v) {
    nxt[++cnt] = head[u]; // 当前边的后继
    to[cnt] = v; // 当前边的终点
    head[u] = cnt; // 起点 u 的第一条边
}
// 遍历
for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
}

图的遍历

广度优先搜索

Breadth-First Search
- 依次访问当前节点，再依次访问它们所有尚未访问的邻接顶点，如此反复
- 以上策略和过程等同于树的 层次遍历
- BFS 会构造出原图的一棵支撑树

实现

template<typename Tv, typename Te> void Graph<Tv, Te>::BFS(Rank v, Rank &dClock) {
    Queue<Rank> Q; status(v) = DISCOVERED;
    Q.enqueue(v); dTime(v) = dClock++;
    for (Rank fClock = 0; !Q.empty(); ) {
        if (dTime(v) < dTime(Q.front()))
            dClock++, fClock = 0; // 开启新的一代
        v = Q.dequeue();
        for (Rank u = firstNbr(v); u != -1; u = nextNbr(v, u)) {
            if (status(u) == UNDISCOVERED) {
                status(u) = DISCOVERED;
                Q.enqueue(u); dTime(u) = dClock;
                // 引入树边, 拓展 BFS 树
                type(v, u) = TREE; parent(u) = v;
            } else {
                type(v, u) = CROSS;
            }
        }
        status(v) = VISITED; fTime(v) = fClock++;
    }
}

推广：若图中包含多个连通/可达分量，则一次检查所有顶点，遇到未发现者则启动一次 BFS

template<typename Tv, typename Te> void Graph<Tv, Te>::bfs(Rank s) {
    reset(); Rank dClock = 0;
    for (Rank v = s; v < s + n; v++)
        if (status(v) == UNDISCOVERED)
            BFS(v % n, dClock);
}

时间复杂度
- 初始化 $O(n + e)$ ，遍历 $O(\sum_{v \in V}(1 + deg(v))) = O(n + 2e)$
- 总计 $O(n + e)$

性质及规律

经 BFS 后，所有边将确定方向，且被分为两类
- 树边 TREE，跨边 CROSS
BFS(v) 以 $v$ 为根，生成一棵 BFS 树
bfs(s) 生成一个 BFS 森林，包含 $c$ 棵树、 $n - c$ 条树边、 $e - n + c$ 条跨边
无向图中，顶点 $v$ $v$ 到 $u$ $u$ 的（最近）距离记作 $dist(v, u)$ $d i s t (v, u)$
- BFS 过程中，队列 $Q$ $Q$ 犹如一条贪吃蛇
  - 其中的顶点按 $dist(s)$ 单调排列
  - 相邻顶点的 $dist(s)$ 相差不超过 1
  - 首、末顶点的 $dist(s)$ 相差不超过 1
  - 由树边联接的顶点， $dist(s)$ 恰好相差 1
  - 由跨边联接的顶点， $dist(s)$ 至多相差 1
- BFS 树中从 $s$ 到 $v$ 的路径，即是二者在原图中的最短通路

深度优先搜索

Depth-First Search
- DFS(s)
  - 访问顶点 $s$
  - 若 $s$ 尚有未被访问的邻居，则任取其一 $u$ ，递归执行 DFS(u)
  - 否则，返回
- 对树而言，等效于 先序遍历
- DFS 会构造出原图的一棵支撑树

实现

template<typename Tv, typename Te> void Graph<Tv, Te>::DFS(Rank v, Rank &clock) {
    dTime(v) = ++clock; status(v) = DISCOVERED;
    for (Rank u = firstNbr(v); u != -1; u = nextNbr(v, u)) {
        switch (status(u)) {
            case UNDISCOVERED:
                type(v, u) = TREE; parent(u) = v;
                DFS(u, clock); break;
            case DISCOVERED: // u 已被发现但未访问完毕, 应为被后代指向的祖先
                type(v, u) = BACKWARD; break;
            default: // u 已访问完毕, 则视承袭关系分为前向边或跨边
                type(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS; break;
        }
    }
    status(v) = VISITED; fTime(v) = ++clock;
}

与 bfs(s) 类似，dfs(s) 也可在 $O(n + e)$ $O (n + e)$ 时间内
- 对于每一连通/可达分量，从其起始顶点 $v$ 进入 DFS（v） 恰好 1 次
- 最终生成一个 DFS 森林（包含 $c$ 棵树、 $n - c$ 条树边）

性质

活跃期 $active[u] = (dTime[u], fTime[u])$ $a c t i v e [u] = (d T i m e [u], f T i m e [u])$
- 括号引理：给定有向图 $G = (V, E)$ $G = (V, E)$ 及其任一 DFS 森林，则
  - $u$ 是 $v$ 的后代 $\iff active[u] \subseteq active[v]$
  - $u$ 是 $v$ 的祖先 $\iff active[u] \supseteq active[v]$
  - $u$ 和 $v$ “无关” $\iff active[u] \cap active[v] = \varnothing$
边分类
- $TREE(v, u)$ $T R E E (v, u)$
  - 可以从当前 $v$ 进入处于 UNDISCOVERED 状态的 $u$
- $BACKWARD(v, u)$ $B A C K W A R D (v, u)$
  - 试图从当前 $v$ 进入处于 DISCOVERED 状态的 $u$
  - DFS 发现后向边 $\iff$ $⟺$ 存在回路
    - 后向边数 $\leqslant$ 回路数
- $FORWARD(v, u)$ $F O R W A R D (v, u)$
  - 试图从当前 $v$ 进入处于 VISITED 状态的 $u$ ，且 $v$ 更早被发现
- $CROSS(v, u)$ $C R O S S (v, u)$
  - 试图从当前 $v$ 进入处于 VISITED 状态的 $u$ ，且 $u$ 更早被发现

拓扑排序

任给有向图 $G$ ，尝试将所有顶点排成一个线性序列，使其次序与原图相容

（每一顶点都不会通过边指向前驱顶点）
- 每个 DAG 对应一个 偏序集 ，而拓扑排序对应一个全序集
  - 有限偏序集必有极值元素，任意 DAG 必有入度为零的顶点
- 可以拓扑排序的有向图，必定无环
- 任何 DAG，都存在至少一种拓扑排序

策略

顺序输出 零入度 顶点 $O(n + e)$

将所有入度为零的顶点存入栈S, 取空队列Q
while (!S.empty()) {
	Q.enqueue( v = S.pop() )
	for each edge(v, u)
		if (u.inDegree < 2) S.push(u)
	G = G \ { v } // 删除v及其关联边(邻接顶点入度减1)
}
return |G| ? "NOT_A_DAG" : Q

逆序输出零出度顶点 $O(n + e)$
- 对图 G 做 DFS，其间
  - 每当有顶点被标记为 VISITED，则将其压入栈 S
  - 一旦发现有后向边，则报告“NOT_A_DAG”并退出
- DFS 结束后，顺序弹出 S 中的各个顶点
  - 各节点按 fTime 逆序排列，即是拓扑排序

双连通分量

无向图 的关节点：其删除之后，原图连通分量增多
- 无关节点的图，称作双连通图
- 极大的双连通子图，称作双连通分量
- DFS 树中的叶节点，不可能是关节点
Highest Connected Ancestor，hca(v) 表示 $subtree(v)$ $s u b t r e e (v)$ 经 后向边 能抵达的最高祖先
- 由括号引理，dTime 越小的祖先，辈份越高
- DFS 过程中，一旦发现后向边 $(v, u)$ $(v, u)$
  - 即取 hca(v) = min(hca(v), dTime(u))
- DFS(u) 完成并返回 $v$ $v$ 时
  - 若有 hca(u) < dTime(v) ，则取 hca(v) = min(hca(u), hca(v))
  - 否则可以断定， $v$ 是关节点，且 $\{v\} + subtree(u)$ 是一个 BCC

实现

template<typename Tv, typename Te> void Graph<Tv, Te>::BCC(Rank v, int &clock, Stack<Rank> &S) {
    hca(v) = dTime(v) = ++clock; status(v) = DISCOVERED; S.push(v);
    for (Rank u = firstNbr(v); u != -1; u = nextNbr(v, u)) {
        switch (status(u)) {
            case UNDISCOVERED:
                parent(u) = v; type(v, u) = TREE;
                BCC(u, clock, S);
                if (hca(u) < dTime(v)) {
                    hca(v) = min(hca(v), hca(u));
                } else { // 否则 v 是关节点
                    // 此时弹出当前 BCC 中除 v 外的所有节点
                    while (u != S.pop());
                }
                break;
            case DISCOVERED:
                type(v, u) = BACKWARD;
                if (u != parent(v))
                    hca(v) = min(hca(v), dTime(u));
                break;
            default; // digraphs only
                break;
        }
    }
    status(v) = VISITED;
}

强联通分量

有向图 的强连通性：图中任意两个节点 $u$ $u$ 和 $v$ $v$ ，都存在从 $u$ $u$ 到 $v$ $v$ 的路径，也存在从 $v$ $v$ 到 $u$ $u$ 的路径
- 满足这种性质的图，称作强连通图
- 极大的强连通子图，称作强连通分量（SCC）
Lowest Reachable Ancestor，low(v) 表示从 $subtree(v)$ $s u b t r e e (v)$ 出发，通过 最多一条非树边 能抵达的、仍在栈中 的最早被发现的祖先
- DFS 过程中，一旦发现一条非树边 $(v, u)$ $(v, u)$ ，且 $u$ $u$ 仍在栈中
  - 即取 low(v) = min(low(v), dTime(u))
- DFS(u) 完成并返回 $v$ $v$ 时
  - 取 low(v) = min(low(v), low(u))（子节点能到达的最低点，父节点也能到）
  - 若返回后发现 low(v) == dTime(v)，则可以断定， $v$ $v$ 是当前发现的一个 SCC 的根
    - 此时，从栈顶到 $v$ 的所有节点，构成一个完整的 SCC

实现

template<typename Tv, typename Te> void Graph<Tv, Te>::SCC(Rank v, int &clock, Stack<Rank> &S) {
    low(v) = dTime(v) = ++clock; status(v) = DISCOVERED; S.push(v);
    for (Rank u = firstNbr(v); u != -1; u = nextNbr(v, u)) {
        switch (status(u)) {
            case UNDISCOVERED:
                parent(u) = v; // 树边
                SCC(u, clock, S);
                low(v) = min(low(v), low(u));
                break;
            case DISCOVERED:
                low(v) = min(low(v), dTime(u));
                break;
            default:
                // (v, u) 是前向边 或 指向已完成 SCC 的跨边
                // 对 low(v) 的计算没有贡献, 忽略
                break;
        }
    }

    if (low(v) == dTime(v)) {
        while (v != S.pop()); // 弹出当前 SCC 中所有点
    }
    status(v) = VISITED;
}

优先级搜索

不同的遍历算法，取决于顶点的 访问策略
可以为每个顶点 $v$ $v$ 维护一个优先级数 priority(v)
- 每个顶点都有初始优先级数；并可能随算法的推进而调整
- 优先级数越大/小，优先级越低/高

统一框架

template<typename Tv, typename Te>
template<typename PU> // 优先级更新策略
void Graph<Tv, Te>::PFS(Rank v, PU prioUpdater) {
    priority(v) = 0; status(v) = VISITED;
    while (1) { // 将下一顶点和边加至 PFS 树中
        for (Rank k = 1; k < n; k++) { // 逐步引入 n-1 个顶点
            for (Rank u = firstNbr(v); u != - 1; u = nextNbr(v, u)) {
                prioUpdater(this, v, u); // 更新顶点及其父亲优先级
            }
            int shortest = INT_MAX;
            for (Rank u = 0; u < n; u++) {
                if (status(u) == UNDISCOVERED && shortest > priority(u)) {
                    shortest = priority(u); v = u;
                }
            }
            status(v) = VISITED; type(parent(v), v) = TREE; // 将最高优先级顶点加入遍历树
        }
    }
}

复杂度

考查内循环
- 更新，邻接矩阵 $O(n^2)$ ，临界表 $O(n + e)$
- 择优，每次 $O(n)$ ，累计 $O(n^2)$
- 合计 $O(n^2)$
采用优先级队列，可分别改至 $O(e \cdot \log e)$ $O (e \cdot lo g e)$ 和 $O(n \cdot \log e)$ $O (n \cdot lo g e)$
- 合计 $O((n + e) \cdot \log e)$
- 对于 稠密图 而言，反而是倒退

Dijkstra 算法

问题分类
- SSSP：Single Source Shortest Path
  - 给定顶点 $s$ ，计算其到其余各点的最短路径及长度
- APSP：All Pairs Shortest Path
  - 找出每对顶点 $u$ 和 $v$ 的最短路径及长度

最短路径树

任一最短路径的前缀，也是一条最短路径
- $u \in \pi(v) \quad {\rm only\,\,if} \,\,\, \pi(u) \subseteq \pi(v)$
消除歧义：各边权重均为正，否则
- 有可能出现总权重非正的环路，最短路径无法定义
Shortest Path Tree
- 所有最短路径的并，既连通也无环
- $\begin{aligned}T = T_{n - 1} = \bigcup_{0 \le i < n} \pi(u_i)\end{aligned}$ 构成一棵树

算法与实现

$\forall v \not\in V_k, \,\, {\rm let} \, priority(v) = \lVert s, v \rVert \le \infty$
套用 PFS 框架，为将 $T_k$ $T_{k}$ 扩充至 $T_{k + 1}$ $T_{k + 1}$ ，只需
- 选出优先级最高的跨边 $e_k$ 及其对应顶点 $v_k$ ，将其 加入 $T_k$
- 随后更新 $V \setminus V_{k + 1}$ $V ∖ V_{k + 1}$ 中所有顶点的优先级
  - 只需枚举 $v_k$ 的邻接顶点
  - ${\rm priority}(u) = \min({\rm priority}(u), {\rm priority}(v_k) + \lVert v_k, u \rVert)$

g->pfs(0, DijkPU<char, Rank>()); // 从顶点 0 开始
template<typename Tv, typename Te> struct DijkPU {
    virtual void operator()(Graph<Tv, Te>* g, Rank v, Rank u) {
        if (g->status(u) != UNDISCOVERED) return;
        // 尚未被发现的邻居 u, 按 Dijkstra 策略做松弛
        if (g->priority(u) > g->priority(v) + g->weight(v, u)) {
            g->priority(u) = g->priority(v) + g->weight(v, u);
            g->parent(u) = v;
        }
    }
}

Prim 算法

最小支撑树
- 总权重 ${\rm w}(T) = \sum_{e \in F} {\rm w}(e)$ 最小的支撑树
- $MST \ne SPT$
- 允许权值为负
  - 支撑树所含边数相等，故可统一调整 increase(1 - findMin())
Cayley 公式：完全图 $\mathcal{K}_n$ 有 $n^{n - 2}$ 棵支撑树

割与极短跨边

任何环路 $C$ 上的最长边 $f$ ，都不会被 MST 采用
- 否则在 $C$ 上必然有另一更优跨边 $e$ 可以替换 $f$
设 $(U;V \setminus U)$ 是图 $N$ 的一个割
- 若 $(u, v)$ $(u, v)$ 是该割的一条极短跨边，则必然 存在一棵包含 $(u, v)$ 的 MST
  - 可反证，任取一棵 MST，将 $(u, v)$ $(u, v)$ 加入，其中出现唯一的回路
    - 该回路必经过 $(u, v)$ 以及割的至少另一跨边 $(s, t)$
    - 摘除 $(s,t)$ 后恢复为一棵支撑树，且总权重不致增加
- 反之，任一 MST 都必 经由极短跨边联接每一割
Prim
- 递增式构造
  - 首先，仍选 $T_1 = (\{v_1\}; \varnothing)$
  - 不断进行扩张， $T_{k + 1} = (V_{k + 1};E_{k + 1}) = (V_k \cup \{v_{k + 1}\}; E_k \cup \{v_{k + 1} u\})$
  - 只需将 $(V_k; V \setminus V_k)$ $(V_{k}; V ∖ V_{k})$ 视作原图的一个割
    - 该割所有跨边中极短者即是 $v_{k + 1}u$
- 正确性证明
  - 只需归纳证明：每一步迭代时，都存在一棵 MST 包含已选边集
    - 假设某时刻边集为 $F$ ，令 $T$ 为包含其的一棵 MST ，考虑下一条加入的边 $e$
    - 如果 $e \in T$ ，那么成立
    - 否则， $T + e$ 一定存在一个环，且该环中至少有一条边 $f \not\in F$
    - 首先， $f$ 的权值一定不会比 $e$ 小，否则 $f$ 会在 $e$ 之前被选取
    - 然后， $f$ 的权值一定不会比 $e$ 大，不然 $T - f + e$ 就是一棵更优的支撑树
    - 所以， $F \subset T + e - f$ ，并且这也是一棵 MST
- 但是，由极短跨边构成的支撑树，未必就是一棵 MST

算法实现

$\forall v \not\in V_k, \,\, {\rm let} \, priority(v) = \lVert V_k, v \rVert \le \infty$
枚举 $v_k$ 的邻接顶点 $u$ ，取 ${\rm priority}(u) = \min({\rm priority}(u), \lVert v_k, u \rVert)$

g->pfs(0, PrimPU<char, Rank>()); // 从顶点 0 开始
template<typename Tv, typename Te> struct PrimPU {
    virtual void operator()(Graph<Tv, Te>* g, Rank v, Rank u) {
        if (g->status(u) != UNDISCOVERED) return;
        if (g->priority(u) > g->weight(v, u)) {
            g->priority(u) = g->weight(v, u);
            g->parent(u) = v;
        }
    }
}

Kruskal 算法

贪心
- 根据代价，从小到大依次尝试各边
- 只要“安全”（不会形成环），就加入该边
正确性
- Kruskal 引入的每条边都属于某棵 MST
- 也可归纳证明：任何时刻，算法选择的边集总是某棵 MST 的子图

并查集

给定一组互不相交的 等价类，各由其中一个成员作为代表
- Find(x) ：找到元素 $x$ 所属的等价类
- Union(x, y) ：合并 $x$ 和 $y$ 所属等价类
优化：路径压缩，启发式合并

Floyd 算法

给定带权网络 $G$ $G$ ，计算其中所有点对之间的最短距离
- Floyd-Warshall
  - 最短路径矩阵
  - 时间 $O(n^3)$ ，实现简单，允许负权边
- 定义 $d^k(u, v)$ $d^{k} (u, v)$ 为中途只经过前 $k$ $k$ 个顶点中转，从 $u$ $u$ 到 $v$ $v$ 的最短路径长度
  - $d^0(u, v) = w(u, v)$
  - $d^k(u, v) = \min\{d^{k - 1}(u, v), d^{k - 1}(u, x) + d^{k - 1}(x, v) \}$

for (int k = 0; k < n; k++)
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
            A[u][v] = min(A[u][v], A[u][k] + A[k][v]);

优先级队列

概述

循 优先级 访问
- 极值元素：须反复、快速定位

template<typename T> struct PQ {
    virtual void insert(T) = 0;
    virtual T delMax() = 0;
    virtual T &getMax() = 0;
};

只需查找极值元，则不必维护所有元素之间的全序关系，偏序足矣

完全二叉堆

结构性：逻辑上完全等同于完全二叉树，可直接借助向量实现
1
2
3
#define Parent(i) (((i) - 1) >> 1)
#define LChild(i) (1 + ((i) << 1))
#define RChild(i) ((1 + (i)) << 1)
- 内部节点最大秩为 $\lfloor \frac{n - 2}{2} \rfloor$

堆序性：处处满足 H[i] <= H[Parent(i)]

H[0] 即是全局最大者

1
2
3

template<typename T> T & PQ_ComlHeap::getMax() {
    return _elem[0];
}

插入删除

逐层上滤和逐层下滤

template<typename T> void PQ_ComplHeap<T>::insert(T e) {
    Vector<T>::insert(e);
    percolateUp(_elem, size - 1);
}
typename<typename T> Rank percolateUp(T *A, Rank i) {
    while (i > 0) {
        Rank j = Parent(i);
        if (A[j] >= A[i]) break;
        swap(A[i], A[j]); i = j;
    }
    return i;
}

template<typename T> T PQ_ComlHeap<T>::delMax() {
    T maxElem = _elem[0]; _elem[0] = _elem[--_size];
    percolateDown(_elem, _size, 0);
    return maxElem;
}
template<typename T> Rank percolateDown(T *A, Rank n, Rank i) {
    Rank j;
    while (i != (j = ProperParent(A, n, i)))
        swap(A[i], A[j]), i = j;
    return i;
}

$e$ $e$ 在每一高度至多交换一次，而完全树必平衡，故插入/删除只需 $O(\log n)$ $O (lo g n)$ 时间
- 平均情况为，插入 $O(1)$ / 删除 $O(\log n)$

建堆

自上而下（或自下而上）的上滤
1
2
for (Rank i = 1; i < n; i++)
percolateUp(i);
- 最坏情况每个节点所需成本线性正比于其深度，总计 $O(n \log n)$
自下而上的下滤
1
2
for (Rank i = n / 2 - 1; i != -1; i--)
percolateDown(i);
- 可理解为子堆的 逐层合并 ，堆序性最终必全局恢复
- 每个内部节点所需成本正比于其高度，总计 $O(n)$
  - 所有节点高度总和为
    
    $\begin{aligned}S(n) &= \sum_{k = 1}^h k \cdot 2^{h - k} = \sum_{k = 1}^h \sum_{i = 1}^k 2^{h - k} = \sum_{i = 1}^h \sum_{k = i}^h 2^{h - k} \\ &=\sum_{i = 1}^h \sum_{k = 0}^{h - i} 2^k = \sum_{i = 1}^h 2^{h - i + 1} - h \\ &= 2^{h + 1} - 2 - h = O(n) \end{aligned}$
- 不适用在线场合

一些应用

Min-Max Heap

最小-最大堆是一个完全二叉堆，具有最小堆和最大堆的特征
- 树中偶数层级的节点都不大于其后代，奇数层级的节点都不小于其后代
- 因此根为 ${\rm Min}$ ，根的左右孩子中的较大者为 ${\rm Max}$
可以在 $O(\log n)$ 时间内同时维护最大值和最小值

对顶堆

由一个大根堆与一个小根堆组成
- 小根堆维护大值 即前 $k$ 大的值，大根堆维护小值即比第 $k$ 大数小的其他数
查询第 $k$ $k$ 大元素的时间复杂度为 $O(1)$ $O (1)$ ，且可在 $O(\log n)$ $O (lo g n)$ 时间内进行以下操作
- 维护（核心思想是保持小根堆的元素数量）、插入元素、删除第 $k$ 大元素、 $k$ 值+1/-1

堆排序

相当于用堆优化 选择排序
- 首先建堆，然后不断迭代
  - 取最大值交换至无序部分尾部，删除当前最大值
- 总时间 $O(n) + n \cdot O(\log n) = O(n \log n)$ $O (n) + n \cdot O (lo g n) = O (n lo g n)$
  - 最好情况为 $O(n)$ （所有元素均相等）
就地算法，但不稳定

template<typename T> void Vector<T>::heapSort(Rank lo, Rank hi) {
    T *A = _elem + lo; Rank n = hi - lo;
    heapify(A, n);
    while (--n > 0) {
        swap(A[0], A[n]); percolateDown(A, n, 0);
    }
}

锦标赛树

胜者树

是完全二叉树，叶节点为各个元素，内部节点为孩子比较后的胜者
- 树根总是全局冠军：类似于堆顶

锦标赛排序

流程
- 构造胜者树
- 选取树根元素
- 沿根向下找到对应叶子，将其无效化（置为 $\pm \infty$ ）
- 从叶子处向上重新进行比较，直至根
- 不断重复
空间 $O(n)$ $O (n)$ ，时间 $O(n + n \cdot \log n) = O(n \log n)$ $O (n + n \cdot lo g n) = O (n lo g n)$ ，不稳定
- 通过记录更新叶子节点的秩，可以稳定

不完全选取

借助锦标赛树，从 $n$ $n$ 个元素中找出最小的 $k$ $k$ 个， $k \ll n$ $k ≪ n$
- 初始化 $O(n)$ ，共 $n - 1$ 次比较
- 迭代 $k$ 步 $O(k \log n)$ ，每步 $\log n$ 次比较
- 常系数相较小顶堆更优

败者树

在胜者树的重赛过程中，须交替访问沿途节点及其兄弟
败者树也是完全二叉树，但其存储内容和胜者树不同
- 内部节点，记录对应比赛的败者
- 增设根的“父节点”，记录冠军
初始化
- 将比赛的败者存入其父节点，胜者则继续向上一层
- 根节点的父节点即是全局的冠军
  - 根节点并非亚军
更新迭代
- 返回叶子进行重赛，元素只需与其 父节点中存储的败者 进行比赛
  - 胜者：继续向上，和更上层节点的败者进行比赛
  - 败者：留在父节点中，替换原来的败者
更新效率更高，用额外的空间使每次信息查找的成本降至最低
- 应用场景：外部排序中的 $k$ -路归并（归并多个有序段）

多叉堆

PFS 中各节点可组织为优先级队列，总体运行时间 $O(n + (n + e) \cdot \log n) = (n + e \cdot \log n)$ $O (n + (n + e) \cdot lo g n) = (n + e \cdot lo g n)$
- 但对于稠密图，不如常规实现
将二叉堆改为多叉堆，堆高降低至 $\log_d n$ $lo g_{d} n$
- 上滤成本降至 $\log_d n$
- 下滤成本增（ $d > 4$ ）至 $d \cdot \log_d n = \frac{d}{\ln d} \cdot \ln n$
如此，PFS 运行时间将为 $n \cdot d \cdot \log_d n + e \cdot log_d n = (n \cdot d + e) \cdot \log_d n$ $n \cdot d \cdot lo g_{d} n + e \cdot l o g_{d} n = (n \cdot d + e) \cdot lo g_{d} n$
- 取 $d \approx e / n + 2$ ，达到最优 $O(e \cdot \log_{e / n + 2} n)$
- 稀疏图保持高效，稠密图改进极大

左式堆

堆合并

方法一：A.insert(B.delMax()) ， $O(m \log (n + m))$
方法二：union(A, B).heapify(n + m) ， $O(n + m)$

两堆合并 = 二路归并

统一沿右侧藤，则所需时间 $\propto$ 右侧藤总长
若能控制藤长，则可持续高效合并

控制藤长

保持 堆序性 ，在堆合并过程中，只涉及少量节点 $O(\log n)$
- 新条件 = 单侧倾斜
  - 节点分布偏向于左侧，合并只涉及右侧
- 不能保证结构性，但这并非堆结构本质要求
Null Path Length，空节点路径长度
- 引入外部节点，转为真二叉树
- $npl({\rm NULL}) = 0$ ， $npl(x) = 1 + \min\{npl({\rm lc}(x)), npl({\rm rc}(x))\}$
- $npl(x) = $ $x$ 到外部节点的最近距离 = 以 $x$ 为根的最大 满子树 的高度
左式堆 $\Leftrightarrow$ 处处左倾
- 对任何内部节点 $x$ $x$ ， $npl({\rm lc}(x)) \ge npl({\rm rc}(x))$ $n p l (l c (x)) \geq n p l (r c (x))$
  - $npl(x) = 1 + npl({\rm rc}(x))$
  - 并不意味着左孩子高度不小于右孩子
- 左倾性不会影响堆序性
- 倾向于将更多节点分布于左侧分支
右侧链 rChain(x) ：从节点 $x$ 出发，一直沿右分支前进
- $npl(r) \equiv \left\vert rChain(r) \right\vert = d$
- 右侧链长为 $d$ $d$ 的左式堆，至少包含
  - $2^d - 1$ 个内部节点
  - $2^{d + 1} - 1$ 个节点
- 包含 $n$ 个节点的左式堆，右侧链长度 $d \le \lfloor \log_2 (n + 1) \rfloor + 1 = O(\log n)$

合并算法

递归：前处理+后处理
- 合并之前，比较 priority 判断是否要交换节点
- 回溯之后，比较 NPL 比较是否要交换子堆

递归实现

template<typename T> BinNodePosi<T> merge(BinNodePosi<T> a, BinNodePosi<T> b) { // 线性递归
    if (!a) return b; if (!b) return a;
    if (*a < *b) swap(a, b);
    (a->rc = merge(a->rc, b))->parent = a; // 将 a 的右子堆与 b 合并
    if (!a->lc || (a->lc->npl < a->rc->npl))
        swap(a->lc, a->rc); // 确保左子堆 npl 不小
    a->npl = a->rc ? 1 + a->rc->npl : 1;
    return a;
} // 返回合并后的堆顶

迭代实现

template<typename T> BinNodePosi<T> merge(BinNodePosi<T> a, BinNodePosi<T> b) {
    if (!a) return b; if (!b) return a;
    if (*a < *b) swap(a, b);
    for (; a->rc; a = a->rc) // 沿右侧链做二路归并, 直至 a-> rc 先于 b 变空
        if (*(a->rc) < *b)
            b->parent = a; swap(a->rc, b);
    (a->rc = b)->parent = a;
    for (; a; b = a, a = a->parent) { // 从 a 出发沿右侧链逐层回溯
        if (!a->lc || (a->lc->npl < a->rc->npl))
            swap(a->lc, a->rc);
        a->npl = a->rc ? a->rc->npl + 1 : 1;
    }
    return b;
}

插入和删除

利用核心操作 merge()

// merge 是 O(logn)
template<typename T> void PQ_LeftHeap<T>::insert(T e) {
    _root = merge(_root, new BinNode<T>(e, NULL));
    _size++;
}

template<typename T> T PQ_LeftHeap<T>::delMax() {
    BinNodePosi<T> lHeap = _root->lc;
    if (lHeap) lHeap->parent = null;
    BinNodePosi<T> rHeap = _root->rc;
    if (rHeap) rHeap->parent = null;
    T e = _root->data;
    delete _root; _size--;
    _root = merge(lHeap, rHeap);
    return e;
}

串

模式匹配

循模式访问
- ${\rm random}\,\, T \, + \, {\rm subtring} \,\, P$
- $n = \left\vert T \right\vert \quad m = \left\vert P \right\vert$
- $ 2 \ll m \ll n$
蛮力策略
- （最差情况下）最好复杂度： $\Omega(n)$ （ $P = {\rm suffix}(T)$ ）
- 平均： $O(n)$
- 最差： $O(n \cdot m)$

int match(char *P, char *T) {
    int n = strlen(T), i = 0;
    int m = strlen(P), j = 0;
    while (j < m && i < n) {
        if (T[i] == P[j]) { i++; j++; }
        else { i -= j - 1; j = 0; } // T 回退, P 复位
    }
    return i - j; // 最终对齐位置
}

KMP 算法

在任一时刻，都有 T[i - j, i) == P[0, j)
- 亦即已掌握了 T[i - j, i) 的所有信息，一旦失败，就应已知哪些位置 值得/不必 对齐
- T[i - j', i) 可径直接受，则不必再做比对
- 如此， $i$ $i$ 将 不必回退
  - 比对成功，则与 $j$ 同步前进
  - 否则， $j$ 更新为某更小的 $j'$ ，并 继续比对

int match(char *P, char *T) {
    int *next = buildNext(P);
    int n = strlen(T), i = 0;
    int m = strlen(P), j = 0;
    while (j < m && i < n) {
        if (j < 0 || T[i] == P[j]) { i++; j++; }
        else j = next[j];
    }
    delete[] next;
    return i - j;
}

next [] 表

最长自匹配：快速右移 + 绝不回退
- $\forall j \ge 1, \, {\rm N}(P, j) = \{0 \le t < j \,\, | \,\, P[0,t) = P[j - t, j)\}$
- ${\rm next}[j] = \max\{N(P, j)\}$ $\Leftrightarrow$ $P[0, j)$ 的最长公共 真前后缀 的长度
传递链
- ${\rm next}^{k + 1}[j] = {\rm next}[{\rm next}^k[j]]$
- $\forall j \ge 1, \, {\rm N}(P, j) = \{ 0, \dots, {\rm next}^2[j], {\rm next}^1[j] \}$
- $-1 \leftarrow 0 \dots \leftarrow {\rm next}^2[j] \leftarrow {\rm next}^1[j] \leftarrow {\rm next}^0[j] = j$
减而治之
- $P$ 在 $j + 1$ 处的自匹配，至多比在 $j$ 处的自匹配多出一个字符
- ${\rm next}[j + 1] = {\rm next}[j] + 1 \iff P[j] = P[{\rm next}[j]]$
- ${\rm next}[0] = -1, \,\, {\rm next}[1] = 0$

int *buildNext(char *P) {
    int m = strlen(P), j = 0;
    int *next = new int[m];
    int t = next[0] = -1;
    while (j < m - 1) {
        if (t < 0 || P[t] == P[j]) {
            ++t; ++j;
            next[j] = t;
        } else t = next[j]; // 尝试下一值得尝试的位置
    }
    return next;
}

分析

摊还分析
- 令 k = 2 * i - j
1
2
3
4
while (j < m && i < n)
if (j < 0 || T[i] == P[j])
i++, j++; // k 恰好加 1
else j = next[j]; // k 至少加 1
- 计步器 k 随着迭代单调递增，且 $k \le 2n - 1$
- 故 build 和 match 总时间复杂度为 $O(n + m)$
每一个 P 串，相当于一台 自动机
适用于顺序存储介质
单次匹配概率越大，优势越明显

再改进

经验 $\sim$ 以往成功的比对：T[i - j, i) 是什么
教训 $\sim$ 以往失败的比对：T[i] 不是什么

- 进一步避免 **注定错误** 的比较 - $\forall j \ge 1, \, {\rm N}(P, j) = \{0 \le t < j \,\, | \,\, P[0,t) = P[j - t, j) \cap {\color{Red}{P[t] \ne P[j]}}\} \cup \{{\color{Red}{-1}}\}$ - ${\color{Red}{-1}} \in {\rm N}(P, j) \ne \varnothing$, ${\rm next}[j] = \max\{{\rm N}(P, j)\}$

int *buildNext(char *P) {
    int m = strlen(P), j = 0;
    int *next = new int[m]; int t = next[0] = -1;
    while (j < m - 1) {
        if (t >= 0 && P[t] != P[j]) {
            t = next[t];
        } else if (P[++t] != P[++j]) { // 此时有扩展匹配段的机会
            next[j] = t;
        } else { // 此时有 P [next[t]] != P [t] == P [j]
            next[j] = next[t];
        }
    }
    return next;
}

BM 算法

通过 后缀匹配 获得比前缀匹配更多的信息来实现更快的字符跳转

迭代： 自右向左 依次比对，找到极大的匹配后缀
- 若完全匹配，则可返回
- 否则查表（类似于 next[] 的作用）确定 P 右移的适当位置，重新自右向左比对

int match(char *T, char *P) {
    int *bc = buildBC(P);
    int *gs = buildGS(P);
    int n = strlen(T), i = 0;
    int m = strlen(P), j = 0;
    for (i = 0; i + m < n; i += max(gs[j]/* or 1 */, j - bc[T[i + j]])) {
        for (j = m - 1; j >= 0 && P[j] == T[i + j]); j--);
        if (j < 0) break;
    }
    delete[] bc; return i; // 最终对齐位置
}

BC 策略

bc [] 表

int *buildBC(char *P) { // 时间复杂度为 O(m+s), s 为字符集规模
    int *bc = new int[256];
    for (size_t j = 0; j < 256; j++) bc[j] = -1;
    for (size_t m = strlen(P), j = 0; j < m; j++)
        bc[P[j]] = j; // 画家算法, 最靠右位置
    return bc;
}

不倾向于使用二维的 bc[][] 表
- 若其能发挥作用，则此时的好后缀必然很长——同时使用的 gs[] 表完全可以替代

分析

最好情况： $O(n / m)$ $O (n / m)$
- 只要 P 不含 T[i + j] ，则可直接移动 $m$ 个字符
- 单次匹配概率越小，性能优势越明显
最差情况： $O(n \times m)$ $O (n \times m)$
- 每轮迭代，都要在扫过整个 P 之后，方能确定右移一个字符
- 单次匹配概率越大的场合，性能越接近于蛮力算法
bc[] 表仅仅利用了失配比对提供的信息（教训）

GS 策略

经验 = 匹配的后缀

Good-Suffix Shift，扫描比对中断于 $T[i + j] = X \ne O = P[j]$ $T [i + j] = X \neq = O = P [j]$ 时， $U = P(j, m)$ $U = P (j, m)$ 即为好后缀
- 下一对齐位置 必须使得
  - $U$ 重新与 $V(k) = P(k, k + m - j)$ 匹配
  - $P[k] \ne O = P[j]$
- 完全匹配
  - 若存在这样的子串 $V(k)$ ，则选取 靠后者 ，通过右移使之与 $U$ 对齐（以免错过可能的成功比对）
- 部分匹配
  - 若不存在，则所有的前缀 $P[0, t)$ 中，选取与 $U$ 的后缀匹配的最长者（以免错过可能的成功比对）
  - $t$ 为 0 则是完全不匹配的情况，可以直接移动整个 $P$ 到 $m + i$ 处

gs [] 表

$\forall \, 0 \le j < m, ss[j] = \max\{ 0 \le s \le j + 1 \,\, | \,\, P(j - s, j] = P[m - s, m) \}$ $\forall 0 \leq j < m, s s [j] = max {0 \leq s \leq j + 1 ∣ P (j - s, j] = P [m - s, m)}$
- $MS[j] = P(j - ss[j], j]$ 即为 $P[0, j]$ 的所有后缀中，与 P 的某一后缀匹配的 最长者

$ss[] \Rightarrow gs[]$ $s s [] \Rightarrow g s []$
- 若 $ss[j] = j + 1$ ，则对任何 $i < m - j - 1$ ， $m - j - 1$ 必是 $gs[i]$ 的一个候选（对应部分匹配）
- 若 $ss[j] \le j$ ，则 $m - j - 1$ 必是 $gs[m - ss[j] - 1]$ 的一个候选（完全匹配）

$ss[]$ $s s []$ 的构造：
- 自后向前逆向扫描，使用双指针维护一个 “已知匹配框”
  - $P(lo, hi]$ 是当前已知的、匹配 P 后缀的最长子串
- 由于 j 严格单调递减、lo 严格单调非增，且每次迭代两者之一会减少，故总时间复杂度为 $O(m)$
- 本质上是 Z-Algorithm（求解最长公共前缀 LCP）在模式串 $P$ 的逆序字符串上的应用

int *buildSS(char *P) {
    int m = strlen(P); int *ss = new int[m];
    ss[m - 1] = m;
    for (int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j--) {
        if (lo < j && ss[m - 1 - (hi - j)] < j - lo) // j 落在匹配框中, 可直接利用之前算出的 ss []
            ss[j] = ss[m - 1 - (hi - j)];
        else {
            hi = j; lo = min(lo, hi);
            while (lo >= 0 && P[lo] == P[m - 1 - (hi - lo)])
                lo--;
            ss[j] = hi - lo;
        }
    }
    return ss;
}

$gs[]$ $g s []$ 的构造：
- 核心是画家算法，按优先级低高先后处理 gs[] 的不同规则
- 其中的“双层循环”同样由于 i, j 两个指针单调变化，故总体是线性的，于是整个算法复杂度为 $O(m)$

int *buildGS(char *P) {
    int *ss = buildSS(P);
    int m = strlen(P); int *gs = new int[m];
    for (int j = 0; j < m; j++) gs[j] = m;
    for (int i = 0, j = m - 1; j >= 0; j--)
        if (j + 1 == ss[j])
            while (i < m - j - 1)
                gs[i++] = m - j - 1; // 对于多个备选, 取最短移动距离
    for (int j = 0; j < m - 1; j++) // 画家算法, 最短移动距离优先
        gs[m - ss[j] - 1] = m - j - 1;
    delete[] ss; return gs;
}

性能分析

空间： $\left\vert bc \right\vert + \left\vert gs \right\vert = O(\left\vert \Sigma \right\vert + m)$
预处理： $O(\left\vert \Sigma \right\vert + m)$
查找效率
- 最好 $O(n / m)$
- 最差 $O(n + m)$
影响因素：单词比对成功的概率
- 通常， $\Pr = 1 / s$

Karp-Rabin 算法

凡物皆数
- Gödel Numbering
  - 逻辑系统的符号、表达式、公式、命题、定理、公理等，均可表示为 自然数
  - 每个有限维的自然数向量（包括字符串），都唯一对应于某个 自然数
    - $\left\langle a_1, a_2, \dots, a_n \right\rangle \,\, \Leftrightarrow p(1)^{1 + a_1} \times p(2)^{a_2 + 1} \times \cdots \times p(n)^{a_n + 1}$ （ $p(k)$ 为第 $k$ 个素数）
- Cantor Numbering
  - 长度有限的字符串，都可视作 $d = 1 + \left\vert \Sigma \right\vert$ 进制的自然数
  - 长度无限的字符串，都可视作 $[0, 1)$ 内的 $d$ 进制小数
串亦为数
- 每个字符串对应一个 $d$ 进制自然数（指纹）
- $P$ 在 $T$ 中出现仅当 $T$ 中某一子串的指纹与 $P$ 的指纹相等
- 如果 $\left\vert \Sigma \right\vert$ 很大，指纹的计算与比对，将不能在 $O(1)$ 时间内完成
散列压缩
- 通过散列，将指纹压缩至存储器支持的范围
- 但 hash() 相等时，还须进一步严格比对
  - 不过，只要散列函数选取得当，便可将冲突的概率控制在 可以接受 的范围
- 可以在 $O(1)$ 时间内，由上一指纹得到下一指纹
字宽
- 可以在 $O(r = \log n)$ 时间内计算出 ${\rm power}(n) = a^n$
- $a^n$ 的二进制展开宽度为 $\Theta(n)$
- 常数代价准则、对数代价准则

排序

快速排序

分而治之

pivot，轴点： $\max[lo, mi) \le [mi] \le \min(mi, hi)$
前缀、后缀各自（递归）排序之后，原序列自然有序

template<typename T> void Vector<T>::quickSort(Rank lo, Rank hi) {
    if (hi - lo < 2) return;
    Rank mi = partition(lo, hi); // 尽可能高效
    quickSort(lo, mi);
    quickSort(mi + 1, hi);
}

划分后，轴点必然已经就位
- 一个序列有序， 当且仅当 所有元素皆为轴点
- 快速排序，即为 将所有元素转化为轴点 的过程

快速划分：LUG

任取一个候选者
- $L + U + G$
交替向内移动 lo 和 hi ，并逐个检查当前元素
- 若更小/大，则转移归入 L/G
lo == hi 时，将候选者嵌入 L、G 之中，即成轴点

template<typename T> Rank Vector<T>::partition(Rank lo, Rank hi) {
    swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);
    T pivot = _elem[lo];
    while (lo < hi) {
        do { hi--; } while (lo < hi && pivot <= _elem[hi]);
        if (lo < hi) _elem[lo] = _elem[hi];
        do { lo++; } while (lo < hi && _elem[lo] <= pivot);
        if (lo < hi) _elem[hi] = _elem[lo];
    }
    _elem[hi] = pivot; return hi; // 候选轴点归位, 返回其秩
}

线性时间：lo 、hi 累计移动距离不超过 $O(n)$
就地：只需 $O(1)$ 附加空间
不稳定

空间复杂度

空间复杂度 $\sim$ $\sim$ 递归深度
- 最好 $O(\log n)$ ，最坏 $O(n)$ ，平均 $O(\log n)$

迭代化+贪心

#define Put(K, s, t) { if (1 < (t) - (s)) { K.push(s); K.push(t); } }
#define Get(K, s, t) { t = K.pop(); s = K.pop(); }
template<typename T> void Vector<T>::quickSort(Rank lo, Rank hi) {
    Stack<Rank> Task; Put(Task, lo, hi);
    while (!Task.empty()) {
        Get(Task, lo, hi); Rank mi = partition(lo, hi);
        if (mi - lo < hi - mi) {
            Put(Task, mi + 1, hi);
            Put(Task, lo, mi);
        } else {
            Put(Task, lo, mi);
            Puts(Task, mi + 1, hi);
        }
    }
} // 大/小任务优先入/出栈, 可保证(辅助栈)空间不过 O(logn)

可归纳假设证得，所需空间不超过 $O(\log n)$ $O (lo g n)$
- 如果采用递归方式对顺序表进行快速排序，递归次数和递归深度与每次划分后得到的分区的处理顺序无关（即每次先处理 较长或较短 的分区）

时间性能

最好：每次划分都（接近）平均
- $T(n) = 2 \cdot T((n - 1) / 2) + O(n) = O(n \log n)$
最坏：每次划分都极不均衡
- $T(n) = T(n - 1) + T(0) + O(n) = O(n^2)$
采用随机选取、三者取中之类的策略，只能降低最坏情况的概率

递归深度

好轴点：落在宽度为 $\lambda \cdot n$ 的居中区间
递归深度（常规随机）：
- 最坏情况 $\Omega(n)$ ，概率极低
- 平均情况递归 $O(\log n)$ 层，概率极高
- 实际上，除非轴点过于侧偏，否则都会有效地缩短递归深度
断言
- 在任何一条递归路径上，好轴点不会多于 $d(n, \lambda) = \log_{\frac{2}{1 + \lambda}}n$
- 抵达 $\frac{1}{\lambda} \cdot d(n, \lambda)$ 层时，即可期望地出现 $d(n, \lambda)$ 个好轴点——从而在此之前终止递归
- 以 $\lambda = 0.5$ 估计，任何一条递归路径的长度，只有极小的概率超过 $D(n, \frac{1}{2}) = \frac{2}{\lambda} \cdot d(n, \frac{1}{2}) \approx 9.64 \cdot \log_2 n$

比较次数

递推分析

记期望比较次数为 $T(n)$ $T (n)$ ， $T(1) = 0$ $T (1) = 0$
- $\begin{aligned} T(n) &= (n - 1) + \frac{1}{n} \cdot \sum_{k = 0}^{n - 1} [T(k) + T(n - k - 1)] \\ &= (n - 1) + \frac{2}{n} \cdot \sum_{k = 0}^{n - 1}T(k)\end{aligned}$
- $n \cdot T(n) - (n + 1) \cdot T(n - 1) = 2 \cdot (n - 1)$
- $\begin{aligned} \frac{T(n)}{n + 1} = 4 \cdot \sum_{k - 2}^n \frac{1}{k + 1} - 2 \cdot \sum_{k = 2}^n \frac{1}{k} = 2 \cdot \sum_{k = 1}^{n + 1} \frac{1}{k} + \frac{2}{n + 1} - 4 \approx 2 \ln n\end{aligned}$
- $T(n) \approx 2 \cdot n \cdot \ln n \approx 1.386 \cdot n \log n$

后向分析

设 排序后 的序列为 $\{a_0, a_1, \dots, a_i, \dots, a_j, \dots, a_{n - 1}\}$
则期望的比较次数为 $\begin{aligned}T(n) = \sum_{i = 0}^{n - 2}\sum_{j = i + 1}^{n - 1} \Pr(i, j) = \sum_{j = 1}^{n - 1}\sum_{i = 0}^{j - 1} \Pr(i, j) \end{aligned}$ $T (n) = i = 0 \sum n - 2 j = i + 1 \sum n - 1 Pr (i, j) = j = 1 \sum n - 1 i = 0 \sum j - 1 Pr (i, j)$
- 即每一对 $\langle a_i, a_j \rangle$ 在排序中会做比较之概率总和
quickSort 的过程可以理解为：将所有元素转化为 pivot
- $\left\langle a_i, a_j \right\rangle$ 会做比较，当且仅当 在 $\{a_i, a_{i + 1}, \dots, a_{j - 1}, a_j\}$ 中， $a_i$ 或 $a_j$ 率先被转化 $\Rightarrow$ $\Pr(i, j) = \frac{2}{j - i + 1}$
- $\begin{aligned}T(n) = \sum_{j = 1}^{n - 1}\sum_{d = 1}^{j} \frac{2}{d + 1} \approx \sum_{j = 1}^{n - 1} 2 \cdot (\ln j - 1) \le 2 \cdot n \cdot \ln n \end{aligned}$

快速划分：DUP

// ...
while (lo < hi) {
    do {
        hi--; // 凡不大于轴点者, 皆归入 L
    } while (lo < hi && pivot < _elem[hi]);
    // ...
    do {
        lo++;
    } while (lo < hi && _elem[lo] < pivot);
    // ...
}
// ...

遇到连续的相等元素时
- lo 和 hi 会交替移动
- 使得切分点接近于 $\frac{lo + hi}{2}$
交换操作有所增加，更不稳定

快速划分：LGU

$S = [lo, hi) = [lo] + (lo, mi] + (mi, k) + [k, hi) = pivot + L + G + U$

template<typename T> Rank Vector<T>::partition(Rank lo, Rank hi) {
    swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);
    T pivot = _elem[lo]; Rank mi = lo;
    for (Rank k = lo + 1; k < hi; k++)
        if (_elem[k] < pivot)
            swap(_elem[++mi], _elem[k]);
    swap(_elem[mi], _elem[lo]); // 轴点归位
    return mi;
}

选取

k-selection ：在任意一组可比较大小的元素中，找出其对应非降排序序列 $S$ 中的 $S[k]$

众数

无序向量中，若有 一半以上 元素同为 $m$ ，则称之为众数
必要性：众数若存在，则其必是中位数
- 若能找出中位数，则不难验证是否为众数
时间 $O(n)$ $O (n)$ 、附加空间 $O(1)$ $O (1)$ 的算法：减而治之
- 若在向量 $A$ $A$ 的前缀 $P$ $P$ 中， $x$ $x$ 出现的次数恰占半数，则 $A$ $A$ 有众数，仅当对应的后缀 $A - P$ $A - P$ 有众数 $m$ $m$ ，且 $m$ $m$ 就是 $A$ $A$ 的众数
  - 若 $x = m$ ，则在排除前缀 $P$ 后， $m$ 与其他元素在数量上的差距 保持不变
  - 若 $x \ne m$ ，则在排除前缀 $P$ 后， $m$ 与其他元素在数量上的差距 不致缩小
- 若将众数的标准从“一半以上”改作“至少一半”
  - 则可以按照以上思路循环两次，以避免算法最后返回了一个错误的候选
  - 或一开始选择一个数验证、若不是则剪除该元素再执行算法（控制元素总数为奇数）

template<typename T> T majCandidate(Vector<T> A) {
    T maj;
    for (Rank c = 0, i = 0; i < A.size(); i++) {
        if (c == 0) { // 意味着前缀可以剪除
            maj = A[i]; c = 1;
        } else {
            maj == A[i] ? c++ : c--;
        }
    }
    return maj;
}

中位数

蛮力
- 排序+遍历， $O(n \log n) + O(k) = O(n \log n)$
堆
- 将所有元素组织为小顶堆，连续调用 delMin()
  - $O(n) + O(k \log n)$
- 任选 $k + 1$ $k + 1$ 个元素组织成大顶堆，遍历剩下的元素，依次 insert 并 delMax()
  - $O(k) + O(n \log k)$
- 将输入任意划分组织为 $k$ $k$ 、 $n -k$ $n - k$ 规模的大、小顶堆，交换堆顶元素直至……
  - $O(n) + O(\min(k, n - k) \log n)$
下界： $\Omega(n)$

QuickSelect

template<typename T> Rank quickSelect(T const *A, Rank n, Rank k) {
    Vector<Rank> R(n); // 索引向量
    for (Rank k = 0; k < n; k++) R.insert(k);
    for (Rank lo = 0, hi = n; ; ) { // 反复做 quickPartition
        swap(R[lo], R[lo + rand() % (hi - lo)]);
        T pivot = A[R[lo]]; Rank mi = lo;
        for (Rank i = lo + 1; i < hi; i++) {
            if (A[R[i]] < pivot)
                swap(R[++mi], R[i]);
        }
        swap(R[lo], R[mi]);
        if (mi < k) lo = mi + 1; // 猜小了, 剪除前缀
        else if (k < mi) hi = mi;
        else return R[mi];
    }
}

记期望比较次数为 $T(n)$ $T (n)$ ， $T(1) = 0$ $T (1) = 0$
- $\begin{aligned} T(n) &= (n - 1) + \frac{1}{n} \cdot \sum_{k = 0}^{n - 1} \max\{T(k), T(n - k - 1)\} \\ &\le (n - 1) + \frac{2}{n} \cdot \sum_{k = n / 2}^{n - 1}T(k)\end{aligned}$
- $T(n) < 4 \cdot n \rightarrow T(n) = O(n)$ $T (n) < 4 \cdot n \to T (n) = O (n)$
  - $\begin{aligned} T(n) \le (n - 1) + \frac{2}{n} \cdot \sum_{k = n / 2}^{n - 1} 4k \le (n - 1) + 3n < 4n\end{aligned}$

LinearSelect

linearSelect(A, n, k)
- 对于小数组（ $\left\vert A \right\vert < Q$ ），直接排序解决
  - $O(1)$
- 将 $A$ 分为 $n / Q$ 组，每组排序、找中位数
  - $O(n)$
- 调用 linearSelect() 找出这 $n / Q$ 个中位数的中位数 $M$
  - $T(n / Q)$
- 以 $M$ 为枢轴，将原数组 $A$ 分为三组： $L, E, G$
  - $O(n)$
- 根据 $k$ 的位置，决定在哪一组里继续递归查找
  1
  2
  3
  if (k < |L|) return linearSelect(A, |L|, k);
  if (k < |L| + |E|) return M
  return linearSelect(A + |L| + |E|, |G|, k - |L| - |E|)
  - $T(3n / 4)$
复杂度 $T(n) = c \cdot n + T(n / Q) + T(3n / 4)$
- 取 $Q = 5$ ， $1 / Q + 3 / 4 < 1$ 时， $T(n) = O(n)$
- 线性，但常数较大

希尔排序

框架

ShellSort：将整个序列视作一个矩阵，逐列各自排序
- 递减增量
  - 由粗到细，重排矩阵，使其更窄，再次逐列排序 h-sorting
  - 如此往复，直至矩阵变为一列 1-sorting
- 步长序列：由各矩阵宽度逆向排列而成的序列
  - $\mathcal{H} = \{h_1 = 1, h_2, \dots, h_k, \dots\}$
  - $A[k] = B[k / h][k \% h]$
- 正确性：最后一次迭代，等同于全排序
- 一个 g-ordered 序列在 h-sorted 之后仍保持 g-ordered
- 一个序列同时保持 g-ordered 和 h-ordered 称为 (g, h)-ordered ，此时对任意 $m, n \in N_+$ 也必然满足 (mg + nh)-ordered
- 对任意互素 $p, q \in N_+$ ，(p, q)-ordered 序列中逆序对的间距不大于 $(p - 1) \times (q - 1)$

template<typename T> void Vector<T>::shellSort(Rank lo, Rank hi) {
    for (Rank d = 0x7FFFFFF; d > 0; d >>= 1) // PS Sequence
        for (Rank j = lo + d; j < hi; j++) {
            T x = _elem[j]; Rank i = j;
            while (lo + d <= i && x < _elem[i - d])
                _elem[i] = _elem[i - d], i -= d;
            _elem[i] = x; // 找到 [j] 插入位置
        }
}

最好情况 $O(n)$ ，就地，不稳定

Shell 序列

Shell’s Sequence

$\mathcal{H}_{shell} = \{1, 2, 4, 8, \dots, 2^k, \dots\}$
最坏情况下 $\Omega(n^2)$ $Ω (n^{2})$
- 考查子序列 $A = {\rm unsorted}[2^{N - 1}, 2^N)$ 和 $B = {\rm unsorted}[0, 2^{N - 1})$ 交错而成的序列
- 进行 1-sorting 时仍有很多逆序对
根源在于， $\mathcal{H}_{shell}$ 中各项并不互素，相邻项也非互素

PS’s Sequence

$\mathcal{H}_{PS} = \mathcal{H}_{shell} - 1 = \{2^k - 1 \,\,|\,\, k \in N\} = \{1, 3, 7, 15, 31, \dots\}$ $H_{P S} = H_{s h e l l} - 1 = {2^{k} - 1 ∣ k \in N} = {1, 3, 7, 15, 31, \dots}$
- 相邻项互素
时间复杂度 $O(n^{3 / 2})$ $O (n^{3 / 2})$
- 平均为 $O(n^{5 / 4})$ （通过模拟得出）

Pratt’s Sequence

$\mathcal{H}_{pratt} = \{2^p \cdot 3^q \,\, | \,\, p, q \in N\} = \{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, \dots\}$
时间复杂度 $O(n \log^2 n)$

Sedgewick’s Sequence

$\mathcal{H}_{Sedgewick} = \{9 \times 4 ^k - 9 \times 2^k + 1 \,\, | \,\, k \ge 0\} \cup \{4^k - 3 \times 2^k + 1 \,\, | \,\, k \ge 2\}$ $H_{S e d g e w i c k} = {9 \times 4^{k} - 9 \times 2^{k} + 1 ∣ k \geq 0} \cup {4^{k} - 3 \times 2^{k} + 1 ∣ k \geq 2}$
- PS 和 Pratt 的结合
最坏复杂度 $O(n^{4 / 3})$ $O (n^{4 / 3})$ ，平均 $O(n^{7 / 6})$ $O (n^{7 / 6})$
- 实践性能最佳