数据结构 第9章 查找 什么是查找？？ 静态查找 动态查找 哈希表 数据结构.

Presentation on theme: "数据结构 第9章 查找 什么是查找？？ 静态查找 动态查找 哈希表 数据结构."— Presentation transcript:

1 数据结构 第9章 查找 什么是查找？？ 静态查找 动态查找 哈希表 数据结构

2 集合关系 查找表（search table） 数据结构

3 查找的基本概念 查找表（Search Table）：是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。
对查找表经常进行的操作有： 　　（1）查询某个"特定的"数据元素是否在表中； 　　（2）查找某个"特定的"数据元素的各种属性； 　　（3）在查找表中插入一个数据元素； 　　（4）从查找表中删除某个数据元素。 静态查找表（Static Search Table）：在使用时主要作前两种统称为“查找”的操作。即查找的前后不会改变查找表的内容。 动态查找表（Dynamic Search Table） 数据结构

4 关键字：是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。若此关键字可以唯一地标识一个元素，则称此关键字为主关键字（Primary key）（对不同的元素，其主关键字均不同）。反之，称用以识别若干元素的关键字为次关键字（secondary key）。当数据元素只有一个数据项时，其关键字即为该数据元素的值。 数据结构

5 查找算法的评价标准：查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。
查找（searching）：是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若表中存在这样的一个元素，则称查找是成功的，此时查找的结果为给出整个数据元素的信息，或指示该数据元素在查找表中的位置；若表中不存在这样的元素，则称查找不成功，此时查找的结果可给出一个“null”元素（或空指针）。 查找算法的评价标准：查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。 对于具有n个数据元素的集合，查找某元素成功的平均查找长度为： ASL＝ 数据结构

6 静态查找表 顺序表的查找（顺序查找） 有序表的查找（折半查找） 索引顺序表的查找（分块查找） 数据结构

7 顺序表的查找（顺序查找） 顺序表的查找将集合中的数据元素构成一个序列，以顺序表或线性链表表示静态查找表。
顺序查找的过程：从表的一端开始，顺序（逐个）扫描线性表，依次将扫描到的结点关键字和给定值Key相比较，若当前扫描到的结点关键字与Key相等，则查找成功；若扫描结束后，仍未找到关键字等于Key的结点，则查找失败。 数据结构

8 顺序查找的实现 #define LIST_INIT_SIZE 100
//线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }SSTable; 数据结构

9 int Search_Seq(SSTable ST,KeyType key) { int k=ST.len-1;
while (k>=0 && ST.elem[k]!=key ) k--; return(k); } int Search_Seq(SSTable ST,KeyType key) { int k=ST.len-1; ST.elem[0].key = key; //哨兵 while (ST.elem[k]!=key ) k--; return(k); } 数据结构

10 顺序查找算法分析 由顺序查找过程可见，查找表中最后一个元素时，仅需比较一次；查找表中第一个元素时，需比较n次；对任一元素i需比较n-i+1次。 设顺序表中每个记录的查找概率相同，即Pi=1/n，则顺序查找算法查找成功时的平均查找长度为： ASLseq= 可以证明，在不等概率查找的情况下，ASLseq 在 时取极小值，这就是说，如果事先已经知道查找表中各个关键字的查找概率的话，则应该按照关键字的查找概率从小而大存放数据元素。 数据结构

11 有序表的查找（折半查找） 折半查找要求线性表的结点按其关键字从小到大（或从大到小）按序排列，并采用顺序存储结构。
采用折半查找时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较: l[mid]. Key = x，搜索成功； l[mid]. Key > x，把搜索区间缩小到表的前半部分，再继续进行对分搜索； l[mid]. Key < x，把搜索区间缩小到表的后半部分，再继续进行对分搜索。 数据结构

12 每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。
例 有一组有序的线性表如下： （10，14，20，32，45，50，68，90，100，120） 下面分析在其中二分查找关键字20的过程。 数据结构

13 下面分析二分查找关键字95的过程: 数据结构

14 折半查找的实现 折半查找的主要步骤为： （1）置初始查找范围：low=1，high=n
（2）求查找范围中间项：mid=(low+high)/2 （3）将指定的关键字值k与中间项a[mid].key比较 若相等，查找成功，找到的数据元素为此时mid 指向的位置； 若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1; 若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1; （4）重复步骤（2）、（3）直到查找成功或查找范围空（low>high），即查找失败为止。 数据结构

15 索引顺序表的查找（分块查找） 分块查找(Blocking Search)又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。
(2)索引表 抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即:ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表L中的起始位置。由于表L是分块有序的，所以索引表是一个递增有序表。 数据结构

16 【例】例如，图9.2就是一个带索引的分块有序的线性表。其中线性表L共有20个结点，被分成3块，第一块中最大关键字25小于第二块中的最小关键字27，第二块中最大关键字55小于第三块中的最小关键字60。
数据结构

17 分块查找的基本思想 分块查找的基本思想是： （1）首先查找索引表 　　索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。 分块查找方法通过将查找缩小在某个块中从而提高了查找的效率，其查找的效率由两部分组成，一是为确定某一块对索引表的平均查找长度El，二是块内查找所需的平均查找长度Eb 。 数据结构

18 typedef struct /*索引表结点类型*/ { datatype key; int address; } indexnode;
分块查找的实现 #include "seqlist.h" typedef struct /*索引表结点类型*/ { datatype key; int address; } indexnode; /* 分块查找 */ int indexseqsearch(seqlist l,indexnode index[],int m,datatype key) {/*分块查找关键字为Key的记录，索引表为index[0..m-1]*/ int i=0,j,last; while (i<m && key>index[i].key) i++; if (i>=m) return -1; else{ /*在顺序表中顺序查找*/ 数据结构

19 else j=index[i+1].address-1; /*j初始时指向本块的最后一个结点*/
if (i==m-1) j=l.len-1; else j=index[i+1].address-1; /*j初始时指向本块的最后一个结点*/ while (j>=index[i].address && key!=l.data[j] ) j--; /*从后向前逐个查找*/ if (j<index[i].address) return -1; else return j; } 数据结构

