《数据结构 第九章 静态查找.ppt》由会员分享，可在线阅读，更多相关《数据结构 第九章 静态查找.ppt（121页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章第九章查查 找找何谓查找表何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的对查找表经常进行的操作操作:1)查查询询某个“特定的”数据元素是否在查找 表中；2)检检索索某个“特定的”数据元素的各种属性；3)在查找表中插入插入一个数据元素；4)从查找表中删去删去某个数据元素。仅作查询和检索操作的查找表为静态查找表。静态查找表静态查找表 有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素,此类表为
2、动态查找表。动态查找表动态查找表查找表可分为两类查找表可分为两类:关键字关键字 用来标识一个数据元素（或记录）用来标识一个数据元素（或记录）的某个数据项的值，称为关键字。的某个数据项的值，称为关键字。主关键字主关键字 若此关键字可唯一地标识一个记若此关键字可唯一地标识一个记录，则称此关键字是主关键字；录，则称此关键字是主关键字；次关键字次关键字 反之，用以识别若干记录的关键反之，用以识别若干记录的关键字是次关键字。字是次关键字。根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一确定一个其个其关键字等于等于给定值的数据元素或的数据元素或(记录记录)。查找查找 若查找表中存在这样一个记
3、录，则称若查找表中存在这样一个记录，则称“查查找成功找成功”。查找结果给出。查找结果给出整个记录的信息，或或指示该记录在查找表中的指示该记录在查找表中的位置；否则称否则称“查找不成功查找不成功”。查找结果。查找结果给出“空记录”或“空指针”。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，用另外一种结构来表用另外一种结构来表示查找表示查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构查找的方法取决于查找表的结构,即表中数据元素是依何种关系组织在一起的。9.1 静态查找表静态查找表9.
4、2 动态查找树表动态查找树表9.3 哈希表哈希表9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的每个数据元素含有类型相同的关键字关键字，可唯一标识数据元素。数据元素同属一个集合。ADT StaticSearchTable Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit();基本操作基本操作P：ADT StaticSearchTable构造一个含n个数据元素的静态查找表ST。Create(&ST,n);操作结果：销毁表ST。Destroy
5、(&ST);初始条件：操作结果：静态查找表ST存在；若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Search(ST,key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST,Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct /数据元素存储空间基址，建表时数据元素存储空间基址，建表时 /按实际长度分配，按实际长
6、度分配，0号单元留空号单元留空 int length;/表的长度表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构为ElemType*elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key;/关键字域关键字域 /其它属性域其它属性域 ElemType;,TElemType;一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表 三、静态查找树表三、静态查找树表四、索引顺序表四、索引顺序表 以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表ST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=
7、64,要求 ST.elemk=e,问:k=?kkkint location(SqList L,ElemType&e,Status(*compare)(ElemType,ElemType)k=1;p=L.elem;while(k=L.length&!(*compare)(*p+,e)k+;if(k=L.length)return k;else return 0;/locationST.elemiST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST,KeyType key)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 /key
8、的数据元素。若找到，则函数值为的数据元素。若找到，则函数值为 /该元素在表中的位置，否则为该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找从后往前找 return i;/找不到时，找不到时，i为为0/Search_Seq 查找算法的平均查找长度平均查找长度 (Average Search Length)为确定记录在表中的位置，需和给定为确定记录在表中的位置，需和给定值进行比较的关键字次数的期望值称为查值进行比较的关键字次数的期望值称为查找算法在查找成功时的找算法在查找成功时的平
9、均查找长度平均查找长度。分析顺序查找的时间性能分析顺序查找的时间性能对于含有对于含有n个数据元素的表，查找成功时的个数据元素的表，查找成功时的平均查找长度为平均查找长度为:n ASL=PiCi i=1其中其中:Pi 为查找第为查找第i 个数据元素的概率，且个数据元素的概率，且 Ci 为为查到第查到第i 个数据元素时，需要进行个数据元素时，需要进行 的比较次数的比较次数.在在等概率等概率查找的情况下，查找的情况下，顺序表查找的平均查找长度顺序表查找的平均查找长度为：为：对对顺序表顺序表而言，而言，Ci 取决于所查元素所处的位置：取决于所查元素所处的位置：查找记录是查找记录是An时时,仅需比较一次
10、仅需比较一次;查找记录是查找记录是A1时时,要比较要比较n次次;查找记录是查找记录是Ai时时,要比较要比较n-i+1次次.ASL=nP1+(n-1)P2+(n-i+1)Pi+2Pn-1+Pn 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在在不等概率查找不等概率查找的情况下，的情况下，ASLss 在在 PnPn-1P2P1时时取极小值取极小值 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。折半查找折半查
11、找又称为又称为二分查找二分查找基本思想基本思想 如果查找表中的数据元素按关键字有序如果查找表中的数据元素按关键字有序(假设假设递增有序递增有序),),则在查找时不必逐个顺序比较则在查找时不必逐个顺序比较,而采用而采用跳跃的方式跳跃的方式,先与先与“中间位置中间位置”的记录关键字值比较的记录关键字值比较,若相等则查若相等则查找成功找成功;若给定值大于若给定值大于“中间位置中间位置”的关键字值的关键字值,则在后半部则在后半部继续进行折半查找继续进行折半查找;否则在前半部进行折半查找否则在前半部进行折半查找.折半查找折半查找仅适用仅适用于以于以顺序存贮结构组织的查顺序存贮结构组织的查找表找表的查找的
12、查找。ST.elemST.length例如例如:key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid =(low+high)/2折半查找算法折半查找算法设待查元素所在区域的下界为设待查元素所在区域的下界为low,上界上界为为hig,则中间位置则中间位置mid=(low+hig)DIV2若此元素关键字值等于给定值若此元素关键字值等于给定值,则查找成则查找成功功;若此元素关键字值大于给定值若此元素关键字值大于给定值,则在区域则在区域mid+1，hig进行折半查找进行折半查找若此关键字值小于给定值若此关键字值小
13、于给定值,则在区域则在区域low，mid-1内进行折半查找内进行折半查找int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值置区间初值 while(low 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。三、静态查找树表三、静态查找树表 当有序表中各记录的查找概率相等查找概率相等时，折半查找折半查找其性能最优。在不等概率不等概率查找查找的情况下，折半查找折半查找情况如何？关键字:A B C D E Pi:0.2 0.3 0.05 0.3 0.15 Ci:
14、2 3 1 2 3 在不等概率查找不等概率查找的情况下，折半查折半查找找不是不是有序表最好的查找方法。例如例如:假设有序表中含5个记录，并且已知各记录的查找概率不等查找概率不等，此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变Ci的值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15=1.9 这就说明，当有序表中各记录的查查找概率不等找概率不等时，折半查找折半查找性能未必是最未必是最优优的。那么，描述此类查找过程的判定树为何类二叉树时，其查找性能最佳？如果只考虑查找成功的情况，则使查找性能达到最佳的判定树是其带权内路径长度之和P
15、H值 n PH=wihi i=1取最小值的二叉树。其中：n为二叉树上结点的个数；hi为第i个结点在二叉树上的层次数；wi为结点的权，且wi=cpi(i=1,2,n)pi为结点的查找概率，c为某个常量称PH值取最小的二叉树为静态最优查找树静态最优查找树。构造静态最优查找树静态最优查找树花费的时间代价较高，在此不做讨论。四、索引顺序表四、索引顺序表索引顺序查找又称索引顺序查找又称分块查找分块查找数据元素的数据元素的特点特点:若把所有若把所有n个数据元素分成个数据元素分成m块块,第一第一块中任一元素的关键字都小于第二块中任一块中任一元素的关键字都小于第二块中任一元素的关键字元素的关键字,第二块中任一
16、元素的关键字第二块中任一元素的关键字都小于第三块中的任一元素的关键字都小于第三块中的任一元素的关键字.,.,第第m-1块中任一元素的关键字都小于第块中任一元素的关键字都小于第m块中块中的任一元素的关键字的任一元素的关键字.而每一块中元素的关而每一块中元素的关键字不一定是有序的键字不一定是有序的。213343851782119433740313322256178735585索引顺序查找示例索引顺序查找示例将将17,8,21,19,31,33,22,25,43,37,40,61,78,73,55,85 分为分为4块块:17,8,21,19,31,33,22,25,43,37,40,61,78,73
17、,55,85以每块中最大关键字作为该块所有元素的索引以每块中最大关键字作为该块所有元素的索引索引顺序查找的索引顺序查找的优点优点是是:在表中插入或删除一个元素时在表中插入或删除一个元素时,只只要找到该元素所属的块要找到该元素所属的块,然后在块内进然后在块内进行插入和删除。因块内元素的存放是行插入和删除。因块内元素的存放是任意的任意的,所以插入和删除时不需移动大所以插入和删除时不需移动大量元素量元素.所付出的代价是增加了存放索所付出的代价是增加了存放索引表的辅助空间。引表的辅助空间。索引顺序查找算法索引顺序查找算法基本思想基本思想:先抽出各块中的最大关键字构成一先抽出各块中的最大关键字构成一个索
18、引表；个索引表；查找分两部进行查找分两部进行:先对索引表进行折半查找或顺序查找先对索引表进行折半查找或顺序查找,确定待查记录在哪一块。确定待查记录在哪一块。在已确定的那一块中进行顺序查找。在已确定的那一块中进行顺序查找。索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间（块）；2）在顺序表的某个区间（块）内进行查找。注意：索引可以根据查找表的特点来构造。注意：索引可以根据查找表的特点来构造。可见，索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。索引顺序查找的平均查找长度索引顺序查找的平均查找长度=查找查找“索引索引”的平均查找长度的平均查找长度 +查找
19、查找“顺序表顺序表”的平均查找长度的平均查找长度四种查找方法比较四种查找方法比较顺序查找顺序查找 折半查找折半查找 静态树表静态树表查找查找分块查找分块查找平均查找平均查找长度长度最大最大等概率查等概率查找最小找最小不等概率不等概率查找最小查找最小次小次小表的表的结构结构 有序表、有序表、无序表均无序表均可可仅适用于仅适用于有序表有序表仅适用于仅适用于有序表有序表表中元素表中元素逐段有序逐段有序表的表的存储存储结构结构顺序、链顺序、链式结构均式结构均可可仅适用于仅适用于顺序存储顺序存储仅适用于仅适用于顺序存储顺序存储顺序、链顺序、链式均可，式均可，索引表顺索引表顺序存储序存储9.2 动动 态态
20、 查查 找找 树树 表表ADT DynamicSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R：数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit();ADT DynamicSearchTa
21、ble操作结果：操作结果：构造一个空的动态查找表DT。InitDSTable(&DT)销毁动态查找表DT。DestroyDSTable(&DT)初始条件：初始条件：操作结果：操作结果：动态查找表DT存在；若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。SearchDSTable(DT,key)初始条件：初始条件：操作结果：操作结果：动态查找表DT存在，key为和关键字类型相同的给定值；动态查找表DT存在，e 为待插入的数据元素；InsertDSTable(&DT,e)初始条件：初始条件：操作结果：操作结果：若DT中不存在其关键字等于 e.key 的
22、 数据元素，则插入 e 到DT。动态查找表DT存在，key为和关键字类型相同的给定值；DeleteDSTable(&T,key)初始条件：初始条件：操作结果：操作结果：若DT中存在其关键字等于key的数据元素，则删除之。动态查找表DT存在，Visit是对结点操作的应用函数；TraverseDSTable(DT,Visit()初始条件：初始条件：操作结果：操作结果：按某种次序对DT的每个结点调用函数 Visit()一次且至多一次。一旦 Visit()失败，则操作失败。一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平衡树三、三、B-树树四、四、B+树树五、键树五、键
23、树一、二叉排序树一、二叉排序树(二叉查找树二叉查找树)1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析 (1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1定义：定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：(3)它的左、右子树也都分别是二叉排序树。(2)若它的右子树不空，则右子树上所有结点的值均大于根结点的值；503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不 通常，取二叉链表作为二叉排序树的存储结构typedef struct BiTNode /结点结构结点结构 struc
24、t BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;TElemType data;2二叉排序树的查找算法：二叉排序树的查找算法：1)若给定值等于等于根结点的关键字，则查找成功查找成功；2)若给定值小于小于根结点的关键字，则继续在左子继续在左子树上进行查找；树上进行查找；3)若给定值大于大于根结点的关键字，则继续在右继续在右子树上进行查找。子树上进行查找。否则，若二叉排序树为空为空，则查找不成功查找不成功；50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字=50,505035,5030403550
25、90,50809095,从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径：从根结点出发，沿着左分支或右分支逐从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。层向下直至指针指向空树为止。查找成功查找成功 查找不成功查找不成功算法描述如下：算法描述如下：Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree&p)/在根指针在根指针 T 所指二叉排序树中递归地查找其
26、所指二叉排序树中递归地查找其 /关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功，/则返回指针则返回指针 p 所指该数据元素的结点，并返回所指该数据元素的结点，并返回 /函数值为函数值为 TRUE;/SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 /指针指针 p 所指查找路径上访问的最后一个结点，所指查找路径上访问的最后一个结点，/并返回函数值为并返回函数值为FALSE,指针指针 f 指向当前访问指向当前访问 /的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULLif(!T)else if(EQ(key,T-data.key)else
27、 if(LT(key,T-data.key)else p=f;return FALSE;/查找不成功查找不成功 p=T;return TRUE;/查找成功查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找在右子树中继续查找30201040352523fT设 key=48fTfT22pfTfTTTTfffp 根据动态查找表的定义，“插入插入”操作在操作在查找不成功查找不成功时才进行时才进行；3二叉排序树的插入算法二叉排序树的插入算法 若二叉排序树为空树空树，则新插入的结
28、点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。Status Insert BST(BiTree&T,ElemType e)/当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 /数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 /回回 TRUE;否则，不进行插入并返回否则，不进行插入并返回FALSE if(!SearchBST(T,e.key,NULL,p)/查找不成功查找不成功 /插入插入 else return FALSE;/查找成功查找成功/Insert BST s
29、=(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;/插入成功插入成功(1)被删除的结点是叶子；(2)被删除的结点只有左子树或者只有右子树；(3)被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排
30、序树的删除算法可分三种情况讨论：和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性仍然保持二叉排序树的特性。50308020908540358832(1)被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832(2)被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向指向被删除结点的左子树或右子树被删除结点的左子树或右子树”。被删关键字被删关键字
31、=408050308020908540358832(3)被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字=50Status DeleteBST(BiTree&T,KeyType key)/若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 /数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 /函数值函数值 TRUE，否则返回函数值否则返回函数值 FALSE if(!T)return FALSE;/不存在关键字等于不
32、存在关键字等于key的数据元素的数据元素 else /DeleteBST算法描述如下：算法描述如下：if(EQ(key,T-data.key)/找到关键字等于找到关键字等于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)/从从二叉排序树中删除结点二叉排序树中删除结点 p，/并重接它的左
33、子树或右子树并重接它的左子树或右子树 if(!p-rchild)/右子树为空右子树为空 else if(!p-lchild)/左子树为空左子树为空 else /左、左、右子树都不为空右子树都不为空/Delete其中删除操作删除操作过程如下所描述：/右子树为空树则只需重接它的左子树右子树为空树则只需重接它的左子树q=p;p=p-lchild;free(q);ppqq/左子树为空树只需重接它的右子树左子树为空树只需重接它的右子树q=p;p=p-rchild;free(q);ppqqq=p;s=p-lchild;while(!s-rchild)q=s;s=s-rchild;/s 指向被删结点的前驱指
34、向被删结点的前驱/左右子树均不空左右子树均不空p-data=s-data;if(q!=p)q-rchild=s-lchild;else q-lchild=s-lchild;/重接重接*q的左子树的左子树free(s);pqs结论：结论：一个无序序列可以通过构造一棵二叉一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程；即为对无序序列进行排序的过程；每次插入的新结点都是二叉排序树的每次插入的新结点都是二叉排序树的叶子结点，在进行插入操作时，不必移动其叶子结点，在进行插入操作时，不必移动其它结点，仅需修改某个结点
35、的指针由空变为它结点，仅需修改某个结点的指针由空变为非空即可。这就相当于在一个有序序列上插非空即可。这就相当于在一个有序序列上插入一个元素而没有移动其它元素。这个特性入一个元素而没有移动其它元素。这个特性告诉我们，对于需要经常插入和删除记录的告诉我们，对于需要经常插入和删除记录的有序表采用二叉排序树结构更为合适。有序表采用二叉排序树结构更为合适。5查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。由关键字序列由关键字序列 3，1，2
36、，5，4构造而得的二叉排序树，构造而得的二叉排序树，由关键字序列由关键字序列 1，2，3，4，5构造而得的二叉排序树，构造而得的二叉排序树，例如：例如：2134535412ASL=（1+2+3+4+5）/5 =3ASL=（1+2+3+2+3）/5 =2.2 下面讨论平均情况下面讨论平均情况:不失一般性，假设长度为 n 的序列中有 k 个关键字小于小于第一个关键字，则必有 n-k-1 个关键字大于大于第一个关键字,由它构造的二叉排序树n-k-1k的平均查找长度是 n 和 k 的函数P(n,k)(0 k n-1)。假设 n 个关键字可能出现的 n!种排列的可能性相同，则含 n 个关键字的二叉排序树
37、的平均查找长度：在等概率查找等概率查找的情况下，二、二叉平衡树二、二叉平衡树何谓何谓“二叉平衡树二叉平衡树”？二叉平衡树的查找性能分析二叉平衡树的查找性能分析二叉平衡树二叉平衡树 又称又称AVL树。它或者是一棵空树，或者树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树或右是具有下列性质的二叉树：它的左子树或右子树都是平衡二叉树，且左子树和右子树的子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过深度之差的绝对值不超过1 1。平衡因子平衡因子 二叉树上任一结点的左子树深度减去右二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。子树深度的差值，称为此结点
38、的平衡因子。二叉平衡树二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之树中每个结点的左、右子树深度之差的绝对值不大于差的绝对值不大于1，即，即 。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树1100-110-10102-10010-100-2100平衡二叉树平衡二叉树不平衡的二叉树不平衡的二叉树 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析：平衡树的查找性能分析：因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的
39、次数进行比较的关键字的次数和和 log(n)相当。三、三、B-树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析1B-树的定义树的定义 B-树是一种平衡平衡的多路查找多路查找树，它在文件系统中很有用。一棵一棵m阶的阶的B-树，或为空树，或为满足下列特树，或为空树，或为满足下列特性的性的m叉树：叉树：树中每个结点至多有树中每个结点至多有m 棵子树；棵子树；若根结点不是叶子结点，则至少有两棵子若根结点不是叶子结点，则至少有两棵子树；树；除根之外的所有非终端结点至少有除根之外的所有非终端结点至少有 m/2 棵棵子树。子树。所有的非终端结点中包含下列信息
40、数据所有的非终端结点中包含下列信息数据 (n,A0,K1,A1,K2,A2,Kn,An)其中：其中：Ki(i=1,2,n)为关键字，且为关键字，且KiKi+1(i=1,n-1);Ai(i=0,n)为指向子树根结点的指针，且指为指向子树根结点的指针，且指针针Ai-1所指子树中所有结点的关键字均小于所指子树中所有结点的关键字均小于Ki(i=1,n),An所指子树中所有结点的关键字均大所指子树中所有结点的关键字均大于于Kn,n(m/2-1nm-1)为关键字的个数为关键字的个数(或或n+1为子树个为子树个数数)。所有的叶子结点都出现在同一层次上，并且所有的叶子结点都出现在同一层次上，并且不带信息不带信
41、息(可以看作是外部结点或查找失败的结点，可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空实际上这些结点不存在，指向这些结点的指针为空)。如图所示为一棵3阶的B-树。在 m 阶的B-树上，每个非终端结点可能含有：n 个关键字关键字 Ki（1 in）nm n 个指向记录的指针指向记录的指针 Di（1in）n+1 个指向子树的指针指向子树的指针 Ai（0in）多叉树的特性非叶结点中的多个关键字多个关键字均自小至大自小至大有有序排列，即：K1 K2 keynum;i=Search(p,K);/在在p-key1.keynum中查找中查找 i，p-keyi=Kkeyi+1
42、if(i0&p-keyi=K)found=TRUE;else q=p;p=p-ptri;/q 指示指示 p 的双亲的双亲 if(found)return(p,i,1);/查找成功查找成功 else return(q,i,0);/查找不成功查找不成功 在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：3插入插入1)插入后，该结点的关键字个数nm，不修改指针;2)插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，令 s=m/2，在原结点中保留 （A0，K1，Ks-1，As-1）；建新结点 （As，Ks+1，Kn，An）；将（
43、Ks，p）插入双亲结点；3)若双亲为空，则建新的根结点。例如:下列为 3 阶B-树50 20 40 80 插入关键字=60,60 80 90,60 80 90 90 50 80 60 30,40 20 30 50 808030 50 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。4删除删除 在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度树的深度。5查找性能的分
44、析查找性能的分析 在含在含 N 个关键字的个关键字的 B-树上进树上进行一次查找，需访问的结点个数不行一次查找，需访问的结点个数不超过超过 log m/2(N+1)/2)+1结论：结论：是是B-树的一种变型树的一种变型四、四、B+树树1B+树的结构特点：树的结构特点：每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指向含最小关键字的结点；每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。50 96 15 5062
45、 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot2查找过程查找过程 在 B+树上，既可以进行缩小范围的查 找，也可以进行顺序查找；在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束；若在结点内查找时，给定值Ki，则 应继续在 Ai 所指子树中进行查找。3插入和删除的操作插入和删除的操作 类似于类似于B-树进行，即必要时，树进行，即必要时，也需要进行结点的也需要进行结点的“分裂分裂”或或“归并归并”。五、键五、键 树树1.键树键树2.双链树双链树3.Trie树树 键树键树又称又称数字查找树数字查找树，它是一棵度，它是一棵度2的树
46、，树中的每个结点中不是包含一的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键个或几个关键字，而是只含有组成关键字的符号。字的符号。例如，若关键字是数值，则结点中例如，若关键字是数值，则结点中只包含一个数位；若关键字是单词，则只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。结点中只包含一个字母字符。1.键树键树HAD$S$VE$E$R$E$IGH$S$例如例如:表示关键字集合HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS 键树的结构特点：键树的结构特点：关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深
47、度和关键字集合的大小无关键树的深度和关键字集合的大小无关；键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符$小于任何其它符号。2.双链树双链树 以二叉链表作存储结构实现的键树typedef enum LEAF,BRANCH NodeKind;/两种结点：两种结点：叶子叶子 和和 分支分支结点结构结点结构:first symbol next分支结点分支结点infoptr symbol next叶子结点叶子结点指向孩子结点指向孩子结点的指针的指针指向兄弟结点指向兄弟结点的指针的指针指向记录指向记录的指针的指针 H AD$HADE$R$ES$GH$I HEHERHEREHIGHHIST 叶子结点叶子结点分支结点分支结点含关键字含关键字的记录的记录3.Trie树树 以多重链表作存储结构实现的键树结点结构结点结构:分支结点分支结点叶子结点叶子结点指向记录的指针0 1 2 3 4 5 24 25 26关键字关键字指向下层结点的指针每个域对应一个“字母”0 1(A)3 4 5(E)9(I)268(H)4(D)19(S)22(V)0 18(R)7(G)190 5(E)THADHAS HAVE HEHERHEREHIGHHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针