第三部分 数据结构

前言

该部分主要介绍算法中常用的数据结构：数组，栈，队列，链表和有根树以及定义在这些数据结构中操作。这些操作主要分作两大类：查询操作和修改操作，常见的查询操作有search，minimum，maximum，successor，predecessor；修改操作有insert，delete。

之后本部分对有根树做了详细介绍：二叉搜索树，红黑树等，并基于红黑树对数据结构的扩张进行阐述。

第十章 基本数据结构

本章介绍几种基本的数据结构：栈，队列，链表，有根树。在章节末，介绍了用数组构造对象和指针的方法（适当了解即可，无需深究）

栈

栈是一种运算受限的线性表，它仅允许在表的一端进行插入和删除运算，且后插入的元素先删除，称为后进先出（LIFO）。汉诺塔问题其中就有栈的概念，后放入的盘子先被拿出。

基本操作（假设栈的容量为n）

队列

队列同样是一种运算受限的线性表，它允许在表的一端插入元素，而从表的另一端删除元素（插入的一端称为队尾，操作称为入队，删除的一端称为队头，操作称为出对），称为先进先出（FIFO）。像在银行排队办理业务就是队列的日常实例。

栈和队列都是动态集合

注意队列的Q.Tail和Q.head的大小关系的并非固定的，换句话说，存在Q.Tail<Q.Head的情况，因为队列在具体实现时，空间是循环利用的，它可以通过取余操作使得数组空间首尾连接（imodA.capasity+1）

基本操作（假设队列的容量为n）

链表

链表是一种物理存储单元上非连续，非顺序的存储结构，也就是说，数据元素的逻辑顺序并不是通过物理单元的次序来表达，而是通过链表中元素指针的链接次序来表达。

根据每个元素的指针个数，链表又可以分为单向链表和双向链表：单向链表只有一个指针，且指向它的下一个元素（也就是它的后继）；双向链表有两个指针，一个指向下一元素，一个指向上一元素（前驱）。

在链表中，有一个特殊情况，表尾的指针指向表头，这样的表成为循环链表；双向链表中，表头和表尾也是相互指向对方的。

这里要提出一个概念：哨兵，它是链表中的一个哑对象，也就是说，它的关键字key并没有实际含义，它的出现只是为了出来表头和表尾的边界条件，能够使得代码可读性更好，代码更为简洁。但有些时候，哨兵的使用也会造成资源的浪费，比如有很多短链表，每个链表都设置哨兵的话，其存储开销还是很大的。

基本操作（以双向链表为例）

加入哨兵（使得操作更为简洁）

有根树

有根树和链表一样，都是通过指针来表达数据元素之间的逻辑顺序。但它和链表不同的是，它的后继不止一个（当然，在有根树中，我们给它新的名称，我们称之为子结点）；对应于，链表中的前驱，我们在树中称之为父结点。最开始的结点，我们称之为根结点，只有根结点没有父结点。

有根树中最常用的就是二叉树，也就是说树中每个结点最多只有两个孩子，我们分别称为左孩子和右孩子。二叉树的表达方式是每个结点有三个指针：p,left,right，分别指向父结点，左孩子和右孩子。

除了二叉树以及其它有结点最大限制的树外，还存在分支无限制的有根树。分支无限制的有根树如果采用二叉树的表达方式，势必会导致资源的巨大浪费，而且我们也无法预知分配多少存储空间（分支无限制，没办法预知子结点的个数），所以一种新的表达方式则更具有优势，它被称为左孩子右兄弟表示法。

关于数组实现对象和指针

这个就不做介绍啦。

第十一章 散列表

散列表也称哈希表，它是通过关键字进行直接访问的数据结构，这一点和数组很像，所以我们其实也可以把它看成是数组概念的推广，它们都能在O(1)时间内完成对元素的访问。和数组不同的是，数组的关键字就是数据元素的存储下标，而散列表则是通过散列函数将关键字映射到表的相关位置。散列表的目的是为了在常数时间内完成数据元素的查询，插入和删除工作。

散列表相对于数组的优势：当实际存储的关键字数目比全部可能的关键字要小时，采用散列表可以节省大量的存储空间。

由于散列函数将关键字映射到表的下标时，存在着多个关键字映射到同一下标中的情况，这种情况我们称之为冲突。这时一般可采用“链表法”或“开放寻址法”。

直接寻址表（直接寻址数组）是关键字全域|U|较小时使用的一种技术。关键字即为表的下标。

由上面的话，我们也能了解到：如果关键字全域很大时，而计算机的内存容量又是有限的，采用直接寻址技术要想存储大小为|U|的表不太实际，甚至是不可能的。通常来说实际存储的关键字集合|K|要比全域|U|小得多，为了防止存储空间的浪费，同时又获取其高效的访问效率。于是新的数据结构——散列表被提出。

散列表的核心在于散列函数，一个好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到m个槽位中的任何一个，并与其他关键字已散列到哪个槽位无关。之后我们会说明，对于满足简单均匀散列假设的散列函数，在其构建的散列表上，如果采用链接法解决冲突，完成一次查询的平均时间都是Θ(1+α)（无论查询是否成功，α为装载因子）

