算法导论-第三部分-读书笔记

朱雀 2022-05-31 13:50 277阅读 0赞

# 第十一章 散列表（哈希表） #

## 11.1 直接寻址表 ##

什么是直接寻址表？  
就是用一个数组，数组的每个位置都保存一个元素。每个数组的位置称作“槽(slot)”。下图描绘了一个直接寻址表，槽 k 指向集合中的一个“关键字”为 k 的元素。如果该集合中没有关键字为 k 的元素，则 T\[k\] = NIL。  
![这里写图片描述][SouthEast]

特点：  
最大复杂度：O(1)  O ( 1 )   
最小复杂度 ：O(1)  O ( 1 )   
排序空间使用：- （无排序）  
使用条件：全域 U 不能很大  
使用场景：todo  
是否稳定：是

## 11.2 散列表 ##

直接寻址技术的缺点是非常明显的：如果全域 U 很大，则在一台标准的计算机可用内存容量中，存储一大小为 U 的一张表可能不太实际。还有，有时候实际存储的关键字集合 K 相对 U 来说可能很小，很多空间都浪费掉了。

在散列方式下，该元素存放在槽 h(k) 中，即利用“散列函数(hash function) h ”，由关键字 k 计算出槽的位置。函数 h 将关键字的全域 U 映射到散列表（hash table）T\[0…m-1\]的位置上。h(k) 的值，称作关键字 k 的“散列值”。

![这里写图片描述][SouthEast 1]

这种方式存在一个问题：两个关键字可能映射到同一个槽中。我们称这种情形为“冲突（Collision）”。我们可以找到有效的办法来解决这个问题：链接法（chaining）和开放导址法（open addressing）。

### 链接法（chaining）： ###

在链接法中，把在同一个槽中的元素，放在一个链表中存储。  
下面的例子中，链表是一个双向链表，这样“插入”和“删除”操作，可以在 O(1) 时间内完成。  
![这里写图片描述][SouthEast 2]

如果散列表中“槽数”至少与“表中的元素数”成正比的话，则全部的字典操作平均情况下都可以在 O(1) 时间内完成。

特点：  
最大复杂度：O(n)  O ( n )   
最小复杂度 ：O(1)  O ( 1 )   
排序空间使用：-（不排序）  
使用条件：todo  
使用场景：todo  
是否稳定：否  
其它：散列表中“槽数”至少与“表中的元素数”成正比的话，则全部的字典操作平均情况下都可以在 O(1) 时间内。

## 散列函数 ##

### 好的散列函数的特点 ###

每个关键字都被“等可能地”散列到 m 个槽位中，并且与其它关键字散列到哪个槽位无关。

一种好的方法导出的散列值，在某种程度上应独立于数据可能存在的任何模式。例如，“除法散列”用一个特定的素数来除所给的关键字，所得的余数即为该关键字的散列值。假定所选择的素数与关键字分布中的任何模式都是无关的，这种方法常常可以给出好的结果。

### 将关键字转换为自然数 ###

如果所给的关键字不是自然数，就需要找到一种方法来将他们转换成为自然数。例如： pt 对应的十进制数为（112, 116），然后以 128 为基数来表示，则为 112 \* 128 + 116 = 14452。在特定的场合，通常还能设计出其他类似的方法，将每个关键字转换为一个（可能是很大的）自然数。

### 11.3.1 除法散列法 ###

什么是除法散列法？  
通过取 k 除以 m 的余数，将关键字 k 映射到 m 个槽中的某一个上，即散列函数为：h(k) = k mod m。由于只需作一次除法操作，所以除法散列法还是非常快的。  
例如，如果散列表的大小为 m=12，所给的关键字为 k=100，则 h(k)=4，把 k 放到第4个槽位上。

下面的内容请注意：  
当使用除法散列时，要避免选择 m 的某些值，例如，m 不应该为 2 的幂，如果 m=2p  m = 2 p ，而 h(k) 就是 k 的 p 个最低位数字。除非已知各种最低 p 位的排列形式为等可能的，否则在设计散列函数时，最好考虑关键字的所有位。（原文一部分：When using the division method, we usually avoid certain values of m. For example, m should not be a power of 2, since if m=2p  m = 2 p , then h(k) is just the p lowest-order bits of k.）