20 二叉排序树 二叉排序树的定义 　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 　　上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树 在线性表的三种查找方法中二分查找法具有最高的查找效率，但是它只适合于顺序存储结构，这给查找表中数据的增、删带来不便。 数据结构

21 退化成单链表 两棵二叉排序树 例 （a） （b） 二叉排序树示例 60 40 80 30 50 68 98 36 30 40 60 58
数据结构

22 对于一棵给定的二叉排序树，树中的查找运算算法可描述如下： （1）当二叉树为空树时，查找失败；
基于二叉排序树的查找运算 对于一棵给定的二叉排序树，树中的查找运算算法可描述如下： （1）当二叉树为空树时，查找失败； （2）如果二叉排序树根结点的关键字等于待查找的关键字，则查找成功； （3）如果二叉排序树根结点的关键字小于待查找的关键字，则用相同的方法继续在根结点的右子树中查找； （4）如果二叉排序树根结点的关键字大于待查找的关键字，则用相同的方法继续在根结点的左子树中查找。 数据结构

23 二叉排序树的查找实现 BiTree SearchBST(BiTree 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); 　　　　　　// 返回在右子树中继续查找所得结果 　} // SearchBST 数据结构

24 在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度 。
二叉排序树的查找算法分析 在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度 。 因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。 30 40 46 50 55 60 65 70 75 80 60 40 70 30 50 65 80 46 55 75 （a） （b） 两棵具有不同检索效率的二叉排序树 数据结构

25 对于图（b）所示的二叉排序树其平均查找长度为： ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.5
在最坏的情况下，含有n个结点的二叉排序树退化成一棵深度为n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序查找相同，即ASL=（n+1）/2。在最好的情况下，二叉排序树形态比较匀称，对于含有n个结点的二叉排序树，其深度不超过log2n，此时的平均查找长度为O（log2n）。 例如，对于上图中的两棵二叉排序树，其深度分别是4和10，在查找失败的情况下，在这两棵树上的最大比较次数分别是4和10；在检索成功的情况下，若检索每个结点的概率相等，则对于图（a）所示的二叉排序树其平均查找长度为： ASLa= = 对于图（b）所示的二叉排序树其平均查找长度为： ASLb=（ ）/10=5.5 数据结构

