【数据结构与算法】查找

一.查找

问题：在哪里找？

​ ——查找表

查找表(Search Table)：是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构：我们可以根据需要把这些数据存成线性表，可以存成树表，或者是散列表。

那么，到底怎么存呢?

——取决于怎么做会使查找更方便

而查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。

静态查找表(Static Search Table)：只作查找操作的查找表。

• 主要操作

1. 查询某个“特定的”数据元素是否在查找表中。
2. 检索某个“特定的”数据元素和各种属性。

动态查找表(Dynamic Search Table)： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

• 主要操作

1. 查找时插入不存在的数据元素。
2. 查找时删除已存在的数据元素。

关键字(Key)：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

• 主关键字：可以唯一地标识一个记录的关键字是主关键字；
• 次关键字：反之，用以识别若干记录的关键字好死次关键字

问题：查找成功否？

查找(Searching)：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。

• 若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置。
• 否则称“查找不成功”。查找结果给出“空记录”或“空指针”。

平均查找长度是衡量查找算法效率的最主要的指标。

问题：查找目的是什么？

——对查找表经常进行的操作。

为了提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为地加上某种确定的约束关系。所以下面来研究查找表的各种组织方法及其查找过程的实施。

二.线性结构的查找

2.1顺序查找

【查找过程】从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。

【应用范围】顺序查找既适用于顺序表，也适用于链表（链表表示的静态查找表）。若用顺序表，查找可以从前往后扫描，也可以从后往前扫描，但若采用单链表，则只能从前往后扫描。

【查找算法】 在顺序表L中查找值为 key 的数据元素。

//顺序表数据元素类型定义
typedef struct{KeyType key;    //关键字域.....           //其他域
}ElemType;
//顺序表结构类型定义
typedef struct{ElemType *R;//表基址int length;      //表长
}SSTable;          //Sequential Search Table
SSTable ST;//定义顺序表STint LocateELem(SSTable ST,KeyType key){  //若成功返回其位置信息，否则返回0for (i=0;i< ST.length;i++)if (ST.elem[i]==e) return i+1;               return 0;
}//查找的其他形式：
int LocateELem(SSTable ST,KeyType key){  //若成功返回其位置信息，否则返回0for (i=0;ST.R[i].key!=key && i<ST.length;i++);//一次循环，两次比较if(i>0)return i;else return 0;
}

【性能分析】

时间复杂度：①查找成功时的平均查找长度（设表中各记录查找概率相等）

​ ASLs(n)=(1+2+ … +n)/n =(n+1)/2；

​ ②查找不成功时的平均查找长度ASLf =n+1。

每执行一次循环都要进行两次比较，是否能改进呢？

【算法改进】 把待查关键字key存入表头（“哨兵”），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