此处翻译的不是很好理解，感觉`lowest-order bits of k`没有翻译好。这句话到底是什么意思？  
例如：  
我们现在有3个数，m=23=8  m = 2 3 = 8 ，下面我们进行看一下这3个数对 8 进行取模后的结果：

<table> 
 <thead> 
  <tr> 
   <th>原数</th> 
   <th>原数的二进制</th> 
   <th>8的二进制</th> 
   <th>mod 8的商的二进制</th> 
   <th>mod 8 的余数的二进制</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>13</td> 
   <td>0000 1101</td> 
   <td>0000 1000</td> 
   <td>0000 0001</td> 
   <td>0000 0101</td> 
  </tr> 
  <tr> 
   <td>29</td> 
   <td>0001 1101</td> 
   <td>0000 1000</td> 
   <td>0000 0011</td> 
   <td>0000 0101</td> 
  </tr> 
  <tr> 
   <td>61</td> 
   <td>0011 1101</td> 
   <td>0000 1000</td> 
   <td>0000 0111</td> 
   <td>0000 0101</td> 
  </tr> 
 </tbody> 
</table>

从上面的结果可以看出来，对于23=8  2 3 = 8 取模的话，就是取“一个数的二进制的最低几位”（这是是最后3位）。对于其它的 2p  2 p  也是一样的，例如：22  2 2 (0000 0100)，24  2 4 (0001 0000) ……  
2p  2 p  的最低位都是 0，所以对 2p  2 p  取模就等于就是把 k 截断保留低位的 p 位。除非已知各种最低 p 位的排列形式为等可能的，否则这种方式是很糟糕的。2p−1  2 p − 1  也是一个糟糕的选择，因为 k 的各字符不会改其散列值（这个还没有看如何证明）。  
参考：

*  [为什么Hash函数 H(k) = k % m中 m 尽量不要为2的幂次 也不是要是2^i -1][Hash_ H_k_ _ k _ m_ m _2_ _2_i -1]
 *  [Need help understanding Division Method for constructing a hash function][]

一个不太接近 2 的整数幂的素数，常常是 m 的一个较好的选择。例如，假定我们要分配一张散列表并用链接法解决冲突，表中大约要存放 n=2000 个字符串，其中每个字符有 8 位。如果我们不介意一次查找需要平均检查 3 个元素，这样分配散列表的大小为 m=701。选择 701 这个数的原因是：它是一个接近 2000/3 但又不接近 2 的的任何次幂的素数。把这个关键字 k 视为一个整数，则散列函数为：`h(k) = k mod 701`

下面是为何使用素数的解释：

*  [为什么求模运算要用素数（质数）—— 哈希表设计][Link 1]：这里的原因感觉有些道理。如果使用 8 这样的偶数的话，4这一列，4、12、20、28，这些哈希映射在同一个格子里的数都是前一个数+8，然后他们都能被2和4整除，这样就导致他们之间有很强烈的关系，很容易发生哈希冲突。如果我们把 4 这一列再进行散列化的话，这一列的数很容易发生冲突，例如，再进行 mod 4 的话，他们全都会到一个格子里；但如果进行 mod 5(素数) 的话，结果是 \{4, 2, 0, 3\}，可见素数的作用。
 *  [Why do hash functions use prime numbers?][Why do hash functions use prime numbers]

### 11.3.2 乘法散列法 ###

主要思想：

*  使用关键字 k 乘上常数 `A(0<A<1)`，并提取 kA 的小数部分
 *  用 m 乘以这个值，再向下取整

散列函数为：`h(k) = ceiling( m(kA mod 1) )`。  
这里“kA mod 1”是取 kA 的小数部分，即 kA - ceiling(kA)。

乘法散列的一个优点是对 m 的选择不是特点关键，一般选择它为 2 的某个幂次（m=2p  m = 2 p ，p 为某个整数），这样可能正好使用计算机的一个字长。

关于 A 的取值，有一套算法，不是太明白。但比较理想的值为：A≈(5‾√−1)/2=0.6180339887...  A ≈ ( 5 − 1 ) / 2 = 0.6180339887...