26 假设待插入的数据元素为x，则二叉排序树的插入算法可以描述为： 若二叉排序树为空，则生成一个关键字为x的新结点，并令其为二叉排序树的根结点；
基于二叉排序树的插入运算 假设待插入的数据元素为x，则二叉排序树的插入算法可以描述为： 若二叉排序树为空，则生成一个关键字为x的新结点，并令其为二叉排序树的根结点； 否则，将待插入的关键字x与根结点的关键字进行比较，若二者相等，则说明树中已有关键字x，无须插入； 若x小于根结点的关键字，则将x插入到该树的左子树中，否则将x插入到该树的右子树中去。 将x插入子树的方法与在整个树中的插入方法是相同的，如此进行下去，直到x作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。 数据结构

27 对于输入实例（30，20，40，10，25，45）， 算法9.6创建二叉排序树的过程如下：
（a）空树 30 20 （c）插入20 30 20 40 （d）插入40 30 （b）插入30 30 20 40 10 （e）插入10 30 20 40 10 25 （f）插入25 30 20 40 10 25 45 （g）插入45 数据结构

28 二叉排序树的插入实现 Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
/*在根指针T所指二叉查找树中递归查找关键字等于key的 数据元素,若查找成功,则指针p指向该数据元素结点,并返回 TRUE,否则指针p指向查找路径上访问的最后一个结点并返回 FALSE,指针f指向T的双亲,其初始调用值为NULL*/ 　if (!T) { p = f; return FALSE; }// 查找不成功 　　else if ( key == T->data.key ) 　　　{ p = T; return TRUE; }　　　 // 查找成功 　　else if ( key < T->data.key ) 　　　return SearchBST (T->lchild, key, T, p ); 　　else return SearchBST (T->rchild, key, T, p ); } // SearchBST 数据结构

