数据结构：查找

简介

平均查找长度（ASL）：在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

查找

顺序查找

顺序查找，又称为线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对关键字有序的顺序表的顺序查找。

1. 一般线性表的顺序查找

一般线性表的顺序查找平均查找长度为：ASL(成功)=(n+1)/2 。查找不成功时，与表中各关键字的比较次数显然是n+1次，从而顺序查找不成功的平均查找长度为：ASL(不成功)=n+1

顺序查找的缺点是当n较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序均可应用。同时注意，对线性的链表只能进行顺序查找。

2. 有序表的顺序查找

如果在查找之前就已经知道表是按照关键字有序的，那么当查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，这样能降低顺序查找失败的平均查找长度。

有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点所查找的长度等于它上面一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下有ASL(不成功)=n/2+n/(n+1)

有序表的顺序查找中的线性表可以是链式存储结构

折半查找

折半查找，又称二分法查找，它仅适用于有序的顺序表。

折半查找的过程可用图示的二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于右子结点值。若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。

用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为约等于log₂(n+1)-1。折半查找的时间复杂度为O(log₂n)，平均情况下比顺序查找效率高。该查找法仅适用于线性表的顺序存储结构，不适合链式存储结构，且要求元素按照关键字有序排序。

分块查找

分块查找的基本思想：将查找表分为若干个子块。块内的元素是无序，但块之间是有序的，即第一块中的最大关键字小于第二块中的所有记录的关键字，第二块中最大的关键字小于第三块中的所有记录的关键字，依次类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找分为两步：第一步在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引块；第二步在块内顺序查找。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设将长度为n的查找表均匀的分布在b块，每块有s个记录，在等概率情况下：

• 若块内和索引表均采用顺序查找，则平均查找长度为ASL=(s²+2s+n)/2s
• 若索引表采用折半查找，则平均查找长度为ASL=⌈log₂(b+1)⌉+(s+1)/2

B树和B+树

从数据结构来讲只有2种，也就是B-树和B+树。有时候，B-树又称为B树，他们是一个东西。请注意，B-树中间的“-”是连字符，而不是“减号”。英文中是B-Tree，翻译成中文后，也就是B树，有的翻译喜欢把连字符“-”也带着，于是就成了B-树，而B-树被有些读者误读为B减树

一个树的阶，就是这个树中各个节点的子节点个数的最大值。也就是说，如果有的节点有2个子节点，有的节点有4个子节点，最多的有5个子节点，那么，这个树的阶就是5。

m阶的B树与m阶的B+树异同：

• 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
• 在B+树中每个结点（非根结点）关键字个数n的范围是⌈m/2⌉≤n≤m（根结点：1≤n≤m）；在B树中，每个结点（非根结点）关键字个数n的范围⌈m/2⌉-1≤n≤m-1（根结点：1≤n≤m-1）
• 在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只有对应子树的最大关键字和指向孩子树的指针，不含有该关键字对应记录的存储地址。
• 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

B树

B树被设计成相对矮宽，而对B树的访问是由一系列的外存操作和内存操作交替组成的。有多少外存操作，就有多少内存操作。但要使外存操作的代价与内存操作的代价大致相当。B树能做到，而AVL与BST却做不到。

• 水平方向：对应与每个节点的内部搜索，在内存（RAM）中进行。
• 垂直方向：对应于磁盘（Disk）操作。树中每下降一层，就要付出一次IO操作的代价。

B树，又称为多路平衡查找树，B树中所有结点的孩子结点树的最大值称为B树的阶，通常用m表示。

• 树中每个结点至多有m棵子树，最少有⌈m/2⌉棵子树（即至多含有m-1个关键字，最少有⌈m/2⌉-1个关键字）
• 当节点中保存k个关键字时（关键字按照从小到大排列），该节点会有k + 1个子节点
• 若根结点不是终端结点，则至少有两颗子树
• 所有的叶子节点都出现在同一层次上，并且不带信息（可以看作是外部结点或者类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
• B树是所有节点的平衡因子均等于0的多路查找树。如图，其中底层方形结点表示叶子结点，这些结点中没有存储信息

1. B树查找

B树查找包含两个基本操作：

• 在B树中找结点
• 在结点上找关键字

由于B树常存储在磁盘上，则前一个查找是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点中的信息读入内存，然后再采用顺序查找或折半查找法查找等于K的关键字