计算方法省略。。。

### 11.3.3 全域散列法（Universal hashing） ###

什么是全域散列法？  
就是准备好一些散列函数，随机地使用散列函数，使之独立于要存储的关键字。

### 11.4 开放寻址法（Open addressing） ###

**什么是开放寻址法？**

**总体概念为：所有元素都存放在线性的散列表里，每个槽位只存放一个元素，没有链表，也没有元素存放在散列表之外。当进行散列后，那个位置有值了，就在当前位置移动一定量的位置，然后再看有没有值；如果有值就再进行移动，直到有空位置；但如果散列表满了，就无法存放了。（开放导址法有很多种，不同点在于“在当前位置移动一定量的位置”。移动多少个位置，是每种方法的不同点）。**

开放寻址法不用指针，而是计算出要存取的槽序列。不用指针而节省的空间，可以提供更多的槽，潜在地减少了冲突，提高了检索速度。但开放寻址法，散列表可能会被填满，以至于不能插入任何新的元素。该方法民到的一个结果便是装载因子 α  α  不会超过 1。（装载因子 α  α  = 数据个数 n / 槽数 m，既然是一个槽只能装一个元素，所以 n/m 不能超过1)

为了使用开放寻址法插入一个元素，需要连续地检查散列表，称为“探查(probe)”，直到找到一个空槽来旋转待插入的关键字为止。检查的顺序不一定是 0，1，…，m-1，而是依赖于待插入的关键字。为了确定要探查哪些槽，我们将散列函数加以扩充，使之包含探查号（从0开始）以作为其第二个输入参数。对于每一个关键字 k，使用开放寻址法的“探查序列(probe sequence)”：

> `<h(k,0), h(k,1), h(k,2), ...h(k, m-1) >`

例如，下面代码中散列表 T 中的元素为，无卫星数据的关键字 k，每个槽包含一个关键字，或是 NIL。HASH-INSERT 过程以一个散列表 T 和一个关键字 k 为输入，要反返回关键字 k 的存储槽位，要么返回“已满”的出错标志。  
![这里写图片描述][SouthEast 3]

HASH-SEARCH 输入为一个散列表 T 和 关键字 k，如果槽 j 中包含了关键字 k，而返回 j；如果 k 不存在，则返回 NIL。（下面的图中感觉有错误，错：h(k, j)，对：h(k, i)）。  
![这里写图片描述][SouthEast 4]  
![这里写图片描述][SouthEast 5]

在分析中，做一个“均匀散列(uniform hashing)”的假设：每个关键字的探查序列等可能为`<0, 1, ... m-1>`组成的`M!`的任意一种。如果序列内容不是全包含`<0, 1, ... m-1>`的话，有的槽位可能就访问不到。例如：

*  第 1 个数插入时，用 h(k, 1)次，即 1 次；
 *  第 2 个数插入时，用 h(k, 2) 次，即 2次。第 1 次用 h(k, 1)，但是有值了；第 2 次用 h(k, 2)，可以插入）

> 这样的话，每个数的插入，都是`M!(M的阶乘种排序中的一种)`。

散列函数的结果是一个数，但均匀散列的结果是一个完整的探查序列。例如：（这个在后面能具体地讲解，现在有个大概的印像就行）

*  k=7k=7，h′(7)=7h′(7)=7，Probing Sequence為\{7,0,1,2,3,4,5,6\}\{7,0,1,2,3,4,5,6\}
 *  k=13k=13，h′(13)=5h′(13)=5，Probing Sequence為\{5,6,7,0,1,2,3,4\}\{5,6,7,0,1,2,3,4\}
 *  k=50k=50，h′(50)=2h′(50)=2，Probing Sequence為\{2,3,4,5,6,7,0,1\}\{2,3,4,5,6,7,0,1\}
 *  k=74k=74，h′(74)=2h′(74)=2，Probing Sequence為\{2,3,4,5,6,7,0,1\}

#### 三种常用的开放导址法 ####

真正的均匀散列是非常难以实现的，在实际应用中有一些近似方法，有三种技术常用来计算开放寻址法：线性探查、二次探查、双重探查。

