《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第9章查找（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第9章查找（可编辑.ppt（119页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学数据结构PPT课件 第9章 查找9.1 查找的基本概念查找的基本概念 被被查查找找的的对对象象是是由由一一组组记记录录组组成成的的表表或或文文件件,而而每每个个记记录录则则由由若若干干个个数数据据项项组组成成,并并假假设设每每个个记记录录都都有有一个能一个能唯一标识该记录的关键字唯一标识该记录的关键字。在在这这种种条条件件下下,查查找找的的定定义义是是：给给定定一一个个值值k,k,在在含含有有n n个个记记录录的的表表中中找找出出关关键键字字等等于于k k的的记记录录。若若找找到到,则则查查找找成成功功,返返回回该该记记录录的的信信息息或或该该记记录录在在表表中中的
2、的位位置置；否否则则查查找找失失败败,返返回回相相关的指示信息。关的指示信息。采用何种查找方法采用何种查找方法?（1）使使用用哪哪种种数数据据结结构构来来表表示示“表表”，即即表表中记录是按何种方式组织的。中记录是按何种方式组织的。（2）表表中中关关键键字字的的次次序序。是是对对无无序序集集合合查查找还是对有序集合查找找还是对有序集合查找?若若在在查查找找的的同同时时对对表表做做修修改改运运算算（如如插插入入和和删删除除），则则相相应应的的表表称称之之为为动动态态查查找找表表；否否则称之为则称之为静态查找表静态查找表。数据组织方式数据组织方式数据是否有序数据是否有序查找算法查找算法 由由于于查
3、查找找运运算算的的主主要要运运算算是是关关键键字字的的比比较较,所所以以通通常常把把查查找找过过程程中中对对关关键键字字需需要要执执行行的的平平均均比比较较次次数数(也也称称为为平平均均查查找找长长度度)作作为为衡衡量量一一个个查查找找算算法法效效率率优优劣劣的的标标准准。平平均均查查找找长长度度ASL（Average Search Length）定义为：）定义为：其中其中,n是查找表中记录的个数。是查找表中记录的个数。pi是查找第是查找第i个记录的概率。一个记录的概率。一般地，均认为每个记录的查找概率相等，即般地，均认为每个记录的查找概率相等，即pi=1/n（1in），），ci是是找到第找到
4、第i个记录所需进行的比较次数个记录所需进行的比较次数。9.2 线性表的查找线性表的查找 在在表表的的组组织织方方式式中中,线线性性表表是是最最简简单单的的一一种种。三三种种在线性表上进行查找的方法：在线性表上进行查找的方法：（1）顺序查找）顺序查找 （2）二分查找）二分查找 （3）分块查找）分块查找 因因为为不不考考虑虑在在查查找找的的同同时时对对表表做做修修改改，故故上上述述三三种种查查找找操操作作都是在静态查找表上实现的。都是在静态查找表上实现的。例例 如如，在在 关关 键键 字字 序序 列列 为为3,9,1,5,8,10,6,7,2,4的的线线性性表表查查找找关关键键字为字为6的元素。的
5、元素。顺序查找过程如下：顺序查找过程如下：开始开始:3 9 1 5 8 10 6 7 2 4 第第1次比较次比较:3 9 1 5 8 10 6 7 2 4 i=0 第第2次比较次比较:3 9 1 5 8 10 6 7 2 4 i=1第第3次比较次比较:3 9 1 5 8 10 6 7 2 4 i=2 第第4次比较次比较:3 9 1 5 8 10 6 7 2 4 i=3 第第5次比较次比较:3 9 1 5 8 10 6 7 2 4 i=4 第第6次比较次比较:3 9 1 5 8 10 6 7 2 4 i=5 第第7次比较次比较:3 9 1 5 8 10 6 7 2 4 i=6 查找成功，返回序号
6、查找成功，返回序号6从前向后查找从前向后查找 顺顺序序查查找找的的算算法法如如下下（在在顺顺序序表表R0.n-1R0.n-1中中查查找找关关键键字字为为k k的的记记录录,成成功功时时返返回回找找到到的的记记录录位位置置,失失败败时时返返回回-1 1）：）：int SeqSearch(SeqList R,int n,KeyType k)int i=0;while(i=n)return-1;else return i;从顺序查找过程可以看到（不考虑越界比较从顺序查找过程可以看到（不考虑越界比较ix.key，只需在子表，只需在子表2中查找；中查找；例例 如如，在在 关关 键键 字字 有有 序序 序
7、序 列列2,4,7,9,10,14,18,26,32,40中中采采用用二二分分查查找找法查找关键字为法查找关键字为7的元素。的元素。二分查找过程如下：二分查找过程如下：查找成功，返回序号查找成功，返回序号2 开开始始:2 4 7 9 10 14 18 26 32 40 low=0 mid=(0+9)/2=4 high=90 1 2 3 4 5 6 7 8 9第第1次比较次比较:2 4 7 9 10 14 18 26 32 40 low=0 mid=(0+3)/2=1 high=3 0 1 2 3 4 5 6 7 8 9第第2次比较次比较:2 4 7 9 10 14 18 26 32 40 lo
8、w=2 mid=(2+3)/2=2 high=3 0 1 2 3 4 5 6 7 8 9思考题思考题采用二分查找的数据适合采用什么存储结构。采用二分查找的数据适合采用什么存储结构。其其算算法法如如下下（在在有有序序表表R0.n-1中中进进行行二二分分查查找找,成成功功时时返返回回记记录录的位置，失败时返回的位置，失败时返回-1）：）：int BinSearch(SeqList R,int n,KeyType k)int low=0,high=n-1,mid;while(lowk)/继续在继续在Rlow.mid-1查找查找 high=mid-1;else low=mid+1;/继续在继续在Rmi
9、d+1.high中查找中查找 return-1;递归算法：递归算法：int BinSearch1(SeqList R,int low,int high,KeyType k)int mid;if(lowk)/在在Rlow.mid-1查找查找 BinSearch1(R,low,mid-1,k);else BinSearch1(R,mid+1,high,k);/在在Rmid+1.high中查找中查找 else return-1;调用方法：调用方法：BinSearch1(R,0,n-1,k);二分查找的全部过程可用一棵二叉树来描述：二分查找的全部过程可用一棵二叉树来描述：把当前查找区间的中间位置上的记
10、录作为根；把当前查找区间的中间位置上的记录作为根；左左子子表表和和右右子子表表中中的的记记录录分分别别作作为为根根的的左左子子树树和和右右子子树。树。称为描述二分查找的称为描述二分查找的判定树判定树或或比较树比较树。R0.10的二分查线的判定树（的二分查线的判定树（n=11）例例 9.1对对 于于 给给 定定 11个个 数数 据据 元元 素素 的的 有有 序序 表表2,3,10,15,20,25,28,29,30,35,40，采用二分查找，试问：，采用二分查找，试问：（1）若若查查找找给给定定值值为为20的的元元素素,将将依依次次与与表表中中哪哪些些元元素比较？素比较？（2）若若查查找找给给定
11、定值值为为26的的元元素素,将将依依次次与与哪哪些些元元素素比比较？较？（3）假假设设查查找找表表中中每每个个元元素素的的概概率率相相同同,求求查查找找成成功功时的平均查找长度和查找不成功时的平均查找长度。时的平均查找长度和查找不成功时的平均查找长度。二分查找二分查找判定树判定树 （2）若若查查找找给给定定值值为为26的的元元素素,依依次次与与25,30,28元元素素比比较较,共比较共比较3次。次。（3）在在查查找找成成功功时时,会会找找到到图图中中某某个个圆圆形形结结点点,则则成成功功时时的的平均查找长度：平均查找长度：解解：（1）若若查查找找给给定定值值为为20的的元元素素,依依 次次 与
12、与 表表 中中25,10,15,20元元 素素 比比较较,共比较共比较4次。次。在查找不成功时在查找不成功时,会找到图中某个方形结点会找到图中某个方形结点,则不成功则不成功时的平均查找长度：时的平均查找长度：当当n较大时，判断树近似于高度为较大时，判断树近似于高度为h=log2(n+1)的满二叉树。的满二叉树。高度为高度为h外层结点层外层结点层结论：结论：（1）在）在n个元素有序表中采用二分查找成功时最多个元素有序表中采用二分查找成功时最多的元素比较次数为的元素比较次数为 log2n。（2）在）在n个元素有序表中采用二分查找成功时最多个元素有序表中采用二分查找成功时最多的元素比较次数为的元素比
13、较次数为 log2n 。成功的二分查找过程成功的二分查找过程恰好是走了一条从判定树的根到被查恰好是走了一条从判定树的根到被查记录的路径，经历比较的关键字次数恰为该记录在树中的层数。记录的路径，经历比较的关键字次数恰为该记录在树中的层数。若若查找失败查找失败，则其比较过程是经历了一条从判定树根到某，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。点的总数。借助二叉判定树，很容易求得二分查找的平均查找长度。借助二叉判定树，很容易求得二分查找的平均查找长度。为讨论方便起见，不妨设内部结点的总数
14、为为讨论方便起见，不妨设内部结点的总数为n=2h-1，则判定树，则判定树是高度为是高度为h=log2(n+1)的满二叉树（深度的满二叉树（深度h不计外部结点）。树不计外部结点）。树中第中第i层上的记录个数为层上的记录个数为2i-1，查找该层上的每个记录需要进行，查找该层上的每个记录需要进行i次比较。因此，在等概率假设下，二分查找成功时的平均查找次比较。因此，在等概率假设下，二分查找成功时的平均查找长度为：长度为：思考题：思考题：不成功查找的平均查找长度是多少？不成功查找的平均查找长度是多少？9.2.3 索引存储结构和分块查找索引存储结构和分块查找 1.索引存储结构索引存储结构 索引存储结构数据
15、表索引存储结构数据表+索引表索引表 索引表中的每一项称为索引项，索引项的一般形式是：索引表中的每一项称为索引项，索引项的一般形式是：（关键字（关键字,地址）地址）关键字唯一标识一个结点，地址作为指向该关键字对关键字唯一标识一个结点，地址作为指向该关键字对应结点的指针，也可以是相对地址。应结点的指针，也可以是相对地址。索引表索引表数据表数据表2.分块查找分块查找 性能：性能：介于顺序查找和二分查找之间的查找方法。介于顺序查找和二分查找之间的查找方法。思路：思路：（1）将数据表）将数据表R0.n-1均分为均分为b块块,前前b-1块中记录个数为块中记录个数为s=n/b，最后一块即第，最后一块即第b块
16、的记录数小于等于块的记录数小于等于s；（2）每一块中的关键字不一定有序，但前一块中的最大）每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是关键字必须小于后一块中的最小关键字，即要求表是“分块有分块有序序”的；的；（3）抽取各块中的最大关键字及其起始位置构成一个索）抽取各块中的最大关键字及其起始位置构成一个索引表引表IDX0.b-1,即即IDXi（0ib-1）中存放着第）中存放着第i块的最大关块的最大关键字及该块在表键字及该块在表R中的起始位置。由于表中的起始位置。由于表R是分块有序的，所是分块有序的，所以索引表是一个递增有序表。以索引表是一个递增有序表
17、。索引表的数据类型定义如下：索引表的数据类型定义如下：#define MAXI typedef struct KeyType key;/KeyType为关键字的类型为关键字的类型 int link;/指向对应块的起始下标指向对应块的起始下标 IdxType;typedef IdxType IDXMAXI;/索引表类型索引表类型 例如例如,设有一个线性表，其中包含设有一个线性表，其中包含25个记录个记录,其关键字序列为：其关键字序列为：8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,4,88,96,87假设将假设将25个记
18、录分为个记录分为5块块,每块中有每块中有5个记录个记录,该线性表的索引存该线性表的索引存储结构如下图所示。储结构如下图所示。采采用用二二分分查查找找索索引引表表的的分分块块查查找找算算法法如如下下（索索引引表表I的的长长度度为为m）：）：int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)int low=0,high=m-1,mid,i;int b=n/m上取整上取整;/b为每块的记录个数为每块的记录个数 while(low=k)high=mid-1;else low=mid+1;i=Ilow.link;while(i=Ilow.link+b
19、-1&Ri.key!=k)i+;if(ikey=k)/递归终结条件递归终结条件 return bt;if(kkey)return SearchBST(bt-lchild,k);/在左子树中递归查找在左子树中递归查找 else return SearchBST(bt-rchild,k);/在右子树中递归查找在右子树中递归查找 50308020908540358832例如，二叉排序树查找过程例如，二叉排序树查找过程查找关键字查找关键字=50,505035,503040355090,50809095 2.二叉排序树的插入和生成二叉排序树的插入和生成 在在二二叉叉排排序序树树中中插插入入一一个个新新记
20、记录录，要要保保证证插插入入后后仍仍满满足足BST性质。性质。插入过程：插入过程：（1）若若二二叉叉排排序序树树T为为空空，则则创创建建一一个个key域域为为k的的结结点点,将它作为根结点；将它作为根结点；（2）否否则则将将k和和根根结结点点的的关关键键字字比比较较，若若两两者者相相等等,则则说说明树中已有此关键字明树中已有此关键字k，无须插入，无须插入,直接返回直接返回0；（3）若）若kkey，则将，则将k插入根结点的左子树中。插入根结点的左子树中。（4）否则将它插入右子树中。）否则将它插入右子树中。对应的递归算法对应的递归算法InsertBST()如下：如下：int InsertBST(B
21、STNode*&p,KeyType k)/在在以以*p为为根根结结点点的的BST中中插插入入一一个个关关键键字字为为k的的结结点点。插插入入成成功功返返回回1,否则返回否则返回0 if(p=NULL)/原树为空原树为空,新插入的记录为根结点新插入的记录为根结点 p=(BSTNode*)malloc(sizeof(BSTNode);p-key=k;p-lchild=p-rchild=NULL;return 1;else if (k=p-key)/存在相同关键字的结点存在相同关键字的结点,返回返回0 return 0;else if(kkey)return InsertBST(p-lchild,k
22、);/插入到左子树中插入到左子树中 else return InsertBST(p-rchild,k);/插入到右子树中插入到右子树中 注意：先序遍历的思想 二二叉叉排排序序树树的的生生成成,是是从从一一个个空空树树开开始始,每每插插入入一一个个关关键键字字,就就调调用用一一次次插插入入算算法法将将它它插插入入到到当当前前已已生生成成的的二二叉叉排排序序树树中中。从从关关键键字字数数组组A0.n-1生生成成二二叉叉排排序序树树的的算算法法CreatBST()如如下：下：BSTNode*CreatBST(KeyType A,int n)/返回树根指针返回树根指针 BSTNode*bt=NULL;
23、/初始时初始时bt为空树为空树 int i=0;while(in)InsertBST(bt,Ai);/将将Ai插入二叉排序树插入二叉排序树T中中 i+;return bt;/返回建立的二叉排序树的根指针返回建立的二叉排序树的根指针 例例 9.3 已已 知知 一一 组组 关关 键键 字字 为为25,18,46,2,53,39,32,4,74,67,60,11。按按表表中中的的元元素素顺顺序序依依次次插插入入到到一一棵棵初初始始为为空空的的二二叉叉排排序序树树中中，画画出出该该二二叉叉排排序序树树，并并求求在在等等概概率率的的情情况况下下查查找找成功的平均查找长度。成功的平均查找长度。解解：生生成
24、成的的二二叉叉排排序序树树如如右右图图所所示。示。思考题思考题n个记录构造的二叉排序树的查找一定是个记录构造的二叉排序树的查找一定是O(log2n)？64725836472583508020908540358832（1）被删除的结点是叶子结点：）被删除的结点是叶子结点：直接删去该结点。直接删去该结点。例例如如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”3.二叉排序树的结点删除二叉排序树的结点删除3050308020908540358832（2）被删除的结点只有左子树或者只有右子树，用其左子）被删除的结点只有左子树或者只有右子树，用其左子树
25、或者右子树代替它。树或者右子树代替它。其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指指向被删除结点的左子树或右子树向被删除结点的左子树或右子树”。被删关键字被删关键字=408050308020908540358832（3）被删除的结点既有左子树，也有右子树）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除以其前驱替代之，然后再删除该前驱结点。前驱是左子树中该前驱结点。前驱是左子树中最大的结点。最大的结点。被删结点被删结点前驱结点前驱结点被删关键字被删关键字=50也可以用其后继替代之，然后再删除该后继也可以用其后继替代之，然后再删除该后继结点。后继是右子树中
26、最小的结点。结点。后继是右子树中最小的结点。6472583int DeleteBST(BSTNode*&bt,KeyType k)/在在bt中删除关键字为中删除关键字为k的结点的结点 if(bt=NULL)return 0;/空树删除失败空树删除失败 else if(kkey)return DeleteBST(bt-lchild,k);/递归在左子树中删除为递归在左子树中删除为k的结点的结点else if(kbt-key)return DeleteBST(bt-rchild,k);/递归在右子树中删除为递归在右子树中删除为k的结点的结点 else/找到了要删除的结点找到了要删除的结点 Dele
27、te(bt);/调用调用Delete(bt)函数删除函数删除*bt结点结点 return 1;void Delete(BSTNode*&p)/从二叉排序树中删除从二叉排序树中删除*p结点结点 BSTNode*q;if(p-rchild=NULL)/*p结点没有右子树的情况结点没有右子树的情况 q=p;p=p-lchild;/其右子树的根结点放在被删结点的位置上其右子树的根结点放在被删结点的位置上 free(q);else if(p-lchild=NULL)/*p结点没有左子树结点没有左子树 q=p;p=p-rchild;/将将*p结点的右子树作为双亲结点的相应子树结点的右子树作为双亲结点的相应
28、子树/free(q);else Delete1(p,p-lchild);/*p结点既没有左子树又没有右子树的情况结点既没有左子树又没有右子树的情况p右子树为空树，则只需重接它的左子树右子树为空树，则只需重接它的左子树q=p;p=p-lchild;free(q);pqqqpp左子树为空树，只需重接它的右子树左子树为空树，只需重接它的右子树q=p;p=p-rchild;free(q);q 删删除除二二叉叉排排序序树树结结点点的的算算法法DeleteBST()如如下下（指指针针变变量量p指指向待删除的结点向待删除的结点,指针变量指针变量q指向待删除结点指向待删除结点*p的双亲结点）：的双亲结点）：v
29、oid Delete1(BSTNode*p,BSTNode*&r)/当被删当被删*p结点有左右子树时的删除过程结点有左右子树时的删除过程 BSTNode*q;if(r-rchild!=NULL)Delete1(p,r-rchild);/递归找最右下结点递归找最右下结点 else /找到了最右下结点找到了最右下结点*r p-key=r-key;/将将*r的关键字值赋给的关键字值赋给*p q=r;r=r-lchild;/将左子树的根结点放在被删结点的位置上将左子树的根结点放在被删结点的位置上 free(q);/释放原释放原*r的空间的空间 q=p;r=p-lchild;while（!r-rchil
30、d）q=r;r=r-rchild;/r指向被删结点的前驱指向被删结点的前驱左右子树均不空左右子树均不空p-data=r-data;if（q!=p）q-rchild=r-lchild;else q-lchild=r-lchild;/重接重接*q的左子树的左子树free（r）;pqr9.3.2 平衡二叉树（平衡二叉树（AVL）若若一一棵棵二二叉叉树树中中每每个个结结点点的的左左、右右子子树树的的高高度度至至多相差多相差1,则称此二叉树为则称此二叉树为平衡二叉树平衡二叉树。在在算算法法中中,通通过过平平衡衡因因子子（balancd factor,用用bf表表示示）来来具具体体实现上述平衡二叉树的定义
31、。实现上述平衡二叉树的定义。平平衡衡因因子子：平平衡衡二二叉叉树树中中每每个个结结点点有有一一个个平平衡衡因因子子域域，每每个个结结点点的的平平衡衡因因子子是是该该结结点点左左子子树树的的高高度度减减去去右右子子树树的的高高度度。从从平平衡衡因因子子的的角角度度可可以以说说，若若一一棵棵二二叉叉树树中中所所有有结结点点的的平平衡衡因因子子的的绝绝对对值值小小于于或或等等于于1，即即平平衡衡因因子子取取值值为为1、0或或-1，则则该二叉树称为该二叉树称为平衡二叉树平衡二叉树。平衡二叉树和不平衡二叉树平衡二叉树和不平衡二叉树 548254821是平衡树是平衡树不是平衡树不是平衡树011000122
32、定义定义AVL树的结点的类型如下：树的结点的类型如下：typedef struct node /记录类型记录类型KeyType key;/关键字项关键字项 int bf;/增加的平衡因子增加的平衡因子 InfoType data;/其他数据域其他数据域 struct node*lchild,*rchild;/左右孩子指针左右孩子指针 BSTNode;平平衡衡二二叉叉树树中中插插入入新新结结点点方方式式与与二二叉叉排排序序树树相相似似，只只是是插插入后可能破坏了平衡二叉树的平衡性，解决方法是调整。入后可能破坏了平衡二叉树的平衡性，解决方法是调整。调整操作可归纳为下列四种情况：调整操作可归纳为下列
33、四种情况：（1）LL型调整型调整 LL调整调整542425LL插入关键字插入关键字2 （2）RR型调整型调整426589426895插入关键字插入关键字 9RR（3）LR型调整型调整16插入插入7377调整以调整以16为根的为根的不平衡子树不平衡子树316LR型调整型调整RL（4）RL型调整型调整7311916调整以调整以7为根的为根的不平衡子树不平衡子树883971116插入插入8 （4）RL型调整型调整RL 例例9.4 输输入入关关键键字字序序列列16,3,7,11,9,26,18,14,15,给给出出构构造造一一棵棵AVL树的步骤。树的步骤。在在平平衡衡二二叉叉树树上上进进行行查查找找的
34、的过过程程和和在在二二叉叉排排序序树树上上进进行行查查找找的的过过程程完完全全相相同同，因因此此，在在平平衡衡二二叉叉树树上上进进行行查查找找关关键键字字的的比比较次数不会超过平衡二叉树的深度。较次数不会超过平衡二叉树的深度。在在最最坏坏的的情情况况下下，普普通通二二叉叉排排序序树树的的查查找找长长度度为为O(n)。那那么么，平平衡衡二二叉叉树树的的情情况况又又是是怎怎样样的的呢呢？下下面面分分析析平平衡衡二二叉叉树树的的高高度度h和结点个数和结点个数n之间的关系。之间的关系。构构造造一一系系列列的的平平衡衡二二叉叉树树T1，T2，T3，其其中中，Th（h=1，2，3，）是是高高度度为为h且且
35、结结点点数数尽尽可可能能少少的的平平衡衡二二叉叉树，如下图所示的树，如下图所示的T1，T2，T3和和T4。为为了了构构造造Th，先先分分别别构构造造Th-1和和Th-2，使使Th以以Th-1和和Th-2作作为为其其根根结结点点的的左左、右右子子树树。对对于于每每一一个个Th，只只要要从从中中删删去去一一个个结结点点，就就会会失失去去平平衡衡或或高高度度不不再再是是h（显显然然，这这样样构构造造的的平平衡二叉树在结点个数相同的平衡二叉树中具有最大高度）。衡二叉树在结点个数相同的平衡二叉树中具有最大高度）。结点个数结点个数n最少的平衡二叉树最少的平衡二叉树 通过计算上述平衡二叉树中的结点个数，来建
36、立高度通过计算上述平衡二叉树中的结点个数，来建立高度与结点个数之间的关系。设与结点个数之间的关系。设N(h)为为Th的结点数，从图中的结点数，从图中可以看出有下列关系成立：可以看出有下列关系成立：N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1当当h1时，此关系类似于定义时，此关系类似于定义Fibonacci数的关系：数的关系：F(1)=1，F(2)=1，F(h)=F(h-1)+F(h-2)通过检查两个序列的前几项就可发现两者之间的对应关系：通过检查两个序列的前几项就可发现两者之间的对应关系：N(h)=F(h+2)-1由于由于Fibonacci数满足渐近公式：数满足渐近公式
37、：F(h)=其中，其中，故由此可得近似公式：故由此可得近似公式：N(h)=即：即：hlog2(N(h)+1)所以，含有所以，含有n个结点的平衡二叉树的平均查找长度为个结点的平衡二叉树的平均查找长度为O(log2n)。思考题思考题为什么提出为什么提出AVL树？树？9.3.3 B-树树 B-树树又又称称为为多多路路平平衡衡查查找找树树，是是一一种种组组织织和和维维护护外外存文件系统非常有效的数据结构。存文件系统非常有效的数据结构。B-树树中中所所有有结结点点的的孩孩子子结结点点最最大大值值称称为为B-树树的的阶阶，通通常常用用m表表示示，从从查查找找效效率率考考虑虑,要要求求m3。一一棵棵m阶阶B
38、-树树或或者者是是一一棵棵空空树，或者是满足下列要求的树，或者是满足下列要求的m叉树：叉树：（1）树树中中每每个个结结点点至至多多有有m个个孩孩子子结结点点（即即至至多多有有m-1个个关关键字）；键字）；（2）除除根根结结点点和和叶叶子子结结点点外外，其其他他结结点点至至少少有有 m/2 个个孩孩子子结点（即至少有结点（即至少有 m/2-1=(m-1)/2 个关键字）；个关键字）；（3）若若根根结结点点不不是是叶叶子子结结点点，则则根根结结点点至至少少有有两两个个孩孩子子结结点；点；（4）每个结点的结构为：）每个结点的结构为：其其中中，n为为该该结结点点中中的的关关键键字字个个数数，除除根根结
39、结点点和和叶叶子子结结点点外外，其其他他所所有有结结点点的的n大大于于等等于于 m/2-1，且且小小于于等等于于m-1；ki（1in）为为该该结结点点的的关关键键字字且且满满足足kiki+1；pi（0in）为为该该结结点点的的孩孩子子结结点点指指针针且且满满足足pi（0in-1）结结点点上上的的关关键键字字大大于于等等于于ki且小于且小于ki+1，pn结点上的关键字大于结点上的关键字大于kn。（5）所所有有叶叶子子结结点点都都在在同同一一层层上上，即即B-树树是是所所有有结结点点的的平衡因子均等于平衡因子均等于0的多路查找树。的多路查找树。一棵一棵3阶阶B-树树非根结点非叶子结点关键字个数：非
40、根结点非叶子结点关键字个数：m/2-1nm-1在在B-树的存储结构中树的存储结构中,各结点的类型定义如下：各结点的类型定义如下：#define MAXM 10/定义定义B-树的最大的阶数树的最大的阶数typedef int KeyType;/KeyType为关键字类型为关键字类型typedef struct node /B-树结点类型定义树结点类型定义 int keynum;/结点当前拥有的关键字的个数结点当前拥有的关键字的个数 KeyType keyMAXM;/1.keynum存放关键字存放关键字,0不用不用 struct node*parent;/双亲结点指针双亲结点指针 struct n
41、ode*ptrMAXM;/孩子结点指针数组孩子结点指针数组0.keynum BTNode;1.B-树的查找树的查找2.在在B-树树中中查查找找给给定定关关键键字字的的方方法法类类似似于于二二叉叉排排序序树树上上的的查查找找，不不同同的的是是在在每每个个记记录录上上确确定定向向下下查查找找的的路路径径不不一一定定是是二二路路（即即二二叉叉）的的，而而是是n+1路路的的。因因为为记记录录内内的的关关键键字字序序列列是是有有序序的的数数量量key1.n，故故既既可可以以用用顺顺序序查查找找,也也可可以以用用折折半半查查找找。在在一一棵棵B-树树上顺序查找关键字为上顺序查找关键字为k的方法为：的方法为
42、：nptr0key1ptr1key2keynptrn递增有序排列递增有序排列将将k与根结点中的与根结点中的keyi进行比较：进行比较：（1）若）若k=keyi，则查找成功；，则查找成功；（2）若若kkey1，则则沿沿着着指指针针ptr0所所指指的的子子树树继继续续查找；查找；（3）若若keyikkeyi+1，则则沿沿着着指指针针ptri所所指指的的子树继续查找；子树继续查找；（4）若若kkeyn，则则沿沿着着指指针针ptrn所所指指的的子子树树继继续续查找。查找。2.B-树的插入树的插入将关键字将关键字k插入到插入到B-树的过程分两步完成：树的过程分两步完成：（1）利利用用前前述述的的B-树树
43、的的查查找找算算法法找找出出该该关关键键字字的的插插入入结结点点（注意（注意B-树的插入结点一定是叶子结点）。树的插入结点一定是叶子结点）。（2）判判断断该该结结点点是是否否还还有有空空位位置置,即即判判断断该该结结点点是是否否满满足足nm-1，若若该该结结点点满满足足nm-1，说说明明该该结结点点还还有有空空位位置置，直直接接把把关关键键字字k插插入入到到该该结结点点的的合合适适位位置置上上（即即满满足足插插入入后后结结点点上上的的关关键键字仍保持有序）；字仍保持有序）；非根结点非叶子结点关键字个数：非根结点非叶子结点关键字个数：m/2-1nm-1 若若该该结结点点有有n=m-1，说说明明该
44、该结结点点已已没没有有空空位位置置，需需要要把把结点分裂成两个。结点分裂成两个。分分裂裂的的做做法法是是，取取一一新新结结点点，把把原原结结点点上上的的关关键键字字和和k按按升升序序排排序序后后，从从中中间间位位置置（即即 m/2=(m+1)/2 之之处处）把把关关键键字字（不不包包括括中中间间位位置置的的关关键键字字）分分成成两两部部分分，左左部部分分所所含含关关键键字字放放在在旧旧结结点点中中，右右部部分分所所含含关关键键字字放放在在新新结结点点中中，中中间间位位置置的的关关键键字字连连同同新新结结点点的的存存储储位位置置插插入入到到父父亲亲结结点点中中。如如果果父父结结点点的的关关键键字
45、字个个数数也也超超过过Max，则则要要再再分分裂裂，再再往往上上插插，直至这个过程传到根结点为止。直至这个过程传到根结点为止。非根结点非叶子结点关键字个数：非根结点非叶子结点关键字个数：m/2-1nm-1例如：关键字序列为：例如：关键字序列为：1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。创建一棵创建一棵5阶阶B-树。树。建立建立B-的过程如下图所示。的过程如下图所示。1 2 6 7插入插入1161 2 6 7 11 插入插入41 2 4插入插入8,137 8 11 13插入插入107 8 11 1311 137 8 6 10插入插入51
46、 2 4 5插入插入1711 13 17 6 10 167 8 9 插入插入9插入插入1611 13 16 1711 1317 20插入插入33 6 10 161 24 5插入插入12,14,18,1911 12 13 1417 18 19 20插入插入1514 1511 12 1313 163 6 10插入插入20163103.B-树的删除树的删除 B-树树的的删删除除过过程程与与插插入入过过程程类类似似，只只是是稍稍为为复复杂杂一一些些。要要使使删删除除后后的的结结点点中中的的关关键键字字个个数数 m/2-1，将将涉涉及及到到结结点点的的“合合并并”问题。在问题。在B-树上删除关键字树上删
47、除关键字k的过程分两步完成：的过程分两步完成：（1）利用前述的）利用前述的B-树的查找算法找出该关键字所在的结点。树的查找算法找出该关键字所在的结点。（2）在在结结点点上上删删除除关关键键字字k分分两两种种情情况况：一一种种是是在在叶叶子子结结点点上删除关键字；另一种是在非叶子结点上删除关键字。上删除关键字；另一种是在非叶子结点上删除关键字。（3）在非叶子结点上删除关键字的过程：）在非叶子结点上删除关键字的过程：假假设设要要删删除除关关键键字字keyi（1in），在在删删去去该该关关键键字字后后,以以该该结结点点ptri所所指指子子树树中中的的最最小小关关键键字字keymin来来代代替替被被删
48、删关关键键字字keyi所所在在的的位位置置（注注意意ptri所所指指子子树树中中的的最最小小关关键键字字keymin一定是在叶子结点上）。一定是在叶子结点上）。然然 后后 再再 以以 指指 针针 ptri所所 指指 结结 点点 为为 根根 结结 点点 查查 找找 并并 删删 除除keymin（即即再再以以ptri所所指指结结点点为为B-树树的的根根结结点点，以以keymin为要删除的关键字，然后再次调用为要删除的关键字，然后再次调用B-树上的删除算法）。树上的删除算法）。这这样样也也就就把把在在非非叶叶子子结结点点上上删删除除关关键键字字k的的问问题题转转化化成成了了在叶子结点上删除关键字在叶
49、子结点上删除关键字keymin的问题。的问题。（4）在）在B-树的叶子结点上删除关键字共有以下三种情况：树的叶子结点上删除关键字共有以下三种情况：假假如如被被删删结结点点的的关关键键字字个个数数大大于于Min，说说明明删删去去该该关关键键字字后该结点仍满足后该结点仍满足B-树的定义，则可直接删去该关键字。树的定义，则可直接删去该关键字。假假如如被被删删结结点点的的关关键键字字个个数数等等于于Min，说说明明删删去去关关键键字字后后该结点将不满足该结点将不满足B-树的定义。树的定义。此此时时若若该该结结点点的的左左（或或右右）兄兄弟弟结结点点中中关关键键字字个个数数大大于于Min,则则把把该该结
50、结点点的的左左（或或右右）兄兄弟弟结结点点中中最最大大（或或最最小小）的的关关键键字字上上移移到到双双亲亲结结点点中中，同同时时把把双双亲亲结结点点中中大大于于（或或小小于于）上上移移关关键键字字的的关关键键字字下下移移到到要要删删除除关关键键字字的的结结点点中中，这这样样删删去去关关键键字字k后后该该结点以及它的左（或右）兄弟结点都仍旧满足结点以及它的左（或右）兄弟结点都仍旧满足B-树的定义。树的定义。非根结点非叶子结点关键字个数：非根结点非叶子结点关键字个数：m/2-1nm-1 假假如如被被删删结结点点的的关关键键字字个个数数等等于于Min，并并且且该该结结点点的的左和右兄弟结点（如果存在