2. B树插入（插入-上溢-分裂）

将关键字key插入到B树的过程如下：

• 定位：利用前述的B树查找算法，找出插入该关键字的最底层中某个非叶子结点（注意：B树中的插入关键字一定是插入在最底层中的某个非叶子结点内）
• 插入：在B树中，每个非失败结点的关键字个数都是⌈m/2⌉-1到m-1之间。当插入后的结点关键字个数小于m，则可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，则必须对结点进行分裂

分裂的方法是：取一个新结点，将插入key后的原结点从中间位置将其中的关键字分为两部分，左部分包含的关键字放到原结点中，右部分包含的关键字放到新的结点中，中间位置的节点插入到原结点的父结点中。若此时导致父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程查到根节点为止，这样导致B树高度增加1。

分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

插入过程和树的构建过程本质是一致的，即都是进行插入操作，并对插入后的B-树进行调整。以下面的树为基础，我们设定B-树的阶为5。用关键字序列[1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15]来构建一棵B-树。

• 插入1、2、6、7作为一个节点

• 插入11：得到1、2、6、7、11. 因为节点个数超过4，所以需要对该节点进行拆分。选取中间节点6，进行提升，提升为父节点

• 插入4、8、13：直接插入即可（有一个规则是新插入的节点总是出现在叶子节点上）

插入10：因为最右下的节点内有5个元素，超过最大个数4了，所以需要进行拆分，把中间节点10进行提升，上升到和6一起

插入插入5、17、9、16：

插入20：插入20后，最右下节点内元素个数为5个，超过最大个数4个，所以，需要把16进行提升

插入3、12、14、18、19：

插入15：会导致13提升到根节点，这时，根节点会有5个节点，那么，根节点中的10会再次进行提升

3. B树删除（删除-下溢-合并）

当所删除的关键字k不在终端结点（最底层非叶结点）时，有下列几种情况：

• 如果小于k的子树中关键字个数>⌈m/2⌉-1，则找出k的前驱值k+，并且用k+来取代k，再递归地删除k+即可
• 如果大于k的子树中关键字个数>⌈m/2⌉-1，则找出k的后继值k-，并且用k-来取代k，再递归地删除k-即可
• 如果两个子树中关键字个数均=⌈m/2⌉-1，则直接将两个子结点合并，直接删除k即可

当被删除的关键字在终端结点中时，有下列几种情况：

• 直接删除关键字：若被删除关键字所在结点的关键字个数>⌈m/2⌉-1，表明删除该关键字后仍满足B树的定义，则直接删除该关键字
• 兄弟够借：若被删除关键字所在结点删除前的关键字个数=⌈m/2⌉-1，且与此结点相邻的右（左）兄弟的关键字个数大于⌈m/2⌉-1，需要调整该节点、右（左）兄弟结点以及其双亲结点（父子换位法），以达到新的平衡
• 兄弟不够借：若被删除关键字所在结点删除前的关键字个数=⌈m/2⌉-1，且此时与该结点相邻的右（左）结点的关键字个数=⌈m/2⌉-1，则将关键字删除后与右（左）兄弟结点及双亲结点中的关键字进行合并

以下面的树为基础，进行删除操作[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]。首先明确一下这个树的定义。它是一个5阶树。所以，每个节点内元素个数为2~4个。我们依次删除8、16、15、4这4个元素。

• 删除8：因为删除8后，不破坏树的性质，所以直接删除即可

• 删除16：这导致该节点只剩下一个13节点，不满足节点内元素个数为2~4个的要求了。所以需要调整。这里可以向孩子借节点

• 删除15：删除15后同样需要调整。调整的方式是18上升，17下降到原来15的位置

删除4：删除4后该节点只剩下5，需要调整。可是它的兄弟节点也都没有多余的节点可借，所以需要进行节点合并。节点合并时，方式会有多种，我们选择其中的一种即可。这里，我们选择父节点中的3下沉，和1，2，以及5进行合并。

4. B-树卫星数据

卫星数据：指的是索引元素所指向的数据记录，比如数据库的某一行。在B-树中，无论中间结点还是叶子结点都带有卫星数据。

B+树

一颗m阶B+树需满足下列条件：