29 由上述过程可知，由无序序列输入建立二叉排序树，再对其进行中序遍历可得一个有序序列，这种方法便是树排序。
Status Insert BST(BiTree &T, ElemType e ){ 　if (!SearchBST ( T, e.key, NULL, p ){ // 查找不成功 　　　s = (BiTree)malloc(sizeof(BiTNode)); 　　　if (!s) exit(1);　　　　　　　　 // 存储分配失败 　　　s->data = e; s->lchild = s->rchild = NULL; 　　　if ( !p ) T = s; 　　　　// 插入 *s 为新的根结点 　　　else if ( e.key < p->data.key ) 　　　　p->lchild = s;　　　　// 插入 *s 为 *p 的左孩子 　　　else p->rchild = s; 　　// 插入 *s 为 *p 的右孩子 　　　return TRUE; 　} // if 　else return FALSE;//树中已有关键字相同的结点，不再插入 　} // Insert BST 由上述过程可知，由无序序列输入建立二叉排序树，再对其进行中序遍历可得一个有序序列，这种方法便是树排序。 数据结构

30 （1）待删除结点为叶结点，则直接删除该结点即可。若该结点同时也是根结点，则删除后二叉排序树变为空树。下图给出了一个删除叶结点的例子；
基于二叉树的删除运算 从二叉排序树中删除一个结点*p时，相当于删除有序序列中的一个元素，但要保证删除后所得的二叉树仍然满足BST性质。即应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。 （1）待删除结点为叶结点，则直接删除该结点即可。若该结点同时也是根结点，则删除后二叉排序树变为空树。下图给出了一个删除叶结点的例子； 60 40 70 30 50 36 80 45 75 20 60 40 70 30 50 36 80 45 删除叶子结点20和75 数据结构

31 （2）待删除结点只有左子树（或右子树），而无右子树（或左子树）。根据二叉排序树的特点，可以直接将其左子树的根结点或右子树的根结点替代被删除结点的位置。
60 40 70 30 50 36 80 45 75 20 60 40 70 30 45 36 80 75 20 删除只有左子树的单孩子结点50 数据结构

32 （3）待删除结点. p既有左子树又有右子树。根据二叉排序树的特点，可以1）令. p的左子树为. p的左子树，而. p的右子树为
（3）待删除结点*p既有左子树又有右子树。根据二叉排序树的特点，可以1）令*p的左子树为*p的左子树，而*p的右子树为*s的右子树；2）用被删除结点中序下的前趋结点（或其中序下的后继结点）代替被删除结点，同时删除其中序下的前趋结点（或中序下的后继结点）。 60 40 70 30 50 36 80 45 75 20 60 45 70 30 50 36 80 75 20 60 36 70 30 50 80 45 75 20 60 70 30 50 36 80 45 75 20 删除具有2棵子树的结点40 数据结构

33 Status DeleteBST(BiTree &T, KeyType key){ if (!T) return FALSE; else {
二叉排序树的删除实现 Status DeleteBST(BiTree &T, KeyType key){ if (!T) return FALSE; else { if (EQ(key, T->data.key)) return Delete(T); else if (LT(key, T->data.key)) return DeleteBST(T->lchild, key); else return DeleteBST(T->rchild, key); } } // DeleteBST 数据结构

34 Status Delete(BiTree &p) { if (!p->rchild) {// 右子树空则只需重接它的左子树
q = p; p = p->lchild; free(q); }else if (!p->lchild) { // 只需重接它的右子树 q = p; p = p->rchild; free(q); } else { // 左右子树均不空 q = p; s = p->lchild; while (s->rchild) // 转左，然后向右到尽头 { q = s; s = s->rchild; } p->data = s->data; // s指向被删结点的“后继” if (q != p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s);} return TRUE; } // Delete 数据结构

35 平衡二叉树 二叉排序树上实现的查找等基本操作的平均时间虽然为O（log2n），但在最坏情况下，二叉排序树退化成一个具有单个分支的单链表，此时树高增至n，这将使这些操作的时间相应地增至O（n）。为了避免这种情况发生，人们研究了许多种动态平衡的方法，包括如何建立一棵“好”的二叉排序树；如何保证往树中插入或删除结点时保持树的“平衡”，使之既保持二叉排序树的性质又保证树的高度尽可能地为O（log2n）。因此本节将介绍一种特殊的二叉树：平衡二叉树。 数据结构

36 平衡因子：即为二叉树中某个结点的左子树高度与右子树高度之差。由此可知，平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树。
平衡二叉树又称为AVL树，它或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。 平衡因子：即为二叉树中某个结点的左子树高度与右子树高度之差。由此可知，平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树。 数据结构

37 如何生成（动态维护）平衡二叉树？ 例（13，24，37，90，53） 数据结构

38 AVL树上因插入新结点而导致失去平衡时的调整方法。
为叙述方便，假设在AVL树上因插入新结点而失去平衡的最小子树的根结点为A（即A为距离插入结点最近的，平衡因子不是-1、0和1的结点）。失去平衡后的调整操作可依据失去平衡的原因归纳为下列四种情况分别进行。 数据结构

39 （1）LL型平衡旋转：由于在A的左孩子的左子树上插入新结点，使A的平衡度由1增至2，致使以A为根的子树失去平衡，如下图所示。此时应进行一次顺时针旋转，“提升”B（即A的左孩子）为新子树的根结点，A下降为B的右孩子，同时将B原来的右子树Br调整为A的左子树。 A 2 B 1 BL Br Ar h A B BL Br Ar h LL型 数据结构

40 （2）RR型平衡旋转：由于在A的右孩子的右子树上插入新结点，使A的平衡度由-1变为-2，致使以A为根的子树失去平衡，如下图所示。此时应进行一次逆时针旋转，“提升”B（即A的右孩子）为新子树的根结点，A下降为B的左孩子，同时将B原来的左子树BL调整为A的右子树。 A -2 B -1 Br BL AL h RR型 A B Br AL BL h 数据结构

41 （3）LR型平衡旋转：由于在A的左孩子的右子树上插入新结点，使A的平衡度由1变成2，致使以A为根的子树失去平衡，如下图所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升”C（即A的左孩子的右孩子）为新子树的根结点；A下降为C的右孩子；B变为C的左孩子；C原来的左子树CL调整为B现在的右子树；C原来的右子树Cr调整为A现在的左子树 A -1 B Ar h BL CL h-1 Cr C A 2 B -1 Ar h BL LR型 C CL h-1 Cr 1 数据结构

42 （4）RL型平衡旋转：由于在A的右孩子的左子树上插入新结点，使A的平衡度由-1变成-2，致使以A为根的子树失去平衡，如下图所示。此时应进行两旋转操作（先顺时针，后逆时针），即“提升”C（即A的右孩子的左孩子）为新子树的根结点；A下降C的左孩子；B变为C的右孩子；C原来的左子树CL调整为A现在的右子树；C原来的右子树Cr调整为B现在的左子树。 B -1 A Br h AL CL h-1 Cr C A -2 B 1 Br h AL RL型 CL h-1 Cr C 数据结构

43 综上所述，在平衡的二叉排序树t上插入一个新的数据元素x的算法可描述如下：
（一）若AVL树t为空树，则插入一个数据元素为x的新结点作为t的根结点，树的深度增1； （二）若x的关键字和AVL树t的根结点的关键字相等，则不进行插入； （三）若x的关键字小于AVL树t的根结点的关键字，则将x插入在该树的左子树上，并且当插入之后的左子树深度增加1时，分别就下列不同情况进行分情形处理： （1）若AVL树的根结点的平衡因子为-1（右子树的深度大于左子树的深度），则将根结点的平衡因子调整为0，并且树的深度不变； 数据结构

44 （2）若AVL树的根结点的平衡因子为0（左、右子树的深度相等），则将根结点的平衡因子调整为1，树的深度同时增1；
（3）若AVL树的根结点的平衡因子为1（左子树的深度大于右子树的深度），则当该树的左子树的根结点的平衡因子为1时需进行LL型平衡旋转；当该树的左子树的根结点的平衡因子为-1时需进行LR型平衡旋转。 （四）若x的关键字大于AVL树t的根结点的关键字，则将x插入在该树的右子树上，并且当插入之后的右子树深度增加1时，需要分别就不同情况进行处理。其处理操作和（三）中所述相对称。 数据结构

45 例：结点序列（120，80，30，90，45，60）逐个插入一棵空的AVL树的过程如下：
120 1 120 2 80 80 80 1 30 120 30 80 -1 80 80 80 30 120 1 30 -1 120 1 30 -2 120 1 45 120 1 90 45 90 45 -1 90 30 60 90 60 数据结构

46 平衡二叉排序树的实现：P236 数据结构

47 B-树 B-树：是一种平衡的多路查找树，在文件系统中，已经成为索引文件的一种有效结构，并得到广泛的应用。 数据结构

48 一棵m阶（m3）B-树，或为空树，或为满足下列特性的m叉树： （1）树中每个结点至多有m棵子树；
（2）若根结点不是叶子结点，则至少有两棵子树； （3）所有的非终端结点中包含下列信息 （n，p0，k1，p1，k2，p2，…，kn，pn） 其中：ki（1in）为关键字，且ki<ki+1（1in）；pj（0jn）为指向子树根结点的指针，且pj（0j<n）所指子树中所有结点的关键字均大于等于Kj并小于kj+1，pn所指子树中所有结点的关键字均大于kn，n（m/2-1nm-1）为关键字的个数（n+1为子树个数）。 数据结构

49 （4）除根结点之外所有非终端结点至少有m/2棵子树；
（5）所有的叶子结点都出现在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。 root 例：一棵3阶的B-树 1 90 2^10^19^ 1^22^ 1^43^ 1^53^ 1^60^ 1^75^ 1^88^ 1^97^ 数据结构

50 B-树的查找过程是一个顺指针查找结点和在结点的关键字中进行交叉进行的过程。
root 1 90 2^10^19^ 1^22^ 1^43^ 1^53^ 1^60^ 1^75^ 1^88^ 1^97^ 数据结构

51 Result SearchBTree(BTree T,KeyType K){
p = T; q = NULL; found = FALSE; i = 0; while (p && !found) { i = Search(p, K); if (i>0 && p->key[i]==K) found = TRUE; else { q = p; p = p->ptr[i]; } j++; } if (found) { // 查找成功 R.pt = p; R.i = i; R.tag = 1; } else { // 查找不成功，返回插入位置信息 R.pt = q; R.i = i; R.tag = 0; return R; } // SearchBTree 数据结构

52 基于B-树的插入运算 在B-树中插入关键字k的方法是：首先在树中查找k，若找到则直接返回；否则查找操作必失败于某个叶子结点上，利用函数SearchBTree（）的返回值*pt及i可以确定关键字k的插入位置，即将k插入到pt所指的叶结点的第i个位置上。 若该叶结点原来是非满（结点中原有的关键字总数小于m-1）的，则插入k并不会破坏B-树的性质，故插入k后即完成了插入操作。例如，下图（a）所示的5阶B-树的某结点（假设为p结点）中插入新的关键字150时，可直接得到图（b）所示的结果。 数据结构

53 若p所指示的叶结点原为满，则k插入后keynum=m，破坏了B-树的性质（1），故须调整使其维持B-树的性质不变。调整的方法是将违反性质（1）的结点以中间位置的关键字key[m/2]为划分点，将该结点（即p） （m，p0，k1，p1，…，km，pm） 分裂为两个结点，左边结点为（m/2-1，p0，k1，…km/2-1，pm/2-1），右边结点为（m-m/2，pm/2，km/2+1，…，km，pm），同时把中间关键字km/2插入到双亲结点中。于是双亲结点中指向被插入结点的指针pre改成pre、km/2、pre’三部分。指针pre指向分裂后的左边结点，指针pre’指向分裂后的右边结点。由于将km/2插入双亲时，双亲结点亦可能原本为满，若如此，则需对双亲做分裂操作。 数据结构

54 插入100以后 插入100以前 km/2 2 … 80 220… 3 … 80 120 220 … pre p pre pre’
2 … … 3 … … pre p pre pre’ 数据结构

55 （a）插入6、8、15、16 （b）插入22 （c）插入10、18、32
如果初始时B-树为空树，通过逐个向B-树中插入新结点，可生成一棵B-树。下图说明了一棵5阶B-树的生长过程。 15 15 6 8 16 22 （a）插入6、8、15、16 （b）插入 （c）插入10、18、32 15 20 15 20 6 8 10 16 18 22 32 22 32 50 56 （d）插入 （e）插入12、19、40、 （f）插入56 20 9 15 32 40 6 8 10 12 6 8 10 12 22 26 36 38 （g）插入9、26、36、52、 （h）插入38 数据结构

56 在B-树上删除数据元素x的关键字x.key分两步完成： （1）利用前述B-树的查找算法找出关键字所在结点
（a）在叶结点上删除关键字； （b）在非叶结点上删除关键字。 此时，根据B-树的特性可知，可以用ki指针pi 所指子树中最小关键字y代替ki，然后在相应的 结点中删除y，或用ki左边指针pi-1所指子树中 最大关键字x代替ki，然后在相应的结点中删除 x。如下图。 数据结构

57 50 28 8 40 60 80 3阶B-树中删除50以60代替50 60 28 8 40 80 数据结构

58 上面非叶子结点的删除转化为了叶子结点的删除，下面主要讨论删除B-树叶子上面一层结点中的关键字的方法，具体分三种情形：
1）被删关键字所在叶子上面一层结点中的关键字数目不小于m/2，则只需要从该结点中删去关键字ki和相应的指针pi，树的其它部分不变。 8 40 28 50 60 80 删除60与115 例： 90 8 40 28 50 80 数据结构

59 2）被删关键字所在叶子上面一层结点中的关键字数目等于m/2-1，而与该结点相邻的右兄弟结点（或左兄弟结点）中的关键字数目大于m/2-1，则需要将其右兄弟的最小关键字（或其左兄弟的最大关键字）移至双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移至被删关键字所在的结点中。 90 8 40 28 50 80 删除90 120 8 40 28 200 50 80 数据结构

60 3）被删关键字所在叶子上面一层结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于m/2-1，则第 2）种情况中采用的移动方法将不奏效，此时须将被删关键字所有结点与其左或右兄弟合并。不妨设该结点有右兄弟，但其右兄弟地址由双亲结点指针pi所指，则在删除关键字之后，它所在结点中剩余的关键字和指针加上双亲结点中的关键字ki一起合并到pi所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。 120 8 40 28 200 50 80 删除120 8 40 28 85 50 80 数据结构

61 哈希表 在已经介绍过的线性表、树等数据结构中，数据元素的存放位置和数据元素之间没有任何关系，因此查找过程是一系列的比较过程。
如果我们构造一个查找表，使数据元素的存放位置和数据元素的关键字之间存在某种关系，则我们可以直接由数据元素的关键字得到该数据元素的存储位置。这样的查找表就是哈希表。 数据元素的关键字与数据元素的存储位置之间的映射函数称为哈希函数。 数据结构

62 例：对于关键字序列{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}，可设关键字的哈希函数如下：
F(key)=|ord(CH1)-ord(‘A’）+1/2|， 其中，CH1为关键字中第一个字母，ord为字符的次序函数。 数据结构

63 因此，对于哈希表，需要研究下面两个主要问题： （1）选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数；
哈希表中经常会出现对于两个不同关键字xi，xj，却有H（xi）=H（xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。碰撞的两个（或多个）关键字称为同义词（相对于函数H而言）。 因此，对于哈希表，需要研究下面两个主要问题： （1）选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数； （2）确定解决冲突的方法。 数据结构

64 哈希函数的构造 直接定址法 取关键字或关键字的某个线性函数值为哈希地址，即：H（key）=key或H（key）=a·key+b
直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，不会产生冲突。但实际应用中能采用直接定址的情况极少。 数字分析法 如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行分析，取其中"分布均匀"的若干位或它们的组合作为哈希表的地址。 数据结构

65 平方取中法 取关键字平方后的中间几位为Hash地址，所取的位数和Hash地址位数相同。这是一种较常用的构造Hash函数的方法。因为通常在选定Hash函数时不一定能知道关键字的全部情况，难以决定取其中哪几位比较合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机每布的关键字得到的Hash地址也是随机的。 折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为Hash地址，称为折叠法。 关键字位数很多且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到Hash地址。 数据结构

66 例：S={5，21，65，22，69}，若H（x）=x % 7，则可以得到：
除留余数法 H（key）=key％p 例：S={5，21，65，22，69}，若H（x）=x % 7，则可以得到： 21 22 65 5 69 随机数法 当关键字不等长时，可取关键字的某个伪随机函数值作为哈希地址。 　　　Hash(key) = random(key) 数据结构

67 冲突的处理 开放定址法 其基本做法是在发生冲突时，按照某种方法继续探测基本表中的其它存储单元，直到找到一个开放的地址（即空位置）为止。显然这种方法需要用某种标记区分空单元与非空单元。 开放定址法的一般形式可表示为： Hi（k）=（H（k）+di）mod m（i=1,…k（km-1）） 其中，H（k）为键字为k的直接哈希地址，m为哈希表长，di为每次再探测时的地址增量。 当di=1，2，3，…，m-1时，称为线性探测再散列；当di=12，-12，22，-22，…，k2，-k2（km/2）时，称为二次探测再散列；当di=随机数序列时，称为随机探测再散列。 数据结构

68 再哈希法 采用再哈希法解决冲突的做法是当待存入散列表的某个元素k在原哈希函数H（k）的映射下与其它数据发生碰撞时，采用另外一个Hash函数Hi（k）（i=1，2，…，n）计算k的存储地址（Hi均是不同的Hash函数），这种计算直到冲突不再发生为止。 拉链法 拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]，凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。 数据结构

69 哈希表的查找和插入 在查找时，首先应计算给定值的哈希函数值， 若表中该位置上没有记录，则表明关键字等于给定值的记录不存在；
若该位置上的记录的关键字和给定值不等，则依据建表时设定的处理冲突的方法寻找“下一个”地址，直至查找成功(即某个位置上的记录的关键字等于给定值)或查找不成功（哈希表中不存在关键字等于给定值的记录），并且在查找不成功的情况下，在该地址插入新的记录。 数据结构

70 Status SearchHash (HashTable H, KeyType kval, int &p, int &c){ // p指示待查记录在表中位置或插入位置,c用以计冲突次数 　　p = Hash(kval);　　　　　// 求得哈希地址 　　while ( H.elem[p].key != NULLKEY　　　　　　&& ( H.elem[p].key != kval) ) 　　　 collision(p, ++c);//求得下一探查地址p 　　if ( H.elem[p].key == kval ) 　　　return SUCCESS; 　　　　　　　　　　 else return UNSUCCESS; } // SearchHash 数据结构

71 Status InsertHash (HashTable &H, Elemtype e){ 　　c = 0; 　　if ( HashSearch(H, e.key, j, c)==SUCCESS ) 　　　return DUPLICATE;　　　　　 　　else if ( c < hashsize[H.sizeindex]/2 ) { 　　　　// 冲突次数c未达到上限，（阀值c可调） 　　　H.elem[j] = e; ++H.count; return OK; 　　} // if 　　else RecreateHashTable(H); // 重建哈希表 　} // InsertHash 数据结构