#### (1) 线性探查(Linear Probing) ####

就是把 h(k) 的值，再进行迭代加 i (i=0,1,2…m-1)，来探查每个槽。公式如下：  
![这里写图片描述][SouthEast 6]

在线性探查中，初始探查位置决定了整个“探查序列”。例子请看 [Hash Table：Open Addressing][Hash Table_Open Addressing] 中的 Linear Probing 部分

线性探查方法比较容易实现，但存在一个问题，称为一次群集（primary clustering）。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。这种现像很容易出现。

#### (2) 二次探查(Quadratic Probing) ####

![这里写图片描述][SouthEast 7]

二次探查的话，增加了常数 C1、C2 来增加探查序列的分散性。但要注意 C1、C2、m 的选择，并不是所有 C1、C2、m 都可以产生 \{0,1,…,m−1\} 的排列组合。此外，如果两个关键字的初始探查位置相同，那么他们的探查序列也是相同的，这一改制可导致轻度的 clustering，称为二次群集（secondary clustering）。  
例子请看 [Hash Table：Open Addressing][Hash Table_Open Addressing] 中的 Quadratic Probing 部分

#### (3) 双重散列(double hashing) ####

双重散列是用于开放寻址法的最好的方法之一，因为它所产生的排列具有随机选择排列的许多特性：  
![这里写图片描述][SouthEast 8]

其中 h1 和 h2 为辅助散列函数。然后，  
1. 第 1 次探查位置为 T\[ h1(k) \]  
2. 接下来探查的位置是：( 前一个位置 + 偏移量 h2(k) ) mod m  
3. 循环第 2 步

例如：  
![这里写图片描述][SouthEast 9]

因为 k = 14，散列表大小为13，h1(k) = k mod 13，h2(k) = 1 + (k mo 13)，所以 h1(k) = 1(14 mod 13)，h2(k) = 1 + 3(14 mod 11) = 4。  
1. 第 1 次探查 h1(k) 的结果 1。但 T\[1\] 已经有了 9，所以再进行探查。  
2. 第 2 次探查 i=1，( 1 + i \* 4 ) / 14 = 5 / 14 = 5。但 T\[5\] 已经有了 98，所以再进行探查。  
3. 第 2 次探查 i=2，( 1 + i \* 4 ) / 14 = 9 / 14 = 9。T\[9\] 没有值，所以放到了 T\[9\] 的位置。

##### 为了能查找散列表，h2(k) 的值必须与表的大小 m 互质 #####

为什么要是互质呢？这里有项神奇的事实：若 a 与 b 互质，那么 (a \* i) mod b 且 i=0,1,2…b-1，正好可以形成 \{0, 1, 2 … b-1\}的排列组合（就是置换）。

若a=5,b=8a=5,b=8，那麼：

*  i=0，(5×0=0)mod8=0
 *  i=1，(5×1=5)mod8=5
 *  i=2，(5×2=10)mod8=2
 *  i=3，(5×3=15)mod8=7
 *  i=4，(5×4=20)mod8=4
 *  i=5，(5×5=25)mod8=1
 *  i=6，(5×6=30)mod8=6
 *  i=7，(5×7=35)mod8=3

##### 如何做到 h2(k) 与 m 互质呢？ #####

有几种方法：  
1，取 m 为 2 的幂，并设计一个总产生奇数的 h2。奇数和偶数总是为互质的。  
2，取 m 为 素数，并设计一个总是返回比 m 小的正整数函数 h2。例如：h1(k) = k mod m，h2(k) = 1 + (k mod m’) 的话，m=701，可以设置 m’=700。

### 11.5 完全散列 ###

什么是完全散列？  
完全散列和链表散列有点像，只不过每个结点又一是个散列，而不是链表。例如：

![这里写图片描述][SouthEast 10]

这个完全散列表是由两个散列表组成，一个是竖的一级散列表，还有就是横向的二级散列表。把一个 k 加入到散列表中过程如下：

*  首先用 h(k) 函数算出 k 在一级散列表中的槽位
 *  再用 h(k) 公式和二级散列表中的参数，算出 k 在二级散列中的位置