• 树中每个结点至多有m棵子树，最少有⌈m/2⌉棵子树（同时至多含有m个关键字，最少有⌈m/2⌉个关键字）结点子树个数与当前结点的关键字个数相同
• 所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（即下一级的索引快）中关键字的最大值及指向其子结点的指针。每个父结点的元素都出现在子结点中，是子结点的最大（或最小）元素
• 所有的叶子结点都位于同一层
• 所有叶子节点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来，形成了一个有序链表。

无论查找成功与否，每次查找都是一条从根结点到叶子结点的路径。

注意：根结点的最大元素，也就等同于整个B+树的最大元素，以后无论插入还是删除多少元素，始终要保持最大元素在根结点中。

1. B树卫星数据

卫星数据：指的是索引元素所指向的数据记录，比如数据库的某一行。在B+树中，只有叶子结点带有卫星数据，其余中间结点仅仅是索引，没有任何数据关联。

B树和B+树比较

B+树的好处主要体现在查询性能上。下面我们分别通过单行查询和范围查询来做分析。

1. 单元素查询

在单元素查询的时候，B+树会自顶向下逐层查找结点，最终找到匹配的叶子结点。比如我们查找的是元素3。

• 第一次磁盘IO：

• 第二次磁盘IO：

第三次磁盘IO：

B树与B+树有两点不同。首先，B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素。这就意味着，数据量相同的情况下，B+树的结构比B-树更加“矮胖”，因此查询时IO次数也更少。其次，B+树的查询必须最终查找到叶子节点，而B-树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点。因此，B-树的查找性能并不稳定(最好情况是只查根节点，最坏情况是查到叶子节点)。而B+树的每一次查找都是稳定的。.

2. 范围查询

下面我们再来看看范围查询。

B-树如何做范围查询呢，只能依靠繁琐的中序遍历。比如我们要查询范围为3到11的元素:

• B-树的范围查找过程自顶向下，查找到范围（3-11）：

• 中序遍历到元素6：

• 中序遍历到元素8：

• 中序遍历到元素9：

• 中序遍历到元素11，遍历结束：

B+树的范围查询，则要简单得多，只需要在链表上做遍历即可：

• B+树的范围查找过程自顶向下，查找到范围（3-11）：

• 通过链表指针，遍历到元素6，8：

• 通过链表指针，遍历到元素9,，11，遍历结束：

B+树果然比B-树的中序遍历要简单得多。综合起来，B+ 树相比B-树的优势有三个：

• IO次数更少
• 查询性能稳定
• 范围查询简便

3. B+树的特征：

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

4. B+树的优势：

• 单一节点存储更多的元素，使得查询的IO次数更少。
• 所有查询都要查找到叶子节点，查询性能稳定。
• 所有叶子节点形成有序链表，便于范围查询。

散列（Hash）表

散列表：是根据关键字而直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素个数无关。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

散列函数

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称为“冲突”，这些发生碰撞的不同关键字称为同义词。

• 直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a*key+b式中，a和b都是常数。这种方法计算简单，并且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，将造成存储空间的浪费。
• 除留余数法：这种方式最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或者等于m的质数p，利用一下公式把关键字转换成散列地址。散列函数为H(key)=key%p。

除留余数法的关键字是选好p，使得每一个关键字通过该函数转换后等待率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

• 数字分析法
• 平方取中法
• 折叠法

处理冲突

开放定址法：所谓开放地址法，指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

• 线性探测法：冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查边全表
• 平方探测法
• 再散列法
• 伪随机序列法

注意：在开放地址法中，不能随便物理删除表中已有的元素，因为若删除元素将会截断其他具有相同散列地址的元素的查找地址。所以若想删除一个元素时，给它做一个删除标记，进行逻辑删除。但是这样做的副作用是：在执行多次删除后，表面上看起来散列表很满，实际上有许多位置没有利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

拉链法：对于不同关键词可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。

例如：关键字序列为，[19， 14， 23， 01， 68， 20， 84， 27， 55， 11， 10， 79]，散列函数为H(key)=key%13，用拉链法处理冲突。

装填因子

装填因子：散列表的装填因子一般记为α，定义为一个表的装满程度，即：α=表中记录数n/散列表长度m

散列表的平均查找长度依赖散列表的装填因子α，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越满，发生冲突的可能性越大，反之发生冲突的可能性越小。