第9章 查找 9.1 基本概念和术语 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 9.5 小结 9.2.1 顺序查找 9.2.2 折半查找 9.2.3 分块查找 9.3 动态查找表 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树和B+树 9.4 哈希表 9.4.1 什么是哈希表 9.4.2 哈希函数的构造方法 9.4.3 处理冲突的方法 9.4.5 哈希表的查找和分析 9.5 小结

9.1 基本概念和术语 1 数据项 (也称项或字段): 是具有独立含义的标识单位，是数据不可分割的最小单位。 2 组合项 9.1 基本概念和术语 1 数据项 (也称项或字段): 是具有独立含义的标识单位，是数据不可分割的最小单位。 2 组合项 由若干项、组合项构成。 3 数据元素（记录） 是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。

9.1 基本概念和术语 4关键码（key） 关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。 9.1 基本概念和术语 4关键码（key） 关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。 能唯一确定一个数据元素（记录）的关键码，称为主关键码(Primary Key)；不能唯一确定一个数据元素（记录）的关键码，称为次关键码(Secondary Key)。

9.1 基本概念和术语 静态查找表(Static Search Table)：仅对查找表进行查找操作，而不能改变的表； 9.1 基本概念和术语 5 查找表(Search Table ) 是由具有同一类型（属性）的数据元素组成的集合（又称为字典）。分为静态查找表和动态查找表两类: 静态查找表(Static Search Table)：仅对查找表进行查找操作，而不能改变的表； 动态查找表(Dynamic Search Table)：对查找表除进行查找操作外，允许向表中插入或删除表中数据元素的表。

9.1 基本概念和术语 6.查找(searching) 按给定的某个值kx，在查找表中确定一个其关键码等于kx的数据元素（记录）。