/*有哨兵顺序查找*/
int Sequential_Search(SSTable ST,KeyType key){ST.R[0].key = key;	//把关键字放在下标为0的位置，称之为“哨兵”for (i=0;ST.R[i].key!=key && i<ST.length;i++);return i;}

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。
上述顺序表查找时间复杂度是O ( n )；空间复杂度是O(1)（多了一个哨兵）

【算法特点】 算法简单，对表结构无任何要求（顺序和链式），但n很大时查找效率较低；ASL太长，时间效率太低。

【改进措施】 非等概率查找时，可按照查找概率进行排序。

那么，记录的查找概率不相等时如何提高查找效率？

查找表存储记录原则——按查找概率高低存储：

（1）查找概率越高，比较次数越少，放在靠后的位置；

（2）查找概率越低，比较次数较多，放在靠前的位置。

记录的查找概率无法测定时如何提高查找效率？

——按查找概率动态调整记录顺序：

（1）在每个记录中设一个访问频度域；

（2）始终保持记录按非递增有序的次序排列；

（3）每次查找后均将刚查到的记录直接移至表头。

---

有序表查找有折半查找，插值查找，斐波那契查找，这里介绍折半查找：

2.2折半查找

折半查找(Binary Searh) 也称二分查找，它是一种效率较高的查找方法。

【应用范围】 折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列（递增或递减）；不宜用于链式结构。

【查找过程】 从表的中间记录开始，如果给定值和 中间记录的关键字相等， 则查找成功；如果给定值大于或者小于中间记录的关键字， 则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空（low>high），则代表查找失败。

例如，对序列5、13、19、21、37、56、64、75、80、88、92中查找21过程如下：

​ ①初时，low=1，mid=(1+11)/2=6 ,high=11

​ ②此时.r[mid].key>21,因此 high=mid-1=5，low=1，mid=(1+5)/2=3

​ ③此时.r[mid].key＜21,因此 low=mid+1=4，high=5，mid=(4+5)/2=4

​ ④此时，k=R[mid].key，查找成功。

【算法思想】 非递归算法 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较：

​ ①若k==R[mid].key，查找成功；

​ ②若k<R[mid].key，则high=mid-1；

​ ③若k>R[mid].key，则low=mid+1。重复上述操作，直至low>high时，查找失败。

【算法描述】

//采用折半查找发在顺序表上进行查找
int Search_Bin(SSTable ST,KeyType key){
//若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length;     //置区间初值                           while(low<=high){mid=(low+high)/2;//取中间位置if(key==ST.R[mid].key)return mid;//查找成功返回所在位置else if(key<ST.R[mid].key) //缩小查找区间high=mid-1;    //从前半部分继续查找else low=mid+1;   //从后半部分继续查找}     return 0;        //表中不存在待查元素
}  

下面来看一下同一种操作的不同算法——递归算法：每一次判断是否与中间位置相等

int Search_Bin(SSTable ST,KeyType key,int low,int high){if(low>high)return 0;//区间不存在，查找不到是返回0mid=(low+high)/2;if(key==ST.elem[mid].key)return mid;else if(key<ST.elem[mid].key)high=mid-1if(key==ST.elem[mid].key)//递归，在前半区间进行查找return mid;elselow=mid+1if(key==ST.elem[mid].key)//递归，在后半区间进行查找return mid;
}

【性能分析】 折半查找使用判定树进行分析。该判定树是一颗二叉排序树，中序有序。判定树的构造过程为：
第一次，进行mid计算时的结点作为根节点，并进行low结点位置和high结点的位置进行计算，作为mid的左右孩子；将前一子表（low-mid）、后一子表（mid-high）分别重复上述步骤，直至所有结点都在判定树中。

如下，对序列5、13、19、21、37、56、64、75、80、88、92进行判定树构造，查找21 如下：

假定每个元素的查找概率相等，求查找成功时的平均查找长度。

对比顺序查找法的平均查找长度是（11+1）/2=6，折半查找法减少了很多，因为折半查找法的时间效率是对数级的，而顺序查找法的时间效率是线性级的。

时间复杂度：查找成功时的平均查找长度（设表中各记录查找概率相等：P_i=1/n）

设表长n=2^h-1，则h=log_2(n+1)（此时，判定树为深度=h的满二叉树）：

利用二叉树的性质，将一个一个（n个）的元素比较转化为一层一层（j层）的结点的比较

【算法特点】

①优点：效率比顺序查找高。

②缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效：找不到mid）。

---

线性索引查找有稠密索引，分块索引和倒排索引，下面介绍分块索引：

2.3分块查找

【应用范围】如果线性表既要快速查找又经常动态变化，则可采用分块查找。

条件：①分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。

②然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

【查找过程】

① 先确定待查记录所在快，对索引表使用折半查找法（因为索引表是有序表）；

② 再在块内查找，在子表内采用顺序查找法（因为各子表内部是无序表）；

【查找算法】 分块查找的算法为顺序查找和折半查找两种算法的简单合成。

【性能分析】

【优缺点】

①优点：插入和删除比较容易，无需进行大量移动。

②缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
总结

三.树型结构的查找

线性表的查找更适用千静态查找表，若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此将它们统称为树表。

3.1二叉排序树

1.定义

二叉排序树 (Binary Sort Tree) 又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。

【性质】二叉排序树或是空树，或是满足如下性质的二叉树：

​ ①若其左子树非空，则左子树上所有结点的值均小于根结点的值；

​ ②若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；

​ ③其左右子树本身又各是一棵二叉排序树

【特点】 中序遍历二叉排序树得到一个关键字的递增有序序列。

---

下面来了解一下二叉树的操作：

2.二叉排序树的常见操作

（1）查找

【算法思想】(1)若二叉排序树为空，则查找失败，返回空指针。

​ (2)若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：

​ ① 若key等于T->data.key，则查找成功，返回根结点地址；

​ ② 若key小于T->data.key，则进一步查找左子树；

​ ③ 若key大于T->data.key，则进一步查找右子树。

【算法描述】

BSTree SearchBST(BSTree T,KeyType key) {if((!T) || key==T->data.key) return T;              else if (key<T->data.key)  return SearchBST(T->lchild,key);   //在左子树中继续查找else return SearchBST(T->rchild,key);   //在右子树中继续查找
} 

【算法分析】平均查找长度和二叉树的形态有关，即:

​ ①最好：log2n（形态匀称，与二分查找的判定树相似）;

​ ②最坏:（n+1)/2（单支树）