例如，k=75，散列函数为 h(k)=(((a \* k + b) mod p) mod m)，且 a=3，b=42，p=101，m=9，而一级散列表的位置是：(((3 \* 75 + 42) mod 101) mod 9 = 2，所以首先把 k 放到 2 号槽位里面。接首，二级散列中有 a2、b2、m2 这三个参数，用这三个参数替换一级散列中的相应的 a、b、m 参数，则 h(k) = (((10 \* 75 + 18) mod 101) mod 9 = 7，所以把 k 放到二级散列的 7 号槽位上。

为了确保在二级散列表上不冲突，一般二级散列表的槽数 m，为保存的数据个数的平方（n2  n 2 ）。适当地选择第一级散列函数，可以将预期使用的总体空间限制为 O(n)。

# 第十二章 二叉搜索树 #

对于一棵“完全”二叉树来说，最坏操作时间为 Θ(lgn)  Θ ( l g n ) 。然而，如果这棵树是一个 n 个结点组成的线性链，操作时间为 Θ(n)  Θ ( n ) 。在12.4节中，我们将看到一棵随机构造的二叉搜索树的期望高度为O(lgn)，因此这样一棵树上的动态集合的基本操作的平均运行的时间是 Θ(lgn)  Θ ( l g n ) 。

实际上，我们并不能总是保证随机地构造二叉搜索树，然而可以设计二叉搜索树的变体，来保证基本操作具有好的最坏情况性能。第13章给出了一个这样的变形，即红黑树，它的树高为O(lgn)。第18章将介绍B树，它特别适用于二级（磁盘）存储器上的数据库维护。

## 12.1 什么是二叉搜索树 ##

二叉搜索树是一种满足下面规则的二叉树：

> 设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key<=x.key。如果y是x右子树中的一个结点，那么y.key >= x.key

简单说，就是一个结点的左子树必须小于等于该结点，一个结点的右子树要大于等于该结点。下面是图例：  
![这里写图片描述][SouthEast 11]

### 二叉搜索树和堆有什么不同呢？ ###

堆只保证上双亲结点比都子节点 大/小，不保证两个子节点中，大/小的一定在左/右。而二叉搜索树的左孩子结点 <= 右孩子结点。

### 二叉搜索树的遍历 ###

二叉树的主要遍历有 3 种：前序遍历、中序遍历、后序遍历  
前中后，是如何定义的呢？是根据一个子树的根结点的输出位置定义的，是先输出根结点还是后输出根结点。但左子树永远都是在右子树之前输出。

*  前序遍历：根结点 —> 左子树 —> 右子树 （根结点最先输出）
 *  中序遍历：左子树—> 根结点 —> 右子树 （根结点在中间输出）
 *  后序遍历：左子树 —> 右子树 —> 根结点 （根结点最后输出）

下面的程序是中序遍历：  
![这里写图片描述][SouthEast 12]  
（前序遍历：就是把第 3 行的代码，放在 1 和 2 中间；后序遍历：就是把第 3 行的代码，放在 4 之后）

这三种遍历的主要思想是：

> 要理解：每次第 n 层的递归，都是第 n + 1 层递归的根节点。例如：上图(a)中的根结点下面的 5 所在的结点，是第 1 层递归；这个结点下面的 2 和 5 结点，是第 2(1+1) 层递归。所以，想要前序输出的话，在 “n 层递归”调用“n -1层递归”之前输出，否则，只能先输出左孩子结点或右孩子结点了。

遍历的时间复杂度为：Θ(n)  Θ ( n )

## 12.2 查询二叉搜索树 ##

### 查找 ###

递归版本：  
![这里写图片描述][SouthEast 13]

非递归版本：  
![这里写图片描述][SouthEast 14]

### 最小元素 ###

因为二叉搜索树的性质：`就是一个结点的左子树必须小于等于该结点，一个结点的右子树要大于等于该结点`  
![这里写图片描述][SouthEast 15]

### 最大元素 ###

![这里写图片描述][SouthEast 16]

### 后继结点和前驱结点 ###

什么是后续结点？  
一个结点 x 的后继结点是大于 x.key 的最小关键字的结点。

什么是前驱结点？  
一个结点 x 的前驱结点是小于 x.key 的最大关键字的结点。

如何找到后继结点呢？

*  首先如果 x 结点有右子树的话，右孩子结点就是后继结点
 *  如果没有右子树的话，就要向上去找。如果 x 结点的父结点不是 NIL 并且 x 结点是父结点的右孩子 的话，就一起向上找。因为如果父结点是 NIL 的话，证明到根点；如果 x 不是它的父结点的右孩子，说明 x 是它的父结点的左孩子，左孩子 <= 父结点，所以父结点就是后继结点。  
    （如果 x 是最大结点的话，返回是 NIL。因为最后 y 的值是根结点的父结点的引用 NIL）

### 12.3 插入和删除 ###

关于插入  
插入就是使用不断和父结点比（最初的父结点就是根结点），如果小于父结点，就去左子树再进行比较；如果大于，就去右子树进行比较。直到可以比较的结点为 NIL（说明它无左/右子结点了），再用 x 结点和当前的结点比较，如果小于当前结点就放到当前结点的左孩子上，如果大于等于当前结点，就放到右孩子上。

时间复杂度为：O(h)，h为树高度

程序和图如下：  
![这里写图片描述][SouthEast 17]

关于删除  
时间复杂度为：O(h)，h为树高度

![这里写图片描述][SouthEast 18]  
![这里写图片描述][SouthEast 19]  
![这里写图片描述][SouthEast 20]

## 12.4 随机构建二叉搜索树 ##

随机构建二叉搜索树，就是把 n 个关键字按“随机次序”插入到一棵初始为空的树。  
这样的话，期望高度为 O(lgn)。

# 第十三章 红黑树（red-black tree） #

二叉搜索树高度较低时，这些集合操作会执行得较快。然后如果树的高度较高时，这些集合操作可能并不比在链表上执行得快。  
（上面的“高度较高”，应该某一侧的子树比另一侧子树高很多，造成非常不平衡的状态。如果是一个完全二叉搜索树的话，没有什么问题）

# 13.1 红黑树的性质 #

红黑树是，在二叉搜索树基础上，加了一个叫“颜色”的存储位，可以是“RED”或“BLACK”。通过“对于每个结点，从该结点到后代叶子结点的简单路径上，均包含相同数目的黑色结点”这个规则，确保没有一条路径会比其它路径长出 2 倍，因而是近似于平衡的。

树中每个结点包含 5 个属性：color、key、left、right 和 p。如果一个结点没有子结点或父结点，则该结点相应的值为 NIL。我们可以把这些 NIL 视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

一棵红黑树是满足下面的红黑性质的二叉搜索树：  
1. 每个结点是红色或黑色  
2. 根结点是黑色  
3. 每个叶结点（NIL）是黑色  
4. 如果一个结点是红色，则它的两个子结点都是黑色  
5. 对每个结点，从该结点到其所有后代叶子结点的简单路径上，无包含相同数目的黑色结点。

关于红黑树的高度：h <= 2lg(n+1)  
搜索的复杂度：O(h)

为了全球处理红黑树代码中的，边界条件，使用一个哨兵来代表 NIL。对于一棵红黑树 T，哨兵 T.nil 是一个与树中普通结点有相同属性的对象。它的 color 属性为 Black，其它属性为任何值。图(a)  
使用哨兵后，就可以将结点 x 的 NIL 孩子裤一个普通结点。为树内每个 NIL 创建一个哨兵结点的话，有些浪费空间，所以用一个哨兵 T.nil 代替所有 NIL。图(b)  
我们通常把注意力放在红黑树的内部结点上，因为他们存储了关键字。下面的部分，所画的红黑树都忽略了哨兵结点。  
![这里写图片描述][SouthEast 21]

## 13.2 旋转 ##

在对树进行“插入”或“删除”操作后，可能会违反了红黑树的性质，为了维护这些性质，必须要改变结点的颜色 或 指针结构。  
指针结构的修改，是通过“旋转(rotation)”来完成的，这是一种能保持二叉搜索树性质的辟中操作。旋转分为：左旋和右旋。

左旋：把`结点 x`，放到`结点 x`的`右结点 y`的左孩子位置。而`结点 x`的`右结点 y`的左孩子，而放到`结点 x`的右结点位置。  
右旋：把`结点 y`，放到`结点 x`的`左结点 x`的右孩子位置。而`结点 y`的`左结点 x`的右孩子，而放到`结点 y`的左结点位置。  
![这里写图片描述][SouthEast 22]

![这里写图片描述][SouthEast 23]

## 13.3 插入 ##

请参看：[Red Black Tree: Insert(新增資料)與Fixup(修正)][Red Black Tree_ Insert_Fixup]  
时间复杂度为：O(lgn)

## 13.4 删除 ##

请参看：[Red Black Tree: Delete(刪除資料)與Fixup(修正)][Red Black Tree_ Delete_Fixup]  
时间复杂度为：O(lgn)

# 第十四章 数据结构的扩张 #

当现在的标准的数据结构，不能满足我们的需要是地，很少的情况下才创造出一种全新类型的数据结构，一般都是在现有数据结构上进行扩张。**相应的，原来数据结构的函数可能也需要修改。**（这个时候，我们必须了解函数的过程）

## 14.1 动态顺序统计 ##

在第 9 章介绍过“顺序统计量的”问题，它的时间复杂度是 O(n)。如果使用红黑树，可以在 O(lgn) 时间内确定任何顺序统计量。

“顺序统计树” T 是在红黑树基础上，再加上一个附加信息 size。它是用来保存“包含以 x 为根的子树(包含x)的(内)结点数”。哨兵的大小为0。  
![这里写图片描述][SouthEast 24]

在一“顺序统计树”中，我们并不要求关键字各不相同（上面的图包含了两个21）。为此，我们定义一个元素的“秩”的位置，是指在中序遍历时的输出位置。（后序遍历时，可能先遍历到下面的 21，其它函数内部可能要进行修改，相对中序遍历的程序来说）

> 什么是秩？就是一个元素所在的位置。英语对应的是 rank，是和矩阵相关的术语。

### 查找具有给定秩的元素 ###

![这里写图片描述][SouthEast 25]

上面程序要注意的是，如果是`位置i`大于当前结点的 size 时，在递归调用右子树时，`位置i`应该是`i-当结点size`。

### 确定一个元素的秩 ###

![这里写图片描述][SouthEast 26]

这个程序中用 r 来表示当前元素的位置。注意，如果是 y=y.p.right 时，r 这个位置元素应该是“左子树的size + r + 1”。因为 y=y.p.right 的意思是，当前结点是它的父结点的右子树，那么下一个我们要迭代的结点应该是它的父结点，而父结点所在的 r ，左子树是比父结点小的元素的个数，所以应该加上左子树的 size。例子如下：

![这里写图片描述][SouthEast 27]

### 对子树规模的维护 ###

在插入和删除后，我们还需要对子树进行维护，让他保持红黑树的性质。维护需要两个阶段：

*  对由根到叶子的路径上遍历每一个结点 x，都增加 x.size 属性。新增结点的 size 为 1。由于一条遍历的路径上共有 O(lgn) 个结点，所以维护 size 属性的代价为 O(lgn)。
 *  对红黑树结构上的改变仅仅是旋转，旋转次数至多为 2。而且，旋转还会使两个结点的 size 属性失效，所以还需要修改两个结点的 size 属性。因为操作是常数，代价为：O(1)

所以维护的代价为：O(lgn) + O(1) = O(lgn)，和一般红黑树是一样的。

### 14.2 如何扩张数据结构 ###

下面的步骤是一个一般模式，不要盲目地按照上面给定的次序来执行这些步骤。例如：如果我们不能有效地维护附加信息，那么确定附加信息以及设计新的操作（步骤2和4）就没有任何意义。然后，这个 4 步法可以使读者在扩张数据结构时，目标确定且有条不紊。

1.  选择一种基础数据结构。
2.  确定基础数据结构中要维护的附加信息。
3.  检验基础数据结构上的基础修改操作能否维护附加信息。
4.  设计一些新的操作。

![这里写图片描述][SouthEast 28]

## 14.3 区间树 ##

![这里写图片描述][SouthEast 29]  
![这里写图片描述][SouthEast 30]  
![这里写图片描述][SouthEast 31]

[SouthEast]: /images/20220531/8a3f19bed06b442fa18f75be994042ae.png
[SouthEast 1]: /images/20220531/deb6e67aff694bfdae0c37ee73ec36c6.png
[SouthEast 2]: /images/20220531/5aa12d40aefb457789590917f48bc283.png
[Hash_ H_k_ _ k _ m_ m _2_ _2_i -1]: http://blog.csdn.net/cinmyheart/article/details/42749531
[Need help understanding Division Method for constructing a hash function]: https://www.reddit.com/r/learnprogramming/comments/5vr1kk/algorithms_and_data_structures_need_help/
[Link 1]: http://blog.csdn.net/qing0706/article/details/50151945
[Why do hash functions use prime numbers]: https://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
[SouthEast 3]: /images/20220531/7673973ec44a4af9bff299a0369e3c2e.png
[SouthEast 4]: /images/20220531/21a7f7f89cdf4d86a0654230ecb609ea.png
[SouthEast 5]: /images/20220531/03657bec6cb645929879b9918f3f9295.png
[SouthEast 6]: /images/20220531/396c8782c8e443e3aa9d055064323e41.png
[Hash Table_Open Addressing]: http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html
[SouthEast 7]: /images/20220531/08192937d34e4df998bc14f5b450d7d7.png
[SouthEast 8]: /images/20220531/698d933183344019bb7a75aaee09cd58.png
[SouthEast 9]: /images/20220531/3701c6d37d794daaba025191c6b61f68.png
[SouthEast 10]: /images/20220531/8980ca1e7a1f4f2589680e217c37e59b.png
[SouthEast 11]: /images/20220531/a9c96212e1c54e95a7b09f2a44259324.png
[SouthEast 12]: /images/20220531/c9c1f2af2ebd415684eae7b4582f2dc2.png
[SouthEast 13]: /images/20220531/20ba445496c4439c829189462c4a72a0.png
[SouthEast 14]: /images/20220531/2ca0bfd3ae8d49cfbbe1dfaead9d7347.png
[SouthEast 15]: /images/20220531/dac90fe9e51f4253b8d5d20db59c51fe.png
[SouthEast 16]: /images/20220531/e001e66d5d844772ab367f78eb3329d8.png
[SouthEast 17]: /images/20220531/88bf3002bc354cc997b0a24e3d2afaf2.png
[SouthEast 18]: /images/20220531/a0aa7ac2692c4336b419dd8333b8b771.png
[SouthEast 19]: /images/20220531/c4653a109cfb4424a4f10d16c790f1af.png
[SouthEast 20]: /images/20220531/97b81286dfe548a795b8ce9eb1f7e76d.png
[SouthEast 21]: /images/20220531/aaeb8d162a8d48c3b357b268569691b2.png
[SouthEast 22]: /images/20220531/403defaa19b845579cd78387f8064012.png
[SouthEast 23]: /images/20220531/32865aefaff7477fb8a0dc67150bff99.png
[Red Black Tree_ Insert_Fixup]: http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html
[Red Black Tree_ Delete_Fixup]: http://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html
[SouthEast 24]: /images/20220531/46d7756a13b541ffa8bf87afe3f6fe96.png
[SouthEast 25]: /images/20220531/4d92325d9de1480dbe1725a184b712bb.png
[SouthEast 26]: /images/20220531/8d7287f168104873a7e334aed3654445.png
[SouthEast 27]: /images/20220531/1fae182fe2cf4427b7340bee15450db0.png
[SouthEast 28]: /images/20220531/c9eeded66de44419846f23cabf5beedc.png
[SouthEast 29]: /images/20220531/caf0d94273024ba597fad1a9a2c6c708.png
[SouthEast 30]: /images/20220531/579616cbecb247f6a2bffd0a05a363df.png
[SouthEast 31]: /images/20220531/dce1f53fdbbe4060bc58b19744828453.png