第 1 周：AVL 树、Splay 和摊还分析¶
AVL 树¶
众所周知的是，简单的二叉查找树可以被随随便便卡成链。为了达成 \(O(\log n)\) 的查询复杂度，我们需要对这棵树重新进行一些设计……
换句话说，我们得把这棵树转一转。
定义¶
- 左子树的高度减去右子树的高度叫做“平衡因子”（Balance Factor，BF）。
- 平衡因子的绝对值必须在 1 以内；也就是说取值范围是 -1、0 和 1。
转转转！¶
AVL 树有两种“转”的方法，它们会改变树的结构。
RR 翻转和 LL 翻转¶
现在有 A 和 B 两个节点，B 是 A 的右子节点。
此时，当 A 的 BF 为 -2， B 的 BF 为 -1，这个时候我们得想办法维持 AVL 树的结构。
那么就让 B 往上移一层，A 当成 B 的左子节点，而 B 原来的左子节点就把 A 原来的右子节点接上去。
因为是（A 的）右节点的右节点出了问题，所以这叫做 RR 翻转。
LL 翻转就是镜像一下。
LR 翻转和 RL 翻转¶
现在有 A、B 和 C 三个节点，B 是 A 的左子节点，C 是 B 的右子节点。
此时，当 A 的 BF 为 2，B 的为 -1，C 的为 1：我们把 C 往上移两层，让它左子节点是 B，右子节点是 A；B 原来的右子节点接上 C 原来的左子节点，A 原来的左子节点接上 C 原来的右子节点。
因为是（A 的）左节点的右节点出了问题，所以这叫做 LR 翻转。
RL 翻转就是镜像一下。
结点最少的 AVL 树¶
\(n_h = n_{h - 1} + n_{h - 2} + 1\)，其中 \(n_h\) 是高度为 h 的结点最少的 AVL 树的结点数。
伸展树 Splay¶
DNA 动了！
Splay 是个均摊复杂度是 \(O(\log n)\) 的树结构。
所以 Splay 搞不了持久化，否则找一个耗时巨大的操作反复横跳就把你卡了。
双旋¶
其实就是 AVL 树的翻转操作，每次把一个节点往上移两层。
Zig：没有祖父节点。
Zig-Zag：方向不同时的旋转。
Zig-Zig：方向相同时的旋转。先旋转那个节点的父亲。
单旋的那个叫 Spaly。
查找¶
顺便把那个节点旋上去，可以保证复杂度。
删除¶
比如说我们现在要把 X 删掉：
- 把 X 旋到根。
- 告诉 X 的子节点说，它们已经没有 🐎 了。
- 选择一个子节点作为新的根。至于接下来怎么把两个子树连起来，随你便。一种可行的方法如下：
- 把左子树的最大的点旋到根，此时它没有右子树。
- 把剩下的那个右子树拼过来。
摊还分析¶
均摊复杂度¶
定义成 M 次连续操作时的平均用时。（一般要求从势能为 0 的情况开始。）
有个例子：现在有个支持一次可以弹出很多个元素的栈。它每次操作的均摊复杂度是啥？\(O(n)\)？实际上是 \(O(1)\)，因为每个元素只会被弹出一次。
预支 Accounting Method¶
当有个操作的实际时间 \(c_i\) 小于算出来的均摊时间 \(\hat{c_i}\) 的时候，这个时间差 \(\hat{c_i} - c_i\) 可以看成是对之后的那些很慢的操作的“预支”（Credit）。
势能 Potential Method¶
定义 x 的势能函数 \(\Phi(x)\)：操作的实际时间小于算出来的均摊时间的时候，会累积这个势能函数。也就是说：\(\hat{c_i} = c_i + \Phi(x) - \Phi(x_\mathrm{before})\)。势能会在那些很慢的操作中起效。
对 Splay 的摊还分析¶
\(D_i\) 是结果树的根。
\(\Phi(D_i) = \sum \log S(i)\)，\(S(i)\) 是 i 这棵子树的节点个数（包括它自己）。
对于 Zig 操作：现在有结点 X 和它的父结点 P。\(R_1\) 是操作前的状态，\(R_2\) 是操作后的状态。
\(\hat{c_i} = 1 + R_2(X) - R_1(X) + R_2(P) - R_1(P) \leq 1 + R_2(X) - R_1(X)\)，因为 P 子树大小变小了。
对于 Zig-Zag 操作：现在有结点 X 和它的父结点 P，以及祖父节点 G。
\(\hat{c_i} = 2 + R_2(X) - R_1(X) + R_2(P) - R_1(P) + R_2(G) - R_1(G) \leq 2 (R_2(X) - R_1(X))\)。
此处有个定理：\(a + b \leq c \to 2 + \log a + \log b \leq 2 \log c\)。
对于 Zig-Zig 操作：现在有结点 X 和它的父结点 P，以及祖父节点 G。
\(\hat{c_i} = 2 + R_2(X) - R_1(X) + R_2(P) - R_1(P) + R_2(G) - R_1(G) \leq 3 (R_2(X) - R_1(X))\)。
于是均摊时间是 \(3(R(T) - R(X)) + 1 = O(\log N)\)。