Chapter 1. AVL&Splay Tree

AVL树

• 如果一个树的左右子树的高度差不超过1，那么这个树是高度平衡的
• AVL树的平衡因子是左子树高度减去右子树高度

RR和RL旋转

记从下到上第一个不平衡的节点为p,该节点的左节点为$p_L$,右节点为$p_R$，右节点的左孩子为$p_{RL}$

RR旋转，将$p$旋转为$p_R$的左孩子

RL旋转，先将$p_R$旋转为$p_{RL}$的右孩子，然后将$p$旋转为$p_{RL}$的左孩子

最少节点数

如果$n_h$是一个高度为$h$的AVL树的最少节点，那么$n_h$满足

$$n_h=n_{h-1}+n_{h-2}+1\\ n_h = F_{h+2}-1\\ h=O(\ln{n})$$

可以发现树的高度有一个对数上界

Splay树

splay树的目标是要让任意$M$个从空树开始的连续操作时间开销为$O(\log N)$

splay树的想法是，当一个节点被访问，那么就通过一系列树的旋转操作将这个节点移动到根节点的位置。

Zig-zag&Zig-zig

对于任意一个要访问的节点，记为$X$,其父亲节点记为 $P$，祖父节点记为$G$.

当节点$X$位于祖父节点的左儿子的右子树时记为Zig-zag，对于右边的定义对称可得。当节点$X$位于祖父节点的左儿子的左子树时，记为Zig-zig

Zig-zig

先将$G$旋转为$P$的孩子，然后将$P$旋转为$X$的孩子

Zig-zag

先将$P$旋转为$X$的孩子，然后将$G$旋转为$X$的孩子

splay树伸展的过程，不仅会将访问的节点移到根节点，同时还将路径上的大部分节点的深度减半。

删除节点

1. 访问要删除的节点$X$
2. 删除移动到根节点的节点$X$，剩下左右子树分别为$T_L$和$T_R$
3. 访问左子树的最大值（或右子树的最小值），该节点一定没有右子树，所以移动到根节点后可以直接将原来的右子树插入到这个节点
4. 将$T_R$插入为根节点的右子树

splay树的摊还分析

定义势能函数$\Phi(D_i)$

$$\Phi(D_i)=\sum_{i\in T}\log S(i),S(i)\text{是}i\text{节点和其所有后代的个数}$$

定理

$$\text{伸展一棵树的摊还时间，最多为}O(\log N)$$

Chapter 2. Red-Black&B+ Trees

红黑树

红黑树的性质

• 每一个节点要么是红色要么是黑色
• 根节点是黑色
• 每一个叶子节点（哨兵节点）是黑色
• 如果一个节点是红色，那么他的孩子节点一定是黑色
• 每一个节点到其后代的叶子节点的路径包含数量相同的黑色节点

任意一个节点的黑高（bh），是该节点到叶子结点的路径所包含的黑色节点的数量。

定理1:

$$N\text{个节点的红黑树，黑高最多为}2\ln(N+1)$$

定理2：

$$\text{bh(Tree)}\geq\text{h(Tree)}/2$$

插入

默认插入节点的颜色是红色

有下面这几种情况

• 插入节点后为根节点

• 插入节点父节点为黑色

• 插入节点父节点为红色（假设父节点是祖父节点的左孩子，为右孩子的情况对称可得）

  • 为父节点的左孩子

    • 父节点的兄弟节点为红色

      将祖父节点的黑色转移到父节点和叔叔节点，然后对祖父节点进行维护

    • 父节点的兄弟节点为黑色

      将父节点染黑，祖父节点染红，父节点旋转到祖父节点的位置

  • 为父节点的右孩子

    先进行旋转，让父节点成为自己的左孩子，自己成为原来的父节点的位置

插入操作的时间复杂度为

$$T=O(h)=O(\ln N)$$

删除

删除一个节点的问题都可以转移到删除叶子节点的问题，如果要删除的叶子节点为红色，可以直接删除，如果为黑色，那么就要对黑高进行维护

如果删除的节点为黑色，记为$X$

• $X$只有一个左孩子或右孩子：孩子节点代替$X$后变黑
• $X$没有孩子
  • 兄弟节点为黑色
    • 兄弟至少有一个红色孩子
      • 兄弟红色孩子与兄弟节点朝向一样（LL或RR）:红色孩子染色为兄弟节点的颜色，兄弟节点染色为父节点颜色，父节点染为黑色，兄弟节点旋转成为父节点
      • 兄弟红色孩子与兄弟节点朝向不一样（LR或RL）:红色孩子节点染色为兄弟节点的父节点，兄弟节点的父节点染色为黑色，然后将变成黑色节点的孩子节点旋转到兄弟节点的位置，再将该孩子节点旋转到原来兄弟节点的父节点的位置
    • 兄弟的孩子全为黑色：将兄弟节点变红，双黑上移
  • 兄弟节点为红色：兄弟节点和父节点交换颜色，兄弟节点旋转到原来父节点的位置，然后继续进行黑色节点的维护

