期中考 cheat sheet
前言
自用复习文档。
1 AVL Trees, Splay Trees and Amortized Analysis¶
1. 1 AVL Trees¶
- AVL 树的最小节点数 \(n_h\) 和树高 \(h\) 的关系：
\[
n_h = \begin{cases} n_{h-1} + n_{h-2} + 1 & \text{if } h > 1 \\ 2 & \text{if } h = 1 \\ 1 & \text{if } h = 0 \end{cases}
\]
- 插入操作盯着高度转，寻找离插入点最近的
trouble finder，\(\text{LL/RR}\) 转一次，\(\text{LR/RL}\) 转两次，旋转的趋势都是转上去
1. 2 Splay Trees¶
- 插入操作盯着访问节点转，\(\text{Parent}\) 是根节点就转一次，否则分为两种情况，如果是 \(\text{zig-zig}\) 即三者位于一条直线上，则将直线颠倒向另一个方向，如果是 \(\text{zig-zag}\) 即三者不在一条直线上，则形似双旋，让 \(\text{X}\) 转到最上面
- \(M\) 次操作（增删查改）的摊还复杂度为 \(O(M \log N)\)
2 Red-Black Trees and B+ Trees¶
2. 1 Red-Black Trees¶
- 对于任意节点 \(x\)，\(\text{sizeof}(x) \geq 2^{\text{bh}(x)} - 1\)，\(\text{bh}(\text{Tree}) \geq \frac{h(\text{Tree})}{2}\)
- 一棵有 \(N\) 个内部节点的红黑树，NIL 叶节点的个数为 \(N+1\)，高度至多为 \(2 \log (N+1)\)
| 旋转次数 | AVL Tree | Red-Black Tree |
|---|---|---|
| Insertion | \(≤ 2\) | \(≤ 2\) |
| Deletion | \(O(\log N)\) | \(≤ 3\) |
| 插入情况 | Parent 节点颜色 | Uncle 节点颜色 | 操作 |
|---|---|---|---|
| / | 红 | 红 | \(P\) 和 \(U\) 染黑，\(G\) 染红 |
| \(\text{LR}\) | 红 | 黑 | 调整 \(N\) 与 \(P\) 的位置 |
| \(\text{LL}\) | 红 | 黑 | 调整 \(P\) 和 \(G\) 的位置并互换颜色 |
| 删除情况 | 操作 |
|---|---|
| 被删除节点为红色且无孩子 | 直接删除 |
| 被删除节点为黑色且有一个孩子 | 孩子必为红色，用该孩子替代被删除节点的位置并着黑色 |
| 被删除节点颜色任意且有两个孩子 | 用succesor的值替代被删除的节点的值并保持颜色不变， 然后将用于替代的节点从原来的位置中删除，转换为其他情况 |
| 被删除节点为黑色且无孩子 | 将该节点删除后用一个双黑节点替代它，然后进行平衡维护 |
| 平衡维护情况 | 操作 |
|---|---|
| 兄弟节点 \(S\) 为红色 | 调整 \(S\) 和 \(P\) 的位置并互换颜色，转换为其他情况 |
| 兄弟节点 \(S\) 为黑色且有同向（\(\text{LL}\) 或 \(\text{RR}\)）红色孩子 | 调整 \(S\) 和 \(P\) 的位置并互换颜色，并将红色孩子染黑 |
| 兄弟节点 \(S\) 为黑色且有异向（\(\text{LR}\) 或 \(\text{RL}\)）红色孩子 | 调整孩子和 \(S\) 的位置，转换为上一种情况 |
| 兄弟节点 \(S\) 为黑色且无红色孩子 | 染红 \(S\)，黑色上递至 \(P\)，转换为其他情况 |
2. 2 B+ Trees¶
- 所有非叶子节点（除了根节点）有 \(y \in [\lceil \frac{M}{2} \rceil, M]\) 个孩子
- B+ 树是自底向上构建的，所有的叶子位于相同深度的位置上
- 对于一棵有 \(N\) 个数据的 \(M\) 阶 B+ 树：
- 深度 \(\text{Depth}(M,N) = O(\lceil \log_{\lceil \frac{M}{2} \rceil} N \rceil)\)
- 插入时间 \(T(M,N) = O(\frac{M \cdot \log N}{\log M}) = O(M \log_M N)\)，所以阶数 \(M\) 不是越大越好，最合适的取值为 \(3\) 或 \(4\)
- 查找时间 \(T_{\text{Find}}(M,N) = O(\log N)\)
4 Leftist Heaps and Skew Heaps¶
左偏堆¶
- 对于一个左偏堆，如果它右侧的路径上有 \(r\) 个节点（即根节点的空指针路径长度为 \(r−1\)），那么它至少有 \(2^r−1\) 个节点
斜堆¶
- 在最坏情况下，斜堆所有操作（合并、插入、删除最小值等）的时间复杂度均为 \(O(N)\)，但摊还复杂度都是 \(O(logN)\)
二项队列¶
- 在一个二项队列中，在偶数深度的节点数不小于在奇数深度的节点数（假定根节点的深度为 0）
- 二项队列将所有子树的根节点存储在数组中（索引为二项树的阶数），使用Left-child-next-sibling结构维护二项树，并按降序维护子树
分治法¶
- 对于递推关系 \(T(N) = aT\left(\frac{N}{b}\right) + \Theta(N^k \log^p N)\)，其中 \(a \geq 1, b > 1, k \geq 0\)，\(p\) 为任意实数，那么：
- 若 \(a > b^k\)，则 \(T(N) = \Theta(N^{\log_b a})\)
- 若 \(a = b^k\)，则
- 若 \(p > -1\)，\(T(N) = \Theta(N^k \log^{p+1} N)\)
- 若 \(p = -1\)，\(T(N) = \Theta(N^k \log \log N)\)
- 若 \(p < -1\)，\(T(N) = \Theta(N^k)\)
- 若 \(a < b^k\)，则
- 若 \(p \geq 0\)，\(T(N) = \Theta(N^k \log^p N)\)
- 若 \(p < 0\)，\(T(N) = \Theta(N^k)\)