第九章 查找

主要内容 　 9.1 静态查找表 9.2 动态查找表 9.3 哈希表

查询 插入 删除 查找表 ？ 是由同一类型的数据元素(或记录)构成的集合。 操作: 某个数据元素或数据元素的某种属性 插入一个数据元素 删除某个数据元素 删除

查找表可分为两类: 1.静态查找表 仅作查询和检索操作的查找表。 2.动态查找表 将“查询”结果为“不在查找表中”的数据元素插入到查找表中； 从查找表中删除数据元素。

关键字 是数据元素中某个数据项的值，用以标识一个数据元素。 若此关键字可以唯一识别一个记录，则称之为“主关键字”。 若此关键字能识别若干记录，则称之谓“次关键字”。

查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成功”。 查找结果给出整个记录的信息 或指示该记录在查找表中的位置； 否则称“查找不成功” 查找结果给出“空记录”或“空指针”。

如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系。 换句话说， 用另外一种结构来表示查找表。

在本章以后各节的讨论中，涉及的关键字类型和数据元素类型统一说明如下： 典型的关键字类型说明可以是： typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char* KeyType; //字符串型 数据元素类型定义为： typedef struct{ KeyType key; //关键字域 … //其他域 }ElemType;

//--对数值型关键字的比较约定为如下的宏定义： #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)< (b)) #define LQ(a,b) ((a)<=(b)) … //--对字符串型关键字 #define EQ(a,b) (!strcmp((a)==(b))) #define LT(a,b) (!strcmp((a)==(b))<0) #define LQ(a,b) (!strcmp((a)==(b))<=0)

9.1 静 态 查 找 表 抽象数据类型静态查找表的定义为： ADT StaticSearchTable { 数据元素同属一个集合。 基本操作 P： Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit()); } ADT StaticSearchTable

Create(&ST, n); 操作结果： 构造一个含n个数据元素的静态查找表ST。 Destroy(&ST); 初始条件： 操作结果： 静态查找表ST存在； 销毁表ST。 Search(ST, key); 初始条件： 操作结果： 静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值； 若 ST 中存在其关键字等于key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

Traverse(ST, Visit()); 初始条件： 操作结果： 静态查找表ST存在，Visit是对元素操作的应用函数； 按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。