（2）插入

【算法描述】 若二叉排序树为空，则插入结点应为根结点，否则，继续在其左、右子树上查找：

①树中已有，不再插入；

②树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。

【算法特点】插入的元素一定在叶结点上。

【算法过程】 在下图所示的二叉排序树上插入结点 20：

过程如下：①45>20,继续在结点45的左子树上查询；

​ ②12<20,继续在结点12的右子树上查询；

​ ③37>20,继续在结点37的左子树上查询；

​ ④24>20,继续在结点24左子树查询，而该结点为叶子结点，将此结点20插入结点24的左子树中。

【算法过程】

/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE，否则返回FALSE
*/
bool InsertBST(BiTree *T, int key){BiTree p, s;if(!SearchBST(*T, key, NULL, &p)){//查找不成功s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = s->rchild = NULL;if(!p){*T = s;	//插入s为新的根节点}else if(key < p->data){p->lchild = s;	//插入s为左孩子}else{p->rchild = s;	//插入s为右孩子}return TRUE;}else{return FALSE;	//树种已有关键字相同的结点，不再插入}
}

（3）生成

从空树出发，对序列{10， 18， 3， 8， 12， 2， 7} 构造二叉排序树。

【过程如下】 ①结点10作为根节点，18>10,插入为结点10的右子树；

​ ②3<10,插入为结点10的左子树；

​ ③8<10,3>8,插入为结点3的右孩子；

​ ④12>10.12<18,插入为结点18的左孩子；

​ ⑤2<10，3>2,插入为结点3的左孩子；

​ ⑥7<10,3<7,8>7,插入为结点8的左孩子，至此二叉排序树生成。

**【注意】**不同插入次序的序列生成不同形态的二叉排序树。如下图所示：

【算法过程】

有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了，几个例子：

int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for(i = 0; i<10; i++){InsertBST(&T, a[i]);
}

上面的代码就可以创建一棵下图这样的树。

（4）删除

【删除思想】将因删除结点而断开的二叉链表重新链接起来，防止重新链接后树的高度增加。

​ ①删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。

​ ②被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。

​ ③被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。

​ ④被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删结点中，再来处理这个结点的删除问题。

【算法过程】

/*从二叉排序树中删除结点p，并重接它的左或右子树。*/
bool Delete(BiTree *p){BiTree q, s;if(p->rchild == NULL){//右子树为空则只需重接它的左子树q = p;p = p->lchild;free(q);}else if(p->lchild == NULL){//左子树为空则只需重接它的右子树q = p;p = p->rchild;free(q);}else{//左右子树均不空q = p;s = p->lchild;	//先转左while(s->rchild){//然后向右到尽头，找待删结点的前驱q = s;s = s->rchild;}//此时s指向被删结点的直接前驱，p指向s的父母节点p->data = s->data;	//被删除结点的值替换成它的直接前驱的值if(q != p){q->rchild = s->lchild;	//重接q的右子树}else{q->lchild = s->lchild;	//重接q的左子树}pree(s);}return TRUE;
}

3.性能分析

二叉排序树的优点明显，插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
例如{ 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } 这样的数组，我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树，如下面右图的二叉排序树：

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂也就为 O(log n)，近似于折半查找。
不平衡的最坏情况就是像上面右图的斜树，查找时间复杂度为O ( n ) ，这等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。

3.2平衡二叉树

1.定义

【概念】左、右子树是平衡二叉树AVL；所有结点的左、右子树深度之差的绝对值≤ 1 。任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；

【平衡因子】 该结点左子树与右子树的高度差。

【算法分析】 对于一棵有n个结点的平衡二叉树AVL，其高度保持在O(log2n)数量级，平均查找长度ASL也保持在O(log2n)量级。

平衡旋转

如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。

【LL平衡旋转】若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转(以B为旋转轴）。

【RR平衡旋转】若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转(以B为旋转轴）。

【LR平衡旋转】若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转(以插入的结点C为旋转轴）。

【RL平衡旋转】若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转(以插入的结点C为旋转轴）。

2.平衡二叉树的常见操作

（1）查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以n h n_hn**h表示深度为h hh的平衡树中含有的最少结点数。显然，有n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2n0=0,n1=1,n2=2，并且有n h = n h − 1 + n h − 2 + 1 n_h=n_{h-1}+n_{h-2}+1n**h=n**h−1+n**h−2+1。可以证明，含有n nn个结点的平衡二叉树的最大深度为O ( l o g 2 n ) O(log2n)O(log2n)，因此平衡二叉树的平均查找长度为O ( l o g 2 n ) O(log2n)O(log2n) 如下图所示。

（2）插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
注意:每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列4种情况：

1. LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
   如下图所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。
   
2. RR平衡旋转(左单旋转)。由于在结点A的右孩子®的右子树®上插入了 新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
   
3. LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树®上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置（即进行一次RR平衡旋转(左单旋转)），然后再把该C结点向右上旋转提升到A结点的位置（即进行一次LL平衡旋转(右单旋转)）。
4. RL平衡旋转(先右后左双旋转)。由于在A的右孩子®的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置（即进行一次LL平衡旋转(右单旋转)），然后再把该C结点向左上旋转提升到A结点的位置（即进行一次RR平衡旋转(左单旋转)）。
   注意: LR和RL旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程，而上图中是以插入C的左子树中为例。

举个例子：
假设关键字序列为15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8}15,3,7,10,9,8，通过该序列生成平衡二叉树的过程如下图所示。

3.性能分析

平衡树查找的时间复杂度为 O(log n)

查找和二叉排序树一致，比较的次数不超过平衡二叉树的深度。

---

【多路查找树】

多路查找树(muitl-way search tree)， 其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。常见的有4种特殊形式：2-3树、2-3-4树、B树和B+树。这里主要介绍B树和B+树，因为2-3树、2-3-4树都是B树的特例。

如下图所示是一颗2-3树：

3.3B树

1.定义

B树也称为B-树，B-树是一种平衡的多路查找树。

【定义】 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：

​ ①树中每个结点至多有m棵子树（至多m-1个关键字）；

​ ②若根结点不是叶子结点，则至少有两棵子树；

​ ③除根之外的所有非终端结点至少有⌈ m/2 ⌉课子树（至少⌈ m/2 ⌉-1个关键字）；

​ ④所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并

不存在，指向这些结点的指针为空。引入失败结点是为了便千分析B-树的查找性能）；

​ ⑤所有的非终端结点最多有m- 1个关键字。

【B树树高】 若n≥1,则对任意-棵包含n个关键字、高度为h、阶数为m的B树:

​ ①树高最高：因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足n≤(m- 1)(1 +m+m2 +…+mh-1)=mh-1,因此有h≥ logm(n+1)。

​ ②树高最低：若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点;第二层至少有2个结点;除根结点外的每个非终端结点至少有⌈m/2⌉棵子树，则第三层至少有2⌈m/2⌉个结点…第h+ 1层至少有2(⌈m/2 )h-1个结点，注意到第h+1层是不包含任何信息的叶结点。

对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1,由此有n+ 1≥2(⌈m/2⌉)h-1,即若树高最小，则h≤log⌈m/2⌉((n+1)/2)+ 1.

2.B树的相关操作

（1）查找

B树的查找包含两个基本操作:①在B树中找结点:②在结点内找关键字。

在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。

例如，在图中查找关键字42。

​ ①首先从根结点开始，根结点只有一个关键字， 且42>22, 若存在，必在关键字22的右边子树上，右孩子结点有两个关键字，而36<42 <45，则若存在，必在36和45中间的子树上，在该子结点中查到关键字42,查找成功)。

​ ②查找到叶结点时(对应指针为空指针),则说明树中没有对应的关键字，查找失败。

（2）插入

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

​ ①定位。利用前述的B树查找算法，找出插入该关键字的最低层中的某个非叶结点(在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意:插入位置一定是最低层中的某个非叶结点)。

​ ②插入。在B树中，每个非失败结点的关键宇个数都在区间[⌈ m/2 ⌉-1, m- 1]内。插入后的结点关键字个数小于m,可以直接插入; 插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，必须对结点进行分裂。

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

对于m=3的B树，所有结点中最多有m-1=2个关键字，若某结点中已有两个关键字，则结点已满，如图中（a)所示。插入一个关键字60后，结点内的关键字个数超过了m-1,如图中(b)所示，此时必须进行结点分裂，分裂的结果如图中©所示。

（3）删除

B树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数>⌈m/2⌉-1,因此将涉及结点的“合并”问题。当被删关键字在终端结点(最低层非叶结点)中时，有下列三种情况:

①直接删除关键字。若被删除关键字所在结点的关键字个数≥⌈m/2⌉，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

②兄弟够借。若被删除关键字所在结点删除前的关键字个数=⌈m/2⌉-1,且与此结点相邻的右(或左)兄弟结点的关键字个数≥⌈m/2⌉,则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法),以达到新的平衡。如图中删除4阶B树的关键字65,右兄弟关键字个数≥⌈m/2⌉=2,将71取代原65的位置，将74调整到71的位置。

③兄弟不够借。若被删除关键字所在结点删除前的关键字个数=⌈m/2⌉-1，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉- 1,则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。在图中删除4阶B树的关键字5，它及其右兄弟结点的关键字个数=⌈m/2⌉-1=1,故在5删除后将60合并到65结点中。

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0 (根结点关键字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根:若双亲结点不是根结点，且关键字个数减少到⌈m/2⌉- 2，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。

3.4B+树

1.定义

B+树是应数据库所需而出现的-种B树的变形树。

【性质】 一棵m阶的B+树需满足下列条件:

​ ①每个分支结点最多有m棵子树(孩子结点)；

​ ②非叶根结点至少有两棵子树，其他每个分支结点至少有⌈ m/2 ⌉棵子树；

​ ③结点的子树个数与关键字个数相等；

​ ④所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来；

​ ⑤所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。

【B+树的查找】 通常在B+树中有两个头指针: 一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对B+树进行两种查找运算: 一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

【应用范围】 B+树的查找、插入和删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

2.B树与B+树的比较

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树中，叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的。

四.散列表

4.1散列表的查找

【哈希方法】 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。

【哈希函数】 哈希方法中使用的转换函数，称之为哈希函数。

【哈希表(杂凑表)】 按上述思想构造的表

【基本思想】 记录的存储位置与关键字之间存在对应关系，Loc(i)=H(keyi)→哈希函数。

【优点】 查找速度极快，时间复杂度为O(1),查找效率与元素个数n无关

【冲突】 不同的关键码映射到同一个哈希地址。key1≠key2，但H(key1)=H(key2)。

​ 例如：对于序列（14，23，39，9，25，11），采用哈希函数H(k)=k mod 7。

​ ①H(14)=14%7=0，插入表中0号位；

​ ②H(23)=23%7=2，插入表中2号位；

​ ③H(39)=39%7=4，插入表中4号位；

​ ④H(9)=9%7=2，应插入表中2号位，而此时2号位已经存有元素23，发生冲突；

​ ⑤H(25)=25%7=4，应插入表中4号位，而此时4号位已经存有元素39，发生冲突；

​ ⑥H(11)=11%7=4，应插入表中4号位，而此时4号位已经存有元素39，发生冲突；

【同义词】 具有相同函数值的两个关键字，如上图例子中，25和11就称为同义词。

【减少冲突的方式】 ①构造好的哈希函数；②制定一个好的解决冲突方案（因为冲突是不可能避免的）。

4.2哈希函数的构造

对哈希函数的构造要求根据元素集合的特性构造，所构造的函数地址空间尽量小、均匀。

4.2.1 常用构造方法

【直接定址法】 Hash(key) = a·key + b (a、b为常数)

​ ①优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。

​ ②缺点：要占用连续地址空间，空间效率低。

例如，给定序列{100，300，500，700，800，900}，哈希函数Hash(key)=key/100，构造哈希表结果如下：

【数字分析法】 选取数码分布较为均匀的若干位作为散列地址，这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

【平方取中法】 取关键字的平方值的中间几位作为散列地址，具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

【除留余数法】 Hash(key)=key mod p (p是一个整数)。该方法的关键是选取有个合适的p值，一般情况下，若表长为m，取p为小于等于m的最大质数。

4.2.2 冲突处理-开放定址法

开放定址法的基本思想为有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。其冲突函数为Hi=(Hash(key)+di) mod m ( 1≤i < m )

【线性探测法】 在该方法中：

例如，关键码集为 {47，7，29，11，16，92，22，8，3}，设哈希表表长为m=11，哈希函数为Hash(key)=key mod 11，构造哈希表并解决冲突。

解： ① 47、7、11、16、92没有冲突；

​ ② Hash(29)=7，有冲突，由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入；

​ ③ 关键字“3” 连续移动了3次，冲突了3次。

优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。

缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率。

【二次探测法】 对于上述方法产生的聚集现象，可采用二次探测法进行解决。在该方法中：

例如，关键码集为 {47，7，29，11，16，92，22，8，3}，设哈希表表长为m=11，哈希函数为Hash(key)=key mod 11，构造哈希表并解决冲突。

解： ①47，7，29，11，16，92，22，8没有冲突；

​ ②Hash(3)=3，哈希地址冲突，由H1=(Hash(3)+12) mod 11=4，仍然冲突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。

【伪随机探测法】 在该方法中：

4.2.3 冲突处理-链地址法

【基本思想】 相同哈希地址的记录链成一单链表，m个哈希地址就设m个单链表，然后用用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

【建立哈希表步骤】

​ ①取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行②解决冲突。

​ ②利用链表的前插法或后插法将该元素插入此链表。

【优点】 ①非同义词不会冲突，无“聚集”现象；

​ ②链表上结点空间动态申请，更适合于表长不确定的情况。

4.3哈希表的查找

【比较步骤】

【例子】 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等。

解： ①用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m。

​ 在此方法中，ASL=(16+2+33+4+9)/12=2.5。

​ ②用链地址法处理冲突

在此方法中，ASL=(16+24+3+4)/12=1.75。

【效率分析】 使用平均查找长度ASL来衡量查找算法，ASL取决于以下几个因素：

​ ①哈希函数；

②处理冲突的方法；

​ ③哈希表的装填因子。α越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

【三种方法比较】 对哈希表技术具有很好的平均性能，优于一些传统的技术；链地址法优于开地址法；除留余数法作哈希函数优于其它类型函数。