链接法中常用的散列方法：除法散列，乘法散列，全域散列；

开放寻址法中常用的散列方法：线性探查，二次探查，双重探查。

说了这么多，开始对上面说的一些知识点进行更具体的分析啦！

链接法散列的分析（散列函数满足简单均匀散列假设）

• 装载因子：给定一个能存放n个元素的，具有m个槽位的散列表T，T的装载因子α即为其一个槽位中链表平均存储的元素个数。

• 链接法散列的最坏情况性能很差，如果所有关键字都散列到同一个槽中，则相当于一个长度为n的链表，这时它的查找时间为Θ(n)。当然，一般情况来说，散列表不会出现最坏情况，如果散列函数经过精心设计的话，其查找的期望时间一般都为常数。

• 查询操作 定理：在简单均匀散列的假设下，对于用链接法解决冲突的散列表，一次成功或不成功的查找平均时间均为Θ(1+α)。

  证明：

  （查找不成功）

  在简单均匀散列的假设下，任何尚未被存储在表中的关键字k都等可能地被散列在m个槽中的任何一个。当查找一个关键字k不成功的情况下，查找的期望时间就是查找至链表T[h(k)]末尾的期望时间，这个时间的期望长度为E[nh(k)]=α，所以，一次不成功的查找平均要检查α个元素，所需总时间（包含计算h(k)的时间）为Θ(1+α)。

  （查找成功）

  怎么去分析这个问题？

  由于我们查找成功，说明元素x必定是这n个元素中的一个且是等可能的。由散列表的插入性质（元素首先根据散列函数计算出关键字对应槽位，之后从对应槽位链表的表头插入），我们可知只有在元素x之后的元素有可能插入在x之前。而如果我们成功查找到x，其实只需要查询x所在链表，在x之后插入到表中的期望元素数加1。我们假设元素xi是第i个元素，并且设ki=xi.key，对关键字ki和kj，定义指示器变量Xij=I{h(ki)=h(kj)}。在简单均匀散列假设下，有Pr(h(ki)=h(kj))=1/m，从而有E[Xij]=1/m。所以一次成功查找所检查的元素期望数目为
  

  E[1n∑i=1n(1+∑j=i+1nXij)]=1n∑i=1n(1+∑j=i+1nE[Xij])=1n∑i=1n(1+∑j=i+1n1m)=1+1n∑i=1n∑j=i+1n1m=1+1nm∑i=1n(n−i)=1+1nm[∑i=1nn−∑i=1ni]=1+1nm(n2−n(n+1)2)=1+n−12m=1+α2+α2n
  
  所以，一次成功查找所需的全部时间（包括计算散列函数时间）为Θ(1+1+α2+α2n)=Θ(1+α)。

  上述定理说明，查询操作平均需要常数时间。

• 插入操作：将散列到同一槽中的所有元素都放在同一链表中，且从表头插入元素，所以可知插入操作的最坏情况运行时间为O(1)；

• 删除操作：删除操作需要根据使用的链表类型（单向链表和双向链表），以及元素输入类型（指针x或关键字key）不同分别考虑。

  对于元素输入类型为关键字key时，删除操作最坏情况运行时间为O(n)，平均运行时间与查找操作相同，为Θ(1+α)（假设满足简单均匀散列假设）；

  对于元素输入类型为指针x时，采用单向链表的散列表删除操作最坏情况运行时间为O(n)，平均运行时间与查找操作相同，为Θ(1+α)（假设满足简单均匀散列假设）；而双向链表最坏情况运行时间为O(1)。

  一般，将查询，插入，删除操作称为字典操作。散列表的字典操作平均情况都可以在O(1)时间内完成。

散列函数

除法散列

h(k)=kmodm

m一般选择一个不太接近2的整数幂的素数。

乘数散列

h(k)=⌊m(kAmod1)⌋

常数0<A<1，kAmod1表示取kA的小数部分，等价于kA−⌊kA⌋

优点：对m的选择不是特别关键

全域散列

hab(k)=((ak+b)modp)modm

从一组精心设计的函数中，随机地选择一个作为散列函数。

全域散列的平均性态是比较好的，有推论，利用全域散列法和链接法解决冲突的散列表，查询，插入和删除三种基本字典操作平均情况的运行时间为O(1)。

开放寻址法

在开放寻址法中，所有元素都存放在散列表中，也就是说，每一个表项中或包含一个元素，或包含NIL，再换句话说，就是装载因子α≤1。

探查：为使用开放寻址法插入一个元素，连续地检查散列表，直到找到一个空槽来放置待插入的关键字为止。

为了确定要探查哪些槽，我们对散列函数进行扩充，使得探查号（从0开始）也成为第二个输入参数，其散列函数形式为

对于每一个关键字，探查序列为<h(k,0),h(k,1),...,h(k,m−1)>

线性探查

h(k,i)=(h′(k)+i)modm;i=0,1,...,m−1

h′为普通散列函数，在这里作为辅助散列函数。