假设静态查找表的顺序存储结构为 typedef struct { // 数据元素存储空间基址，建表时 // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; ElemType *elem; 数据元素类型的定义为: typedef struct { keyType key; // 关键字域 … … // 其它属性域 } ElemType ;

k 9.1.1 顺序表的查找 以顺序表或线性链表表示静态查找表 ST.elem 假设给定值 e=64, 要求 ST.elem[k] = e, 问: k = ?

i ST.elem 64 key=64 i ST.elem 60 key=60

顺序查找算法 方法： 从最后1个元素开始依次往前找， 第0个元素存放要查找的关键字----哨兵 int Search_Seq(SSTable ST, KeyType key) { //在顺序表ST中顺序查找其关键字等于key的数据元素。 //若找到，则函数值为该元素在表中的位置，否则为0。 ST.elem[0].key=key; //“哨兵” for (i=St.length; !EQ(ST.elem[i].key, key); --i ); //从后往前找 return i; //找不到时，i为0 }//Search_Seq

平均查找长度 与给定值进行比较的关键字个数的平均值称为算法在查找成功时的平均比较长度ASL(Average Search Length) pi 是查找第i个元素的概率 ci 是查找第i个元素的比较次数

在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。

9.1.2 有序表的查找 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

例如: key=64 的查找过程如下： ST.length ST.elem low low high high mid mid mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2

算法 9.2 int Search_Bin ( SSTable ST, KeyType key ) { //若找到，则函数值为该元素在表中的位置，否则为0。 low = 1; high = ST.length; // 置区间初值 while (low <= high) mid = (low + high) / 2; if(EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 算法 9.2

分析折半查找的平均查找长度 先看一个具体的情况，假设：n=11 1 2 3 4 判定树 6 3 9 1 4 2 5 7 8 10 11

一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。 假设 n=2h-1 并且查找概率相等 则 在n>50时，可得近似结果

9.1.4 索引顺序表的查找 索引顺序表： 索引表 索引表 查找表 最大关键字 起始地址 查找表 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 1 7 索引表 最大关键字 起始地址 查找表

查找过程： 1）由索引确定记录所在区间； 2）在顺序表的某个区间内进行查找。 查找索引ASL 查找顺序表ASL 总ASL

9.2 动 态 查 找 表 ADT DynamicSearchTable { D是具有相同特性的数据元素的集合。 数据对象D： 9.2 动 态 查 找 表 ADT DynamicSearchTable { D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字， 可唯一标识数据元素。 数据对象D： 数据关系R： 数据元素同属一个集合。 基本操作P： InitDSTable(&DT) DestroyDSTable(&DT) SearchDSTable(DT, key); InsertDSTable(&DT, e); DeleteDSTable(&T, key); TraverseDSTable(DT, Visit()); }ADT DynamicSearchTable

InitDSTable(&DT); 操作结果： 构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件： 操作结果： 动态查找表DT存在； 销毁动态查找表DT。 SearchDSTable(DT, key); 初始条件： 操作结果： 动态查找表DT存在，key为和关键字类型相同的给定值； 若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

InsertDSTable(&DT, e); 初始条件： 操作结果： 动态查找表DT存在，e 为待插入的数据元素； 若DT中不存在其关键字等于 e.key 的 数据元素，则插入 e 到DT。 DeleteDSTable(&T, key); 初始条件： 操作结果： 动态查找表DT存在，key为和关键字类型相同的给定值； 若DT中存在其关键字等于key的数据元素，则删除之。

TraverseDSTable(DT, Visit()); 初始条件： 操作结果： 动态查找表DT存在，Visit是对结点操作的应用函数； 按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。

9.2.1 二叉排序树和平衡二叉树 一 、二叉排序树 1．定义： 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树： （1）若它的左子树不空，则左子树所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树所有结点的值均大于根结点的值； （3）它的左、右子树也都分别是二叉排序树。

例如: 50 30 80 20 40 90 10 25 35 85 66 23 不是二叉排序树。 88

通常，取二叉链表作为二叉排序树的存储结构。 typedef struct BiTNode { struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; TElemType data;

2．二叉排序树的查找算法： 若二叉排序树为空，则查找不成功； 否则， 1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。

例如: 二叉排序树 50 50 50 50 50 50 30 30 80 80 20 40 40 90 90 查找失败 35 35 85 32 88 查找关键字 == 50 , 35 , 90 , 95 ,

在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找不成功

算法描述如下： 算法 9.5 Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) { // 在根指针 T 所指二叉排序树中递归地查找其关键字等于 key 的数据元素， // 若查找成功，则返回指针 p 指向该数据元素的结点，函数值为 TRUE; //否则表明查找不成功，返回指针 p 指向查找路径上访问的最后一个结点， //返回函数值为FALSE; //指针 f 指向当前访问的结点的双亲，其初始调用值为NULL } // SearchBST … … … … 算法 9.5

if (!T) { p = f; return FALSE; } // 查找不成功 else if ( EQ(key, T->data.key) ) { p = T; return TRUE; } // 查找成功 else if ( LT(key, T->data.key) ) SearchBST (T->lchild, key, T, p ); // 在左子树中继续查找 else SearchBST (T->rchild, key, T, p ); // 在右子树中继续查找

22 设 key = 48 f f T f T f f T f T p 30 T 20 40 T f 10 25 35 p T f 23 T

3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 若二叉排序树为空树，则新插入的结点为新的根结点； 否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

Status InsertBST(BiTree &T, ElemType e ) { // 当二叉排序树中不存在关键字等于 e.key 的 // 数据元素时，插入元素值为 e 的结点，并返回 TRUE; // 否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p )) { } else return FALSE; } // Insert BST … … 算法 9.6

s = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s->data = e; s->lchild = s->rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点 else if ( LT(e.key, p->data.key) ) p->lchild = s; // 插入 s 为 p 的左孩子 else p->rchild = s; // 插入 s 为 p 的右孩子 return TRUE; // 插入成功

4．二叉排序树的删除算法 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 可分三种情况讨论： （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。

50 30 80 20 40 90 35 85 32 88 （1）被删除的结点是叶子结点 例如: 被删关键字 = 20 88 其双亲结点中相应指针域的值改为“空”

50 30 80 20 40 90 35 85 32 88 （2）被删除的结点只有左子树或者只有右子树 被删关键字 = 40 80 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。

40 50 30 80 20 40 40 90 35 85 32 88 （3）被删除的结点既有左子树，也有右子树 被删关键字 = 50 前驱结点 被删结点 以其前驱替代之，然后再删除该前驱结点

… … 算法描述如下： 算法 9.7 Status DeleteBST (BiTree &T, KeyType key ) { // 数据元素，则删除该数据元素结点，并返回 // 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; // 不存在关键字等于key的数据元素 else { } } // DeleteBST … … 算法 9.7

if ( EQ (key, T->data.key) ) else if ( LT (key, T->data.key) ) else { Delete (T); return TRUE; } DeleteBST ( T->lchild, key ); // 继续在左子树中进行查找 DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找

… … … … … … 其中删除操作过程如下所描述： void Delete ( BiTree &p ){ // 并重接它的左子树或右子树 if (!p->rchild) { } else if (!p->lchild) { } else { } } // Delete … … … … … … 算法 9.8

void Delete(BiTree &p) { //从二叉树中删除结点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=p表示p的左子树上无右子树 q->rchild=s->lchild; //重接*q的右子树 q->lchild=s->lchild; //重接*q的左子树 free(s); }//Delete 50 30 80 20 90 85 40 35 88 32

二、平衡二叉树（AVL树） - h 是一棵空树 或具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树 左子树和右子树的深度之差的绝对值不超过1。 结点的平衡因子= - R L h 右子树高度 左子树高度

5 5 4 8 4 8 2 2 1 平衡二叉树的特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1。即 。 树中每个结点的左、右子树深度之差的绝对值不大于1。即 。 平衡因子只能是-1、0、1 例如: 5 5 4 8 4 8 2 2 是平衡二叉树 不是平衡二叉树 1

构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离新插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况：LL型、LR型、RR型、RL型。

13 24 7 24 13 7 单向右旋平衡处理 53 20 13 24 7 53 20 13 24 7 5 5

lc 单向右旋平衡处理 由于*p的左子树的左子树上插入结点 使*p的平衡因子由1增至2 lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; p lc p

13 7 13 24 7 24 单向左旋平衡处理 13 24 53 7 5 90 13 24 53 7 5 90

rc 单向左旋平衡处理 由于*p的右子树的右子树上插入结点 使*p的平衡因子由-1增至-2 rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; p p rc

双向先右后左旋转平衡处理 7 10 13 7 10 13 7 13 10 53 20 13 24 7 5 13 24 53 7 5 13 20 24 53 7 5 20

p rc rc ld p ld ld p rc 双向先右后左旋转平衡处理 由于*p的右子树的左子树上插入结点 使*p的平衡因子由-1增至-2 if(ld->bf= =1) { p->bf=0; rc->bf=-1; ld->bf=0;}

rc rc rc p p ld ld ld p if(ld->bf= =-1) {p->bf=1; rc->bf=0; } rc p

rc rc p ld p ld rc=p->rchild; ld=rc->lchild; switch(ld->bf) {case 1: p->bf=0; rc->bf=-1; ld->bf=0; break; case -1: p->bf=1; rc->bf=0 ; ld->bf=0; break; } R_Rotate(p->rchild); L_Rotate(p); p ld rc rc p ld

双向先左后右旋转平衡处理 28 17 12 28 17 28 12 12 17 13 64 23 35 19 64 13 28 35 23 19 64 28 23 35 19 13 28

p p rd lc lc rd rd p lc if(rd->bf= =1) { p->bf=-1; lc->bf=0; } lc p

p p lc rd lc rd rd p lc if(rd->bf= =-1) { p->bf=0; lc->bf=1; } p lc

双向先左后右旋转平衡处理 由于*p的左子树的右子树上插入结点 使*p的平衡因子由1增至2 lc=p->lchild; rd=lc->rchild; swirch(rd->bf) {case 1: p->bf=-1; lc->bf=0; rd->bf=0; break; case -1: p->bf=0; lc->bf=1; rd->bf=0; break; } L_Rotate(p->lchild); R_Rotate(p);

平衡二叉排序树的类型定义为： typedef struct BSTNode { ElemType data; int bf; //结点的平衡因子 struct BSTNode * lchild, * rchild; //左、右孩子指针 } BSTNode, *BSTree;

b.若e的关键字小于*T的关键字，插入左子树lc 若T->bf== -1 //*T为根结点，*lc为根的左孩子，*rc为根的右孩子 a.若T为空树 插入e为T的根结点，树的深度增加1 b.若e的关键字小于*T的关键字，插入左子树lc 若T->bf== -1 if插入后lc深度增加，树T的深度不变, T->bf=0 若T->bf==0 if插入后lc深度增加，树T的深度增加1, T->bf=1 若T->bf==1 if插入后lc深度增加，树T的深度不变, if( lc->bf= =1) 对T单右旋平衡处理, if(lc->bf= =-1) 对T双向先左后右平衡处理

c.若e的关键字大于*T的关键字，插入右子树rc if(T->bf= =1) 树T的深度不变, T->bf=0 if(T->bf= =0) 树T的深度增加1,T->bf= -1 if(T->bf= =-1) 树T的深度不变 if(rc->bf= =-1) 对T单左旋平衡处理 if(lc->bf= =1) 对T双向先右后左平衡处理

void R_Rotate ( BSTree &p) { //对以 void R_Rotate ( BSTree &p) { //对以*p为根的二叉排序树作右旋处理，处理之后p指向新的根结点，即旋转处理之前的左子树的根结点 lc = p->lchild; //lc指向的*p的左子树根结点 p->lchild= lc->rchild; //lc的右子树挂接为*p的左子树 lc->rchild=p; p=lc; //p指向新的根结点 }// R_Rotate p lc 算法 9.9 p

void L_Rotate ( BSTree &p) { //对以 void L_Rotate ( BSTree &p) { //对以*p为根的二叉排序树作左旋处理，处理之后p指向新的根结点，即旋转处理之前的右子树的根结点 rc = p->rchild; //rc指向的*p的右子树根结点 p->rchild= rc->lchild; //rc的左子树挂接为*p的右子树 rc->lchild=p; p=rc; //p指向新的根结点 }// L_Rotate 算法 9.10 p p rc

算法 9.11 #define LH 1 //左高 #define EH 0 //等高 #define RH -1 //右高 Status InsertAVL (BSTree &T, ElemType e, Boolean &taller) { //1.若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0； //2.若因插入而使二叉排序树失去平衡，则作平衡旋转处理； //3.布尔变量taller反映T长高与否。 if (!T) {//插入新结点，树“长高”，置taller为TRUE T = (BSTree) malloc (sizeof (BSTNode)); T->data = e; T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE; }

else { if (EQ (e. key, T->data else { if (EQ (e.key, T->data.key)) //树中已存在和e有相同关键字的结点 taller = FALSE; return 0; } //则不再输入 if (LT (e.key, T->data.key)) { //应继续在*T的左子树中进行搜索 if (!InsertAVL (T->lchild, e, taller)) return 0; //未插入 if (taller) //已插入到*T的左子树中且左子树“长高” switch (T->bf) { //检查*T的平衡度 case LH; //原本左子树比右子树高，需要做左平衡处理 LeftBalance (T); taller = FALSE; break; case EH; //原本左、右子树等高，现因左子树增高而使树增高 T->bf = LH; taller = TRUE; break; case RH; //原本右子树比左子树高，现左、右子树等高 T->bf = EH; taller = FALSE; break; }//switch (T->bf) } //if

else { //应继续在. T的右子树中进行搜索 if ( else { //应继续在*T的右子树中进行搜索 if (!InsertAVL (T->rchild, e, taller)) return 0; //未插入 if (taller) //已插入到*T的右子树中且右子树“长高” switch (T->bf) { //检查*T的平衡度 case LH; //原本左子树比右子树高，现左、右子树等高 T->bf = EH; taller = FALSE; break; case EH; //原本左、右子树等高，现因右子树增高而使树增高 T->bf = RH; taller = TRUE; break; case RH; //原本右子树比左子树高，需要做右平衡处理 RightBalance (T); taller = FALSE; break; } //switch (T->bf) }//else return 1; }//InsertAVL

void LeftBalance ( BSTree &T ) { //对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针T指向新的根结点 lc = T->lchild; //lc指向*T的左子树根结点 switch (lc->bf) { //检查*T的左子树的平衡度，并作相应平衡处理 case LH： //新结点插入在*T的左孩子的左子树，要作单右旋处理 T->bf = lc->bf = EH; R_Rotate(T); break; case RH： //新结点插入在*T的左孩子的右子树，要作双旋处理 rd = lc->rchild; //rd指向*T的左孩子的右子树根 switch (rd->bf) { //修改*T及其左孩子的平衡因子 case LH: T->bf = RH; lc->bf = EH; break; case EH: T->bf = lc->bf = EH; break; case RH: T->bf = EH; lc->bf = LH; break; } // switch (rd->bf) rd->bf = EH; L_Rotate(T->lchild); //对*T的左子树作左旋平衡处理 R_Rotate(T); //对*T的作右旋平衡处理 }// switch (lc->bf) }// LeftBalance 算法 9.12

请对如下数据： 43，12，50，31，71，35，24，62，11，20 构造一棵平衡的二叉排序树，并计算ASL。 43 12 50 31 71 35

9.2.2 B-树和B+树 1．B-树的定义 B-树是一种平衡的多路查找树：

一棵 m 阶的B-树，或为空树，或为满足下列特性的m叉树： （1）所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树； （2）根结点或为叶子结点，或至少含有两棵子树； （3）所有非终端结点含有下列信息数据： （n，A0，K1，A1，K2，A2，…Kn，An）

Ai为指向子树根结点的指针，且指针Ai-1所指子树上所有关键字均小于Ki ； An 所指子树上所有关键字均大于Kn ； （n，A0，K1，A1，K2，A2，…Kn，An） 其中：Ki为关键字，且均自小至大有序排列，即：K1< K2 < … < Kn ； Ai为指向子树根结点的指针，且指针Ai-1所指子树上所有关键字均小于Ki ； An 所指子树上所有关键字均大于Kn ； （4）树中所有叶子结点均不带信息，且在树中的同一层次上；

B-树结构的描述如下: #define m 3 //B-树的阶，暂设为3 typedef struct BTNode { int keynum; // 结点中关键字个数，即结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; //关键字向量（0号单元不用） struct BTNode *ptr[m+1]; //子树指针向量 Record *recptr[m+1]; // 记录指针向量（0号单元不用） } BTNode, *BTree; // B树结点和B树的类型

2.查找过程： 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置； 若查找不成功，则返回插入位置。

假设返回的是如下所述结构的记录： typedef struct { BTNode *pt; // 指向找到的结点的指针 int i; // 1..m，在结点中的关键字序号 int tag; // 标志查找成功(=1)或失败(=0) } Result; // 在B树的查找结果类型

… … 算法 9.13 Result SearchBTree(BTree T, KeyType K) { //在m 阶的B-树 T 中查找关键字 K, 返回查找结果 (pt, i, tag)。 // tag=1,查找成功， 指针 pt 所指结点中第 i 个关键字等于 K // tag=0,查找失败，K 作为关键字标识的记录应插入在指针 pt 所指结点 // 中第 i 个关键字和第 i+1个关键字之间 { } // SearchBTree … … 算法 9.13

p=T; q=NULL; found=FALSE; i=0; //初始化，p指向待查接点，q指向p的双亲 while (p && !found) { i=Search(p, K); // 在p->key[1..keynum]中查找 ，i使得p->key[i]<=K<p->key[i+1] if (i>0 && p->key[i]==K) found=TRUE; //找到待查关键字 else { q=p; p=p->ptr[i]; } } if (found) return (p,i,1); // 查找成功 return (q,i,0); // 查找不成功，返回k的插入位置信息

3．插入 在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况： 1）插入后，该结点的关键字个数n<m，不修改指针;

2）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，令 s = m/2，在原结点中保留（A0，K1，…… ， Ks-1，As-1）；建新结点 （As，Ks+1，…… ，Kn，An）；将（Ks，p）插入双亲结点； 3）若双亲为空，则建新的根结点。

插入 插入30 先找到插入的位置(p,i)--总在最高层的非终端结点 45 24 3 12 37 50 100 61 70 53 90 3 12 37 50 100 61 70 53 90 插入30 30 37

45 24 30 37 3 12 50 100 61 70 53 90 插入26 26 30 37 45 3 12 50 100 61 70 53 90 24 30 26 37

45 70 45 3 12 50 100 61 70 24 30 26 37 53 90 插入85 61 70 85 53 70 90 61 70 85 53 70 90

3 12 24 30 26 37 100 50 85 45 70 53 90 61 24 45 70 插入7 3 7 12 3 7 12 7 24 30 7 24 30

3 7 12 70 24 30 45 26 37 100 50 85 53 90 61

若p中关键字个数<m-1，插入相应位置 分裂成: 而关键字km/2和指针p’一起插入到p的双亲中去 并且双亲也可能分裂，分裂可能一直进行到根结点， 使树的深度增加

Status InsertBTree (BTree &T, KeyType K, BTree q, int i ) { //在m阶B-树T上结点*q的key[i]和key[i+1]之间插入关键字K。若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B-树。 x = K; ap = NULL; finished = FALSE; while (q && !finished) { Insert (q, i, x, ap) ; //将x和ap分别插入到q->key[i+1]和q->ptr[i+1] if (q->keynum<m) finished = TRUE; //插入完成 算法 9.14

else { s= m/2; split (q, s, ap); x = q->key[s]; //将q->key[s+1 else { s= m/2; split (q, s, ap); x = q->key[s]; //将q->key[s+1..m], q->ptr[s..m]和q>recptr[s+1..m] //移入新结点*ap q = q->parent; if (q) i = Search (q, x); //在双亲结点*q中查找x的插入位置 }//else }//while if (!finished) //T是空树(参数q初值为NULL)或者 //根结点已分裂为结点*q和*ap NewRoot (T, q, x, ap); //生成含信息(T, x, ap)的新的根结点*T，原T和ap为子树指针 return OK; }// InsertBTree

4．删除 先找到关键字所在的结点（p，i） (1)p为最下层的非终端结点 A. 若p中关键字数目不小于 m/2  ，则从p中删去Ki，Ai B. 若p中关键字数目等于m/2  -1, 且与p相邻的右(左)兄弟结点中关键字个数大于m/2  -1 则将右(左)兄弟中最小(大)的关键字移到双亲结点中， 且将双亲结点中小(大)于又最接近上移关键字的 关键字下移到p中 C. 若和p相邻的兄弟中关键字数目都等于m/2  -1, 且结点p有 右兄弟，右兄弟由双亲结点的Ai指向 则删去关键字后，p中剩余关键字和指针与Ki一起合并到 Ai所指的右兄弟结点中，并从双亲结点中删去（Ai，Ki） 若该结点没有右兄弟则合并到左兄弟 合并可能一直进行到根

先找到关键字所在的结点（p，i） (2)p不是最下层的非终端结点 用Ai 所指的最小关键字Y代替Ki，在相应结点中删除Y 45 24 3 37 100 61 70 90 删去45 61 24 3 37 100 70 90

45 24 3 12 37 50 100 61 70 53 90 删去50 45 24 3 12 37 53 100 70 61 90

45 24 3 12 37 53 100 70 61 90 删去53 45 24 3 12 37 100 61 70 90

45 24 3 12 37 100 61 70 90 删去12 45 24 3 37 100 61 70 90

45 24 3 37 100 61 70 90 删去37 45 90 3 24 100 61 70

5. B+树 B-树的变型树 非终端结点：索引 叶子结点：所有关键字 查找： 从最小关键字开始顺序查找 从根结点开始随机查找

9．3哈希表 一、哈希表 根据设定的哈希函数和处理冲突的方法，将一组关键字映象到一个有限的连续的地址空间上，并将关键字的映象作为记录在表中存储位置的表。 H(key)=key MOD 12 84 01 14 27 23 11 10 55 68 19 20 79

二、哈希函数的构造方法 1．原则：均匀性 若关键字集中任一关键字，经哈希函数映象到地址集合中任一地址的概率是相等的，则此哈希函数为均匀的哈希函数。 H(key)=(key-1949) MOD 100 2．直接定址法 H（key）=a*key+b a、b为常数 H(key)= key -1949

3．数学分析法 设key为以r为基的数 H（key）取key中若干数位进行运算 H(key)= key/1000%100 4．平均取中法 取关键字平方后的中间几位 H(key)= key2/1000%100

5．折叠法 将关键字分割成位数相同的几部分（最前/后一部分的位数可以不同），然后取各部分的叠加和（去掉进位）. key=0-442-20586-4 5864 4220 +) 04 10088 5864 0224 +) 04 6092 H1(key)=0088 H2(key)=6092

H(key)= key MOD 10 6．除数留余法 关键字被某个不大于哈希表表长m的数p除后所得余数 H（key）=key MOD p 7．随机数法 选取哈希函数的因素： 计算哈希函数的时间 关键字的长度 哈希表的大小 关键字的分布情况 记录的查找频率

三、处理冲突的方法 设哈希表的地址集为0至n-1 冲突是指由关键字得到的哈希地址为j(0jn-1） 对不同的关键字得到同一个哈希地址的现象称为冲突。具有相同函数值的关键字成为该哈希函数的同义词。在一般情况下，冲突只能尽可能的少，不能完全避免 三、处理冲突的方法 设哈希表的地址集为0至n-1 冲突是指由关键字得到的哈希地址为j(0jn-1） 而j位置上已经有记录 处理冲突是指为该关键字记录找到另一个哈希地址。 处理冲突过程中可能得到一个地址序列： H1、H2、…………、Hk 直到第k次才得到一个不冲突的地址

1．开放定址法 Hi=(H(key)+di) MOD m i=1,2,….,k (km-1) H(key)为哈希函数，m为哈希表表长， di为增量序列 di的取值有三种： (1)线性探测再散列di=1,2,……,m-1， (2)二次探测再散列di=12，-12，22，-22，32，-32， …., k2 (km/2) (3)伪随机探测再散列di=伪随机数序列

2．链地址法 将所有关键字是同义词的记录存储在同一线性链表中，插入后可使同义词在同一线性链表中按关键字有序

3．再哈希法 在同义词产生冲突时用另一个哈希函数区分它们 Hi=RHi (key) i=1,2,3,….,k RHi为多个不同的哈希函数 4．建立一个公共溢出区 用HashTable[0..n-1]作为基本表，每个分量存放一个记录，用OverTable[0..v]作为溢出表。一旦发生冲突，按先后顺序填入溢出表，与H(key)无关。

int hashsize[]={977, …}; //哈希表容量递增表,一个合适的素数序列 typedef struct 四、哈希表的查找 与造哈希表基本相同 //------------开放定址哈希表的存储结构---------------- int hashsize[]={977, …}; //哈希表容量递增表,一个合适的素数序列 typedef struct {ElemType *elem; //数据元素存储基址，动态分配数组 int count; //当前数据元素个数 int sizeindex; //当前容量 }HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1

Status SearchHash(HashTable H, KeyType K, int &p, int &c) //并返回SUCCESS； //否则以p指示插入位置，并返回UNSUCCESS。 //c用以计冲突次数，其初值为0，供建表插入时参考 { p=Hash(K); //求得哈希地址 while (H.elem[p].key!=NULLKEY && !EQ(K, H.elem[p].key) //该位置中填有记录，并且关键字不等 collision(p, ++c); //求下一探查地址p if EQ(K, H.elem[p].key) return SUCCESS; //查找成功，p返回待查数据元素位置 else return UNSUCCESS; //查找不成功，p返回的是插入位置 }//SearchHash

插入算法 Status InsertHash(HashTable &H, ElemType e) //并返回OK；若冲突次数过大，则重建哈希表 c=0; if(SearchHash (H, e.key, p, c)) return DUPLICATE; //表中已有与e有相同关键字的元素 else if (c<hasize[H.sizeindex]/2) {//冲突次数c未达到上限（c的阀值可调） H.elem[p]=e; //插入e ++H.count; return OK; } else RecreateHashTable(H); }//InsertHash

ASL=(6*1+2*3+1*5+1*9+1*7+1*6)/12=39/12 key=(14,01,68,27,55,19,20,84,79,23,11,10) 采用除数留余法建立哈希表， 用线性探测再散列处理冲突 H(key)=key MOD 12 84 01 14 27 23 11 10 55 68 19 20 79 19 20 10 23 11 79 假设每个元素被查找的概率相同 ASL=(6*1+2*3+1*5+1*9+1*7+1*6)/12=39/12

key=（14,01,68,27,55,19） 问题：查找不成功时的平均查找长度？ H(key)=key MOD 12 01 14 27 23 19 55 68 1 + 5 + 4 + 3 + 2 + 1 + 1 + 4 + 3 + 2 + 1 + 1 =28 查找不成功时，ASL=28/12=7/3

将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为： H(key) = (key*3) MOD T，处理冲突采用线性探测再散列法，要求装载因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 装载因子=关键字个数/哈希表长度 哈希表长度=10 H(key)=(key*3) Mod 10 30 7 14 11 8 18 9 7 + 6 + 5 + 4 + 3 + 2 + 1 + 2 + 1 + 1 =32 等概率情况: 查找成功的ASL= (6*1+1*2)/7=8/7 查找不成功的ASL= 32/10=3.2

已知长度为11的表（xa,wa,wi,zo,yo,xu,yu,we,wm,zi,yr),按表中元素顺序依次插入一颗初始为空的平衡二叉树，画出插入完成以后的平衡二叉排序树，并求ASL。 RL xa wa wa LR wi wa xa wi yo wa zo wi zo wi yo wa yo xa RL wa xa xa zo wi yo yo wa xu zo xu xu zo

（xa,wa,wi,zo,yo,xu,yu,we,wm,zi,yr) LR LR wa xu zo we xu zo wa wi xu zo wm yu we yu wa yu zi xa xa we yo we yo RL wa wi xu zo wa wi xu zi wm zi wm yu zo yu yr

（xa,wa,wi,zo,yo,xu,yu,we,wm,zi,yr) RL wa wi xu yu wa wi xu zi wm yr zi wm yu zo zo yr xa we yu ASL=(1*1+2*2+3*4+4*4)/11=3 wa wi yo zi wm xu yr zo

已知一组关键字为{21，33，12，40，68，59，25，51}，试依次插入关键字生成一棵3阶B-树；如果此后删除40，画出每一步执行后B-树的状态。