B+树

M阶B+树的性质

1. 根节点要么是叶子要么孩子数量在2到M之间
2. 除了根节点的所有非叶子节点孩子数都在$\lceil M/2\rceil$到$M$之间，并且键的个数为孩子个数-1
3. 所有叶子有相同的深度

删除

如果删除导致节点下溢出，那么先看该节点的左右节点是否能将元素移入该节点，如果不行，那么父节点就进行合并。

Chapter 3. Inverted File Index

从一系列文本文件中，我们将每一个单词出现的频率以及其对应的出现的位置进行统计，得到倒排索引文件

term

Word Stemming: 提取词干，将一个词的多种形式归纳到词根

Stop Words：对一些高频使用但是意义不大的词进行忽略

Distributed indexing

• term-partitioned index
• document-partitioned index

Dynamic indexing:

文件是动态添加的，对于添加的新文件，我们需要将新的索引插入到字典中，对于原来已有的索引我们需要进行更新

采用主索引（Main Index）和辅助索引（auxiliary index），当新文件添加时，只在辅助索引当中进行更新，进行搜索时，对主索引和辅助索引都进行查询，在辅助索引到达一个阈值或者系统空闲的时候，再进行更新。

compression

对于数据的储存，如果我们将每一个数据唯一对应一个id，那么当数据量很大的时候，id所占据的物理空间就会很大。通过储存两个相邻索引的差值，这样可以对储存所占据的内存进行压缩。

Thresholding:阈值处理

• Document：将文件按权重排序，只返回前$x$个文件
• Query：将query的单词按频率进行排序，只根据原始query的一些词进行搜索

precision&recall

$$P=R_R/(R_R+I_R)\\ R=R_R/(R_R+R_N)$$

Chapter 4. Leftist Heaps & Skew Heaps

Leftist Heaps

定义

null path length是从一个节点到叶子结点的最短路径，空节点的npl记为-1

$$\text{Npl(X)}=\text{min{Npl(C)+1 for all C as children of X}}$$

左倾堆的每一个节点都满足，其左孩子的npl至少和其右孩子的npl相等。

定理

$$\text{一个右节点路径上有r个节点的左倾树至少有}2^r-1\text{个节点}$$

复杂度

• Merge操作的时间复杂度为$O(\log N)$
• DeleteMin操作的时间复杂度为$O(\log N)$

Skew Heaps

为了实现$M$个连续操作至多花费$O(M\log N)$

每一次merge的时候都对左右子树进行交换

note：

1. 斜堆相比于左倾堆，不需要维护npl并且也不需要检查是否需要交换左右孩子
2. 精确的计算左倾堆和斜堆的右节点路径的期望值是一个开放性问题

斜堆的摊还分析

插入和删除都是merge操作，摊还分析可以得到时间复杂度为

$$T_{\text{amortized}}=O(\log N)$$

势能函数定义为树中重节点的数量

重节点的定义为：如果以一个节点右子树的节点数量超过这个树的节点数量的一半，那么就为重节点。反之为轻节点。

Chapter 5. Binomial Queue

二项队列是一系列二项树组成的森林

从空堆插入$N$个节点建堆的时间开销是$O(N)$，而斜堆和左倾堆插入的时间开销是 $O(\log N)$，二项队列就是为了实现常数时间开销的插入。

二项队列可以按照二进制的形式，唯一地表示任意整数。

二项队列是通过$\text{left-child next-sibling}$的结构来实现的

时间复杂度

• $\text{FindMin}=O(\log N)$
• $\text{Merge}=O(\log N)$
• $\text{Insert}=O(1)，N次连续的插入操作时间开销为O(N)$

Chapter 6. Backtracking

• 八皇后问题

• $\text{The Turnpike Reconstruction Problem}$

• $\alpha-\beta\text{ pruning}$

  $\alpha-\beta$剪枝法能保证搜索的节点上界为$O(\sqrt N)$

Chapter 7. Divide and Conquer

• 最近点问题

• 解递推方程

  • 替换法
  • 递归树法
  • 主定理法

Chapter 8. Dynamic Programming