线性探查容易出现一次群集的问题。

二次探查

h(k,i)=(h′(k)+c1i+c2i2)modm;i=0,1,...,m−1

h′为辅助散列函数，c1,c2为正辅助常量。。

二次探查容易出现二次群集的问题，此为轻度群集。

双重探查

h(k,i)=(h1(k)+ih2(k))modm;i=0,1,...,m−1

h1,h2均为辅助散列函数。为了能够查找整个散列表，值h2(k)必须要与m互素。

一个例子：取m是2的幂，并设计总产生奇数的h2。

开放寻址散列的分析

• 给定一个装载因子为α=n/m<1的开放寻址散列表，并假设是均匀散列的，则对于一次不成功的查找，其期望探查次数至多为1/(1−α)；由此可以推知插入一个元素至多需要做1/(1−α)次探查，因为关键字被放入第一个遇到的空槽中。

• 定一个装载因子为α=n/m<1的开放寻址散列表，并假设是均匀散列的，则对于一次不成功的查找，其期望探查次数至多为1αln11−α；由此可知，删除一个元素至多需要1αln11−α次探查。

  假设散列表是半满α=n/m=50%的，一次不成功查找的平均探查次数至多为1/(1−0.5)=2，一次成功查找的平均探查次数至多为1/0.5ln(1/(1−0.5))<1.387；

  假设散列表是α=n/m=90%满的，一次不成功查找的平均探查次数至多为1/(1−0.9)=10，一次成功查找的平均探查次数至多为1/0.9ln(1/(1−0.9))<2.559。

完全散列（perfect hashing）

采用两级散列方案实现完全散列。完全散列适用场景：关键字集合是静态的（静态：一旦关键字存入表中，关键字集合就不再变化）。如，程序设计语言的保留字集合，CD-ROM上的文件名集合。

完全散列概念描述

首先利用从某一全域散列函数簇中仔细挑选出的一个散列函数h，将n个关键字散列到m个槽中；

然后，和链表法不同的是，我们并不将落在同一槽中的关键字用链表链接来解决冲突，而是采用精心选择的散列函数hj来实现，也就是说，我们通过两级散列来实现元素存储和解决冲突。

合理选择第一级散列函数，以及第二级散列函数的空间需求

为了确保在第二级上不出现冲突，需要让散列表Sj的大小mj是散列到槽j中关键字nj的平方。虽然这样看上去，由于mj对nj的二次依赖使得总体空间需求量很大，但是其实我们可以通过适当的选择第一级散列函数，将预期使用的总体存储空间限制在O(n)内。

完全散列的几条定理

• 定理1：如果从一个全域散列函数类中随机选出散列函数h，将n个关键字存储在一个大小为m=n2的散列表中，那么表中出现冲突的概率小于1/2；

  证明：n个关键字，则有(n2)对关键字可能发生冲突，如果散列函数从全域散列函数类中选出，则每对关键字发生冲突的概率为1/m，设X是一个统计冲突次数的随机变量，当m=n2时，期望的冲突次数为
  

  E[X]=(n2)⋅1m=n(n−1)2⋅1n2<12

• 定理2：如果从某一个全域散列函数类中随机选出散列函数h，用它将n个关键字存储在一个大小为m=n的散列表中，则有E[∑m−1j=0n2j]<2n，这里nj为散列到槽j中的关键字数。

  证明：我们有数学恒等式：a2=a+2(a2)，于是有
  

  E[∑j=0m−1n2j]=E[∑j=0m−1(nj+2(nj2))]=E[∑j=0m−1nj]+2E[∑j=0m−1(nj2))]=n+2E[∑j=0m−1(nj2)]
  
  其中∑m−1j=0(nj2)是散列表中发生冲突的关键字的总对数，根据全域散列性质，这一和式期望至多为
  
  (n2)⋅1m=n(n−1)2m=n−12
  
  所以，有
  
  E[∑j=0m−1n2j]≤n+2⋅n−12=2n−1<2n

• 推论1：如果从某一全域散列函数类中随机选出散列函数h，用它将n个关键字存储在一个大小m=n的散列表中，并将每一个二级散列表的大小设置为mj=n2j(j=0,1,...,m−1)，则在一个完全散列方案中，存储在所有二次散列表中所需的存储总量的期望值小于2n。

  证明：
  

  ∵mj=n2j∴E[∑j=0m−1mj]=E[∑j=0m−1n2j]<2n

• 推论2：如果从某一个全域散列函数类中随机选出散列函数h，用它将n个关键字存储到一个大小为m=n的散列表中，并将每个二级散列表的大小置为mj=n2j(j=0,1,...,m−1)，则用于存储所有二级散列表的存储总量等于或大于4n的概率小于1/2。

  证明：由马尔科夫不等式Pr{X≥t}≤E[X]/t可推知
  

  Pr{∑j=0m−1≥4n}≤E[∑m−1j=0mj]4n<2n4n=1/2
  
  ​

  从推论2中可以看出，只需从全域散列函数类中随机选出几个散列函数，尝试几次就可以快速地找到一个所需存储量较为合理的函数。