9.1 基本概念和术语 7 数据元素类型说明 typedef struct {/* 出生日期类型定义 */ 9.1 基本概念和术语 7 数据元素类型说明 typedef struct {/* 出生日期类型定义 */ char year[5]； /* 年：用字符型表示，宽度为4个字符 */ char month[3]； /* 月：字符型，宽度为 2 */ char date[3]； /* 日：字符型，宽度为 2 */ }BirthDate； typedef struct {/* 数据元素类型定义 */ char number[7]； /* 学号：字符型，宽度为6 */ char name[9]； /* 姓名：字符型，宽度为8 */ char sex[3]； /* 性别：字符型，宽度为2 */ BirthDate birthdate；/*出生日期:构造类型 */ char comefrom[21]； /* 来源：字符型，宽度为20 */ int results； /* 成绩：整型，宽度由 “C语言”决定 */ } ElemType；

9.1 基本概念和术语 8 查找表的类型定义 例：用线性表表示查找表： （1）用顺序表来表示查找表： 9.1 基本概念和术语 8 查找表的类型定义 例：用线性表表示查找表： （1）用顺序表来表示查找表： typedef MAXSIZE 1000 typedef struct{//顺序存储结构 ElemType elem[MAXSIZE+1]； int length; }SStable; （2）用单链表表示查找表 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; 用其它形式表示的线性表的类型定义在以后的章节中解释。

9.1 基本概念和术语 说明： 本章以后讨论中，涉及的关键码类型和数据元素类型统一说明如下： typedef struct { 9.1 基本概念和术语 说明： 本章以后讨论中，涉及的关键码类型和数据元素类型统一说明如下： typedef struct { KeyType key；/*关键码字段，可以是整型、字符型、构造型等*/ …… /* 其它字段 */ } ElemType；

9.2 静态查找表 9.2.1 顺序查找 9.2.2 折半查找 9.2.3 分块查找

9.2 静态查找表 （基于线性表的查找） 静态查找表结构 静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。 typedef MAXSIZE 1000 typedef struct{//顺序存储结构 ElemType elem[MAXSIZE+1]； int length; }SStable; typedef struct LNode{//链式存储结构 ElemType data; struct LNode *next; }LNode,*LinkList;

9.2 静态查找表 （基于线性表的查找） 9.2.2 顺序查找(Sequential Search) 查找方法：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息。 例：给定kx=56,90，在下表中进行顺序查找。 1 2 3 4 5 6 7 8 9 10 11 19 13 37 21 05 56 75 92 64 80 88

9.2 静态查找表 （基于线性表的查找） //不设置监视哨的顺序查找算法 9.2.1顺序查找 int search_Seq(SSTable ST，KeyType kx) { i=l.length; while (i>=1&&ST.elem[i].key!=kx) i--; return i; }

9.2 静态查找表 （基于线性表的查找） 9.2.1 顺序查找 【算法9.1】以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留空。 int search_Seq(SSTable ST，KeyType kx) { /*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在数组中的下标，否则返回0 */ ST.elem[0].key = kx；/* 监视哨*/ for( i = ST.length ; ST.elem[i].key != kx ；i-- )； return i； }

9.2 静态查找表 （基于线性表的查找） n ∑ ASL= Pi·Ci i=1 9.2.1 顺序查找 【性能分析】 其中：Pi为表中第i个数据元素的查找概率， Ci为表中第i个数据元素的关键码与给定值kx相等时，按算法定位关键码的比较次数。

9.2.2 顺序查找 (Sequential Search) 【性能分析】 查找成功时，顺序查找的平均查找长度为： ASL= Pi·(n-i+1) n ∑ i=1 = ·(n-i+1) １ ─ ｎ n+1 =─ 2 查找不成功时，关键码的比较次数总是n+1次。 算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为O(n)。

9.2.2 顺序查找(Sequential Search) 顺序查找缺点: 当n很大时，平均查找长度较大，效率低； 优点: 是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

9.2 静态查找表 （基于线性表的查找） 9.2.3有序表的折半查找 条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。 基本过程： 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

9.2 静态查找表 （基于线性表的查找） 9.2.3有序表的折半查找 例：已知含11个元素的有序表（关键字即为数据元素的值）： （05,13,19,21,37,56,64,75,80,88,92） 查找关键字21和85的数据元素。

9.2 静态查找表 （基于线性表的查找） 9.2.3有序表的折半查找 【算法9.2】int Search_Bin (SSTable ST，KeyType kx) { low=1；high=ST.length； while(low<=high) { mid=(low+high)/2； if(kx==ST.elem[mid].key) return mid; else if(kx>ST.elem[mid].key) low=mid+1； else high=mid-1； } return 0;

9.2 静态查找表 （基于线性表的查找） 【性能分析】 9.2.3有序表的折半查找 折半查找过程可用一棵判定树来描述。判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。

9.2 静态查找表 （基于线性表的查找） 【性能分析】 9.2.3有序表的折半查找 例： 对于下面有序表进行折半查找的判定树如下：（05,13,19,21,37,56,64,75,80,88,92） 6 3 9 1 4 7 10 8 11 2 5

9.2 静态查找表 （基于线性表的查找） n ∑ i=1 h ∑ i=1 １ ─ ｎ n+1 =─ log2(n+1)-1 n ASL= 9.2.3有序表的折半查找 【性能分析】 查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。对于n个结点的判定树，树高为k，则有k<=┗ log2n┛+1。因此，折半查找在查找成功时，所进行的关键码比较次数至多为┗ log2n┛+1 。 查找失败时和给定值进行比较的关键字的个数也超不过┗ log2n┛+1 。 折半查找成功时的平均查找长度为： n ∑ i=1 h ∑ i=1 １ ─ ｎ n+1 =─ log2(n+1)-1 n ASL= Pi·Ci = j·2j-1

9.2 静态查找表 （基于线性表的查找） 【性能分析】 9.2.3有序表的折半查找 折半查找的时间复杂度为O(logn) 优点：比较次数少，查找速度快，平均性能好。 缺点：要求待查的表为有序顺序表，插入、删除不方便。

9.2 静态查找表 （基于线性表的查找） 索引顺序表的组织： 9.2.4索引顺序表的查找（分块查找） 首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。 构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。

9.2 静态查找表 （基于线性表的查找） 例：下图为一个索引顺序表 9.2.4索引顺序表的查找（分块查找） 索引表 各块内的最大关键字 25 58 88 88 71 60 58 36 45 32 28 8 25 12 14 18 索引表 各块内的最大关键字 各块的起始地址 列表 0 1 2 3 4 5 6 7 8 9 10 11 12

9.2 静态查找表 （基于线性表的查找） 分块查找的基本过程为： 9.2.4索引顺序表的查找（分块查找） 1）首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。 （2）进一步用顺序查找法，在相应块内查找关键字为K的元素。

9.2 静态查找表 （基于线性表的查找） 9.2.4索引顺序表的查找（分块查找） 分块查找的平均查找长度由两部分组成：即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度LW。 ASLbs=LB+LW 假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有：

9.2 静态查找表 （基于线性表的查找） 若用顺序查找法确定待查元素所在的块，则有： = (n/s + s)/2 +1 9.2.4索引顺序表的查找（分块查找） 若用顺序查找法确定待查元素所在的块，则有： ASLbs = Lb + Lw = (b+1)/2 + (s+1)/2 = (n/s + s)/2 +1 当s= 时， ASLbs 取最小值 +1。 √n ─ √n ─ 若用顺序查找法确定待查元素所在的块，则有： ASLbs = Lb + Lw = log2(b+1)/2-1+ (s+1)/2 ≈ log2(n/s+1)+ s/2

9.3 动态查找表 9.3.1二叉排序树 1.二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： 　（1） 若左子树不空，则左子树上所有结点的值均小于根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于根结点的值。 （3）左右子树也都是二叉排序树。 二叉排序树又称为二叉查找树。

9.3 动态查找表 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树和B+树

9.3 动态查找表 9.3.1二叉排序树 1.二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： 　（1） 若左子树不空，则左子树上所有结点的值均小于根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于根结点的值。 （3）左右子树也都是二叉排序树。 二叉排序树又称为二叉查找树。

9.3 动态查找表 二叉排序树示例2 45 12 3 37 24 53 100 61 90 78 二叉排序树示例1 9.3.1二叉排序树 1.二叉排序树定义 由定义可知，对二叉排序树进行中序遍历，可得到一个按关键码递增有序的序列。 例： CAO ZHAO DING CHEN WANG 二叉排序树示例2 45 12 3 37 24 53 100 61 90 78 二叉排序树示例1

9.3 动态查找表 9.3.1二叉排序树 1.二叉排序树定义 例：下面的树不是二叉排序树 50 30 80 20 90 10 85 40 35 25 23 88 66

9.3 动态查找表 9.3.1二叉排序树 2.二叉排序树上的查找 从其定义可见，二叉排序树的查找过程为： ① 若查找树为空，查找失败。 　① 若查找树为空，查找失败。 　② 查找树非空，将给定值kx与查找树的根结点关键码比较。 　③ 若相等，查找成功，结束查找过程，否则， a．当kx小于根结点关键码，查找将在左子树上继续进行，转① b．当kx大于根结点关键码，查找将在右树上继续进行，转①

9.3 动态查找表 9.3.1二叉排序树 2.二叉排序树上的查找 例：在下面的二叉排序树中查找关键字等于100、40的记录。 45 12 3 37 24 53 100 61 90 78

9.3 动态查找表 9.3.1二叉排序树 2.二叉排序树上的查找 二叉排序树（查找表）的类型定义： typedef int KeyType;//设关键字的类型可直接进行比较 typedef struct  node { KeyType  key ; /*关键字的值*/ …… /*其它字段的值*/   struct node  *lchild,*rchild;/*左右指针*/ }BitNode,*BiTree;

9.3 动态查找表 9.3.1二叉排序树 2.二叉排序树上的查找 递归算法： BiTree SearchBST(BiTree T, KeyType key) { if (!T)||(T->key==key) return T;/*查找成功*/ else if (key < T-> key) return SearchBST(T->lchild, key); else return SearchBST(T->rchild, key); }

9.3 动态查找表 9.3.1二叉排序树 2.二叉排序树上的查找 非递归算法： BiTree SearchBST(BiTree T, KeyType key) { p=T; while(P) { if (p->key==key) return p;/*查找成功*/ else if (key<p->key) p=p->lchild; else p=p->rchild; } return NULL;/*查找失败*/ }/*SearchBST*/

9.3 动态查找表 9.3.1二叉排序树 3.二叉排序树的插入和生成 二叉排序树中插入一个结点： 设待插入结点的关键码为kx，先在二叉排序树中进行查找，若查找成功，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。 构造一棵二叉排序树则是逐个插入结点的过程。

9.3 动态查找表 58 42 98 70 90 63 45 55 83 67 10 9.3.1二叉排序树 3.二叉排序树的插入和生成 例：记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造的一棵二叉排序树为： 58 42 98 70 90 63 45 55 83 67 10

9.3 动态查找表 9.3.1二叉排序树 3.二叉排序树的插入和生成 二叉排序树中插入结点的算法：

二叉排序树中插入结点的递归算法： void InsertBST(BiTree &T, KeyType key) { if (T==NULL) { s=(BiTree)malloc(sizeof(BitNode)); s->key=key;s->lchild=NULL;s->rchild=NULL; T=s; } else if(key<T->key) InsertBST(T->lchild,key); else if (key>T->key) InsertBST(T->rchild,key);

二叉排序树中插入结点的非递归算法： void InsertBST(BiTree &T, KeyType key) { p=NULL;q=T; while(q!=NULL){ if (kx==q->key) return; else if (kx<q->key) {p=q;q=q->lchild;} else {p=q;q=q->rchild;} } s=(BiTree)malloc(sizeof(BitNode)); s->key=key;s->lchild=NULL;s->rchild=NULL; if (p==NULL) T=s; else if (key<p->key) p->lchild=key; else p->rchild=key;

9.3 动态查找表 9.3.1二叉排序树 3.二叉排序树的插入和生成 创建二叉排序树的算法： void CreateBST(BiTree &T) { T=NULL; scanf("%d", &key); while (key!=ENDKEY) /*ENDKEY为自定义常数*/ { InsertBST(bst, key); }

9.3 动态查找表 下面分三种情况讨论： 9.3.1二叉排序树 4.二叉排序树的删除 从二叉排序树中删除一个结点，必须保证删除后所得的二叉树仍然满足二叉排序树的性质不变。 删除操作： 首先确定被删除的结点是否在二叉排序树中。若不在 ，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似）。 下面分三种情况讨论：

f->lchild=NULL；free(p)； （2）若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树。即：f->lchild=p->lchild（或f->lchild=p->rchild）；free(p)； （3）若p既有左子树，又有右子树， 如下图(a)，则处理的方法有两种： F P PL PR f p (a) P的左右子树均不空

方法一：首先找到p结点在中序序列中的直接前驱s结点，如图 (b) 所示，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：f->lchild=p->lchild；s->rchild= p->rchild；free(p)；结果如图 (c) 所示。 F P C PR f p c S Q QL SL q s CL (b) S为P的直接前驱 CL F C S SL PR f c (c) 将P的左子树改为F的左子树，将P的右子树改为S的右子树。

方法二：首先找到p结点在中序序列中的直接前驱s结点，如图 (b) 所示，然后用s结点的值，替代p结点的值，再将s结点删除。即：原s结点的左子树改为s的双亲结点q的右子树：p->data=s->data；q->rchild= s->lchild；free(s)；结果如图 (d) 所示。 F P C PR f p c S Q QL SL q s CL (b) S为P的直接前驱 (d) 将原P结点的值改为S结点的值，删除原S结点并将原S的左子树改为Q的右子树 F S C PR f p c Q QL SL q CL

9.3 动态查找表 9.3.1二叉排序树 4.二叉排序树的删除 例：从下图（a）的二叉排序树中依次删除11、13、插入13、删除5、删除9，画出每步操作后的二叉排序树。 9 5 13 3 7 1 2 11 15 18

9.3 动态查找表 二叉排序树的各分支越均衡，树的深度浅，其平均查找长度ASL越小。 9.3.1二叉排序树 5.二叉排序树的查找分析 在二叉排序树上的查找和折半查找类似，恰是走了一条从根到该结点的路径，和给定值比较的关键字个数不超过树的深度。 含有n个结点的二叉排序树的平均查找长度和树的形态有关，而树的形态和初始序列有关。 二叉排序树的各分支越均衡，树的深度浅，其平均查找长度ASL越小。

9.3 动态查找表 9.3.1二叉排序树 5.二叉排序树的查找分析 例： 12 24 37 45 53 93 (b)输入关键字序列为{12,24,37,45,53,93}时的二叉排序树 45 24 12 37 53 93 (a) 输入关键字序列为{45,24,53,12,37,93}时的二叉排序树 假设每个元素的查找概率相等，则它们的平均查找长度分别是：ASL=(1+2+2+3+3+3)/6=14/6 ASL=(1+2+3+4+5+6)/6=21/6

9.3 动态查找表 9.3.1二叉排序树 5.二叉排序树的查找分析 因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。

9.3 动态查找表 9.3.2平衡二叉树 1.问题的提出 为使二叉排序树的检索效率最高，就要使二叉排序树在插入和删除后仍能维持好的形态。 45 24 12 37 53 93 (a) 输入关键字序列为{45,24,53,12,37,93}时的二叉排序树 12 24 37 45 53 93 (b)输入关键字序列为{12,24,37,45,53,93}时的二叉排序树

9.3 动态查找表 9.3.2平衡二叉树（AVL树） 2.平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树： （1）左子树与右子树高度之差的绝对值小于等于1； （2）左子树和右子树也是平衡二叉排序树。 平衡因子BF(Balance Factor) ：结点的左子树深度与右子树深度之差。

9.3 动态查找表 9.3.2平衡二叉树（AVL树） 2.平衡二叉树的概念 例： 40 25 50 30 58 60 -1 -2 1 20 20 40 25 60 30 50 70 80 -1 (b)一棵失去平衡的二叉排序树 (a)一棵平衡二叉排序树

9.3 动态查找表 9.3.2平衡二叉树（AVL树） 3.非平衡二叉树的平衡处理 处理的原则: 对失去平衡的最小子树（最小不平衡子树）进行平衡化处理，使其变为平衡。 设与插入结点最近、且平衡因子的绝对值超过1的祖先结点为A，则以A为根结点的子树称为最小不平衡子树。

9.3 动态查找表 1 27 -2 Ａ 10 1 51 -1 18 41 插入结点 最小 不平衡子树 25 9.3.2平衡二叉树（AVL树） 3.非平衡二叉树的平衡处理 例： 1 27 -2 Ａ 10 1 51 -1 18 41 插入结点 最小 不平衡子树 25

处理的方法： 分四种情况处理： （1）LL型 的处理(左左型) 条件：A的左孩子的左子树上插入结点后，导致失衡。 调整方法：（单右旋）。即以B为轴，对A做一次顺时针旋转。A成为B的右子树，而原来B的右子树则变成A的左子树。

（1）LL型 的处理(左左型) 例： 25 20 40 15 30 1 B A 60 ©调整后的二叉排序树 40 25 60 20 30 1 A B (a)平衡二叉排序树 40 25 60 20 30 2 1 A B 15 (b)插入15后失去平衡

（2）RR型的处理 条件：A的右孩子的右子树上插入结点后，导致失衡。 调整方法：（单左旋）。即以B为轴，对A做一次逆时针旋转。A成为B的左子树，而原来B的左子树则变成A的右子树。

（3）LR型的处理 条件：A的左孩子的右子树上插入结点后，导致失衡。 调整方法：（先左旋后右旋）。即先以C为轴，对B做一次左旋，然后以C为轴，对A做一次右旋。

（3）LR型的处理 例： (a)一棵平衡二叉排序树 (c)调整后的二叉排序树 (b)插入45后失去平衡 1 80 10 90 40 20 30 60 50 70 85 95 A C B (a)一棵平衡二叉排序树 （3）LR型的处理 例： 80 10 90 40 20 30 60 50 70 85 95 A 1 C -1 B 45 2 (b)插入45后失去平衡 60 10 80 40 20 30 50 45 70 90 C -1 1 B A 85 95 (c)调整后的二叉排序树

（4）RL型的处理 条件：A的右孩子的左子树上插入结点后，导致失衡。 调整方法：（先右旋后左旋）。即先以C为轴，对B做一次右旋，然后以C为轴，对A做一次左旋。

9.3 动态查找表 9.3.2平衡二叉树（AVL树） 实例： 例1：给定关键字序列（13,24,37,90,53），构造AVL树。 例2：给定关键字序列（5,3,4,7,6,8,2,1），构造AVL树。 为什么当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小平衡子树进行平衡化处理即可？ 由于平衡化处理后，以B或C为的新子树为平衡二叉树，且它的深度与插入之前以A为根的子树相同，因而不影响插入路径上的所有祖先结点的平衡度。

9.3 动态查找表 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。 9.3.2平衡二叉树（AVL树） 4.平衡二叉树查找的分析。 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。 时间复杂度为O(logn)。

9.3 动态查找表 9.3.3 B-树和B+树 1. 问题的提出 二叉排序树 平衡二叉树 多路平衡查找树 最好：O(log2n) 12 24 37 45 53 93 最好：O(log2n) 最坏：O(n) h 平衡二叉树 45 24 12 37 53 93 最坏： O(log2n) h 多路平衡查找树 37 12 24 37 45 53 93 最坏： O(logxn) h

9.3 动态查找表 9.3.3 B-树和B+树 2. B-树的定义。 B-树(B树)是一种平衡的多路查找树。 一棵m阶的B-树，或是空树，或是满足以下条件的m叉树： （1）树中每个结点至多有m棵子树； （2）若根结点不是叶子结点，则至少有二棵子树； （3）除根结点外的所有非终端结点至少有┌m/2┐棵子树； （4）所有结点包含信息（n,A0,K1,A1,…Kn,An)其中Ki为关键字且有序，Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+1,An所指子树中所有结点的关键字均大于Kn； （5）所有叶子结点都出现在同一层次上，并且不带信息（为空）。

n A0 K1 A1 … Kn An 图9.14 一棵4阶的B-树 n+1个分支 1 35 1 18 1 39 1 99 2 43 78 1 11 1 27 1 39 3 47 53 64 1 99 图9.14 一棵4阶的B-树

9.3 动态查找表 9.3.3 B-树和B+树 3. B-树的查找及分析。 例：在图9.14中查找47和23的过程。

9.3 动态查找表 9.3.3 B-树和B+树 3. B-树的查找及分析。 性能分析: 在B-树是进行查找包含两种基本操作： （2）在结点中找关键字：在内存中进行。 因此在磁盘上进行查找的次数（即待查关键字所在结点在B-树是的层次数），是决定B-树查找效率的关键因素。 含n个关键字的m阶B-树的最大深度为logm/2((n+1)/2) + 1 最坏的情况： O (logm/2n)

9.3 动态查找表 4. B-树的插入。 深度为h的m阶B树，首先检索到第h层，确定插入结点位置。 9.3.3 B-树和B+树 4. B-树的插入。 深度为h的m阶B树，首先检索到第h层，确定插入结点位置。 （1）若被插入结点中关键码个数小于m-1，则插入。 （2）若被插入结点中关键码个数等于m-1，则引起 结点“分裂”。

9.3 动态查找表 9.3.3 B-树和B+树 4. B-树的插入。 ... ... P m A0 K1 A1 ... Km Am ... ... P 9.3.3 B-树和B+树 4. B-树的插入。 结点“分裂”： m A0 K1 A1 ... Km Am 分裂前 ... Ｋ m/2 ... P P m/2 -1 A0 K1 A1 ... K m/2 -1 A m/2 -1 m-m/2 A m/2 Km/2+1 Am/2+1 ... K m A m 分裂后

9.3 动态查找表 9.3.3 B-树和B+树 4. B-树的插入。 例：在下面的3阶B-树中依次插入30、26、85和7。 45 24 3 12 37 50 53 90 61 70 100

9.3 动态查找表 1）在最下层结点中删除一个关键字 9.3.3 B-树和B+树 5. B-树的删除。 当结点中的关键字数大于m/2 -1 时，可直接删除(关键字Ki和Ai)。 当结点中关键字数等于m/2-1时，如果其右（左）兄弟中关键字数目大于m/2  -1 ，则需将其兄弟结点中的最小（或最大）关键字上移至双亲结点中，而将其双亲结点中大于（或小于）且紧靠该上移关键字的关键字下移至被删关键字所在的结点中。 当最下层待删结点及其左右兄弟中的关键字数目均为最低要求数目m/2  -1时，需要进行合并处理。

9.3 动态查找表 9.3.3 B-树和B+树 5. B-树的删除。 例：在下面的3阶B树中依次删除12、50、53和37。 45 24 3 12 37 50 53 90 61 70 100

9.3 动态查找表 2）在非最下层结点中删除一个关键字 9.3.3 B-树和B+树 5. B-树的删除。 一般情况下，删除非最下层结点中的关键字，可转化为删除最下层结点中的关键字。

9.3 动态查找表 9.3.3 B-树和B+树 6. B+树 B+树是B树的变形。 一棵m阶的B+树，或为空树，或是满足下列条件的m叉树： （3）若根结点不是叶子结点，则至少有两棵子树； （4） 有n棵子树的结点有n个关键码；

9.3 动态查找表 9.3.3 B-树和B+树 6. B+树 例：一棵3阶的B+树 59 97 15 44 59 72 97 10 15 21 37 44 51 59 63 72 85 91 97

9.3 动态查找表 9.3.3 B-树和B+树 6. B+树 一棵m阶的B+树和B树的差异： （A）有n棵子树的结点中含有n个关键码； （C）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中最大（或最小）关键码。

9.4 哈希表 9.4.1 什么是哈希表 1 问题的提出： 前面讨论的查找表的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程基于给定值和关键字集合中各个关键字的比较，查找的效率取决于和给定值进行比较的关键字个数。 理想情况：不经过任何比较，一次存取便能得到所查记录。为此就必须在记录的存储位置和其关键字之间建立一个确定的对应关系f。

9.4 哈希表 9.4.1什么是哈希表 2 哈希法的基本思想： 首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。 创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

9.4 哈希表 9.4.1什么是哈希表 例： 对于如下7个关键字{Zhao, Qian, Sun, Li, Wu, Chen, Han} ，设 哈希函数 f(key) = (Ord(第一个字母) -Ord(‘A’)+1)/2；得哈希表： 0 1 2 3 4 5 6 7 8 9 10 11 12 13   Chen Han Li Qian Sun Wu Zhao

9.4 哈希表 9.4.1什么是哈希表 3 基本概念 哈希函数（散列函数）： 使每个关键码都和结构中存储位置对应，这样的一个对应关系称为散列（哈希hush）函数。 冲突（collision）： 设哈希函数是h(key)，若key1key2 ,而 h(key1)=h(key2)。 key1和key2称为同义词(synonym)。 哈希表 根据设定的哈希函数 H(key) 和处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为哈希表，这一映像过程称为哈希造表或散列，所得的存储位置称哈希地址或散列地址。

9.4 哈希表 9.4.2 哈希函数的构造方法 一个好的哈希函数的原则： ①函数本身便于计算 ； ②计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。 常用的散列函数有： 1 直接定址法 2 数字分析法 3 平方取中法     4 折叠法 5 除余法 6 随机数法

9.4 哈希表 9.4.2 哈希函数的构造方法 1 直接定址法 取关键字的或关键字的某个线性函数值为哈希地址。即： H(key)＝key 或 H(key)＝a·key+b 其中a和b为常数。

9.4 哈希表 9.4.2 哈希函数的构造方法 2 数字分析法 假设关键码是以r为基的数，并且哈希表中可能现的关键码都是事先知道的，则可取关键码的分布较均匀的若干数位组成散列地址。 Key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 329

9.4 哈希表 当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。 9.4.2 哈希函数的构造方法 3 平方取中法 当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。 先求出关键码的平方，然后取中间几位作为地址。 例： key=4731 (4731)2 = 22382361 h(key)=382

9.4 哈希表 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希函数地址，称为折叠法。 9.4.2 哈希函数的构造方法 4 折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希函数地址，称为折叠法。 例：国际标准图书编号：0-442-20586-4 以其为关键字建立哈希表。 5864 5864 4220 0224 04 04 + + 10088 6092 H(key)=0088 H(key)=6092 移位叠加 间界叠加

9.4 哈希表 设定哈希函数为: 9.4.2 哈希函数的构造方法 5 除余法 H(key) = key MOD p 5 除余法 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且p 应为不大于 m 的素数以减少冲突的发生。 例如：给定一组关键字为: 12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为:3, 3, 0, 6, 6, 3。可见，因 p 可被 3整除, 所以所有含3的倍数的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。

9.4 哈希表 9.4.2 哈希函数的构造方法 6 随机数法 设定哈希函数为: H(key) = Random(key) 6 随机数法 设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。

9.4 哈希表 9.4.2 哈希函数的构造方法 在实际应用中需视不同的情况采用不同的哈希函数。通常，应考虑的因素有： 计算哈希函数所需时间 （简单） 关键字的长度 哈希表大小 关键字分布情况 记录查找频率

9.4 哈希表 9.4.3 处理冲突的方法 “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。 哈希函数h(key)的值域所对应的地址空间称为基本区域。发生碰撞时，同义词可以存放在基本区域中未被占用的单元，也可以存放到另开的区域中。

9.4 哈希表 9.4.3 处理冲突的方法 1. 开放定址法 在基本区域内形成一个探查序列 Hi = (H(key) + di)MOD m, i = 1, 2, …, k ( k m-1) 其中：m为表长，di为增量序列，可有多种取法： (1) di = 1, 2, 3, …, m-1, 称线性探测再散列; (2) di = 12,-12,22,-22,32, …, ±k2, 称二次探测再散列; (3) di =伪随机数序列,称伪随机探测再散列。

9.4 哈希表 0 1 2 3 4 5 6 7 8 9 10 9.4.3 处理冲突的方法 (a) (b) (c) (d) 60 17 29 1.开放定址法 例：哈希表的表长为11,H(key)=key mod 11,已填关键字为17、60、29的记录。现有记录，其关键字为38。 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (a) 60 17 29 38 (b) 38 60 17 29 (c) 38 60 17 29 (d) (a)插入前； (b)线性探测再散列；(c) 二次探测再散列；(d)伪随机探测再散列，伪随机数列9

9.4 哈希表 9.4.3 处理冲突的方法 2.链地址法(拉链法) 基本思想： 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。 例：对给定的关键字序列（19,14,23,1,68,20,84,27,55,11,10,79）， 给定哈希函数为H(key)=key%13，试用拉链法解决冲突建立哈希表。

9.4 哈希表 1 2 3 4 5 6 7 8 9 10 11 12 ^ 14 27 79 68 55 19 84 20 23 图 9.26 拉链法解决冲突的散列表 9.4.3 处理冲突的方法 2.链地址法(拉链法) 例： 对给定的关键字序列（19,14,23,1,68,20,84,27,55,11,10,79）， 给定哈希函数为H(key)=key%13，试用拉链法解决冲突建立哈希表。

9.4 哈希表 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。 9.4.3 处理冲突的方法 3.再哈希法 这种方法是同时构造多个不同的哈希函数： Hi = RHi（key） , i=1，2，…，k 在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。 RHi（key）均是不同的哈希函数 4. 建立一个公共溢出区 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

9.4 哈希表 9.4.4 哈希表的查找及分析 1 查找的过程 和构造散列表的过程基本一致。给定key值，根据散列函数求得散列地址，若表中没有记录，则查找不成功；否则比较关键码，若和给定值相等，则查找成功；否则根据造表时设定的冲突处理方法找“下一地址”，直到散列表某个位置为空或表中所填记录的关键码等于给定值时为止。

9.4 哈希表 9.4.4 哈希表的查找及分析 2 查找算法 以开放定址法处理冲突的方法为例，说明哈希表的查找过程。 #define m 100 //<哈希表长度> #define NULLKEY 0 //<代表空记录的关键字值> typedef int KeyType; typedef struct { KeyType key; … } ElemType ;

typedef ElemType HashTable[m] ; int HashSearch(HashTable ht, KeyType K){ p0=hash(K); if (ht[p0].key==NULLKEY) return (-1); else if (ht[p0].key==K) return (p0); else { /* 用线性探测再散列解决冲突 */ for (i=1; i<=m-1; i++) { pi=(p0+i) % m; if (ht[pi ].key==NULLKEY) return (-1); else if (ht[pi].key==K) return (pi); } return (-1);

9.4 哈希表 α＝ 9.4.4 哈希表的查找及分析 哈希表中元素个数 哈希表的长度 3 性能分析： 哈希法中影响关键字比较次数的因素有三个： 哈希函数、 处理冲突的方法、哈希表的装填因子α 。 α可描述哈希表的装满程度。显然，α越小，发生冲突的可能性越小，而α越大，发生冲突的可能性也越大。 α＝ 哈希表中元素个数 哈希表的长度

9.4 哈希表 9.4.4 哈希表的查找及分析 以下给出几种不同处理冲突方法的平均查找长度： 平均查找长度 处理冲突的方法 线性探测法 二次探测法 与双哈希法 平均查找长度 查找成功时 查找不成功时 拉链法

9.4 哈希表 9.4.4 哈希表的查找及分析 4 实例： 例：对给定的关键字序列（19,14,23,1,68,20,84,27,55,11,10,79）， 给定哈希函数为H(k)=k%13，表长为13。 (1)用线性探测再散列法处理冲突，建哈希表，求ASL。 解： （1） ASL=(6*1+1*2+3*3+1*4+1*9)/12=30/12=2.5

9.5 小结 各种查找方法的比较 1. 静态查找表 2. 动态查找表 （1）顺序查找 简单，常用于未排序元素的检索，但检索效率不高； （2）折半查找： 仅用于已排序元素，检索效率较高；但当插入、删除运算时会引起大量数据的移动。 2. 动态查找表 （1）二叉排序树：元素插入次序不同，会构成不同的二叉排序树。平均检索长度最好为O(log2n) 。 （2）平衡二叉排序树：维持较高的检索效率，但平衡化过程较复杂。

9.5 小结 对于较大的必须存放在外存贮器上的字典，应采用B树或B+树。 （3）哈希表： 检索操作达到近乎随机存取的速度。但散列表示经常出现碰撞与堆积现象，增加了检索长度。 （4） B树或B+树： 对于较大的必须存放在外存贮器上的字典，应采用B树或B+树。 B+树是B树的变种。B树和B+树都能动态地调整，保持均衡，而保持较高的检索效率。