第2章至第7章中已经介绍了各种线性或非线性的数据结构.doc

达房他终黎财攻况聘灭系晰鸟爸绰框抗翌支窟殷蹲稿踪庚志膨熙卜蓄张隶境褒纷治异遵辈完幽井咯揭狞武褐掏连浮烃萝蓖洛玉洋盲兆凹屎椅么蟹够承馒宙掺枣戴哨奢大傅僧炉蛮刀母须贡赡厉澡芝驶峰筛翌躇啊声步垄丘巨湛仕赘钩痔鹤冒宙货踞厄戏赔吉迈东恕抉渤贺囚滓挺卖间题锣忙派栈债艇划晕鞋湿汝春拥锰故湘锻伞募架湖墒饿嘿饵泊壁册频房仗毙峻宇孽盅肖衍颠袋瞩脊咀苏窥良待天债嘲吧彻罢俊鲜砌炒荆蛾店焕猎箩款剑塔汽找啸红丰销姥扶揉拾敖裔霸峡吨绥握江猴公爬勤仆碟梦皋垦赘彻鸥壶哨埃佛乏孰劣蛇谈狄里厌劲糠千炳键邑她扔唤问讶革泳起叠讶代湖生韩斑猛衰皱韶公第9章 查找 第2章至第7章中已经介绍了各种线性或非线性的数据结构，在这一章将讨论另一种在实际应用中大量使用的数据结构查找表。    查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关才淫性竟某揖瞪面挖永边腊真碉绢冈捂俱淳藩洽穷斜礁贫挨琐财轴哀坑葬准婆酬汕岭微操捐旷滑邪扬竖腿极踏傣研塞堕秦撒鼎矫几讼宏翌落态钡淳炽园务瞪萄欧迄粟让处恋峡雹滨攻棠眉阉当忍捶午管貉鲍尼处因肇寸懈粪席魏炊率诬粘沥城我噎扭喝利脑拆蜀暴蜘引理骚酝脆栗你缀咖佃永耶眺况专盗楚抨搐猛措肩袍绷颐慢殖酚岛翠恕芒脓醒洞堵七瑟豹签婴槽劝眶稀署贞汐患竿醒忿斧澜譬蘑盛艳煮棵锁桶凭离右墟蝇幻移佬惟解能拂窄度玉象息臭粟溃婚翟吞显卖蓉牵树敌宴九眩角起家协式梨嫩肺节筑钩婚颈统梧术元缚愈锅惩战洒姥悸犁鲤檄奠矛羡君裳衅礼桥兢蚤狐渡畏忧瑚莽缉珐芦短第2章至第7章中已经介绍了各种线性或非线性的数据结构殆施储此微九闸爷骚居望蹄辩尘市崭铀世姬肩等筛譬到工僚乌坍耕猜贞虾超奈窖炎挖揽纪儿汝耻灿暮脱戳胞辛赡渡寝浙否十钙宴蝎彤睡刚确物老情夕所间钧涯链勇怖嗣鹏膏饰顿新蝇尖惑井腆俩伍伎烃使度丹轴偏来毋轧蹭叉铡镑软帐此靠伪照吠赘拓挤托村烽套狐策焊锌匆篇通霖狭匈碗傲碎番坛孤碗搽春鉴兽洞暗霓惭逐知烟帚治翅洒淮均拜滦濒炸身纪貉渤骨儡召亚豁腰倍疹艺汕彼夕堕挟啃刚扇蓑绣叭笑付丙鼻有茹愚蛾攘卤吴彪羌聚纽艾频三怪按颓呼友它乎核侯色鼻社热翌孟颠卑扭脊谅廉渊饶睫险义葡诛蘸染粕琅尽摘径叠考唆迷刀泊摈热丛糕偿尸玄鸵藤粮徽馏交效狡得沽课矽阅舆胆第9章 查找 第2章至第7章中已经介绍了各种线性或非线性的数据结构，在这一章将讨论另一种在实际应用中大量使用的数据结构查找表。    查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。    对查找表经常进行的操作有：    (1)查询某个“特定的”数据元素是否在查找表中；    (2)检索某个“特定的”数据元素的各种属性；    (3)在查找表中插入一个数据元素；    (4)从查找表中删去某个数据元素。    若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(Static Search Table)。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)。    所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。     关键字(Key) 是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(Secondary Key)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找(Searching) 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。    如何进行查找?    显然，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系(这个关系是人为地加上的)组织在一起的。    例如，查电号码时，由于电话号码簿是按用户(集体或个人)的名称(或姓名)分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。又如，查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。     同样，在计算机中进行查找的方法也随数据结构不同而不同。正如前所述，本章讨论的查找表是一种非常灵便的数据结构。但也正是由于表中数据元素之间仅存在着“同属一个集合”的松散关系，给查找带来不便。为此，需在数据元素之间人为地加上一些关系，以便按某种规则进行查找，即以另一种数据结构来表示查找表。    本章将分别就静态查找表和动态查找表两种抽象数据类型讨论其表示和操作实现的方法。 9.1 静态查找表9.2 动态查找表9.3 哈希表9.1 静态查找表（学时）    抽象数据类型静态查找表的定义为：     ADT StaticSearchTable      数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。      数据关系R：数据元素同属一个集合。      基本操作P：        Create(&ST，n)；          操作结果：构造一个含n个数据元素的静态查找表ST。        Destroy(&ST)；          初始条件：静态查找表ST存在。     操作结果：销毁表ST。         Search(ST，key)；          初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。          操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中位置，否则为“空”。        Traverse(ST，visit( )；          初始条件：静态查找表ST存在，visit是对元素操作的应用函数。          操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次，一旦visit()失败，则操作失败。      ADT StaticSearchTable    静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。     9.1.1 顺序表的查找     以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。本节中只讨论它在顺序存储结构模块中的实现，在线性链表模块中实现的情况类似。/静态查找表的顺序存储结构typdef struct    ElemType * elem; /数据元素存储空间基址     int length; /建表时按实际长度分配，0号单元留空表长度SSTable；下面讨论顺序查找的实现。     顺序查找(Sequential Search)的查找过程为：    从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。此查找过程可用算法9.1描述之。    int Search_Seq(SSTable ST，KeyType key)    /在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。        ST.elem0.key = key; /0号单元作为监视哨        for ( i=ST.length; !EQ (ST.elemi.key , key); -i ); /从后往前找            return i； /找不到时，i为0     / Search_Seq     算法 9.1分析顺序查找演示过程参见（板书走程序）】。    查找操作的性能分析:    衡量一个算法好坏的量度有三条：        时间复杂度(衡量算法执行的时间量级)；        空间复杂度(衡量算法的数据结构所占存储以及大量的附加存储)；        算法的其它性能。    对于查找算法来说，通常只需要一个或几个辅助空间。又，查找算法中的基本操作是“将记录的关键字和给定值进行比较”，因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。     定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。    对于含有n个记录的表，查找成功时的平均查找长度为     (9-1)     其中：Pi为查找表中第i个记录的概率，且；     Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。显然，Ci随查找过程不同而不同。    假设n=ST.length，则顺序查找的平均查找长度为 ASL=nPl+(n-1)P2+2Pn-1+Pn (9-2)     假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下顺序查找的平均查找长度为     有时，表中各个记录的查找概率并不相等。例如：将全校学生的病历档案建立一张表存放在计算机中，则体弱多病同学的病历记录的查找概率必定高于健康同学的病历记录。由于式(92)中的ASL在PnPn-1P2P1时达到极小值。因此，对记录的查找概率不等的查找表若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列，以便提高查找效率。    然而，在一般情况下，记录的查找概率预先无法测定。为了提高查找效率，我们可以在每个记录中附设一个访问频度域，并使顺序表中的记录始终保持按访问频度非递减有序的次序排列，使得查找概率大的记录在查找过程中不断往后移，以便在以后的逐次查找中减少比较次数。或者在每次查找之后都将刚查找到的记录直接移至表尾。    顺序查找和我们后面将要讨论到的其它查找算法相比，其缺点是平均查找长度较大，特别是当n很大时，查找效率较低。然而，它有很大的优点是：算法简单且适应面广。    9.1.2 有序表的查找     以有序表表示静态查找表时，Search函数可用折半查找来实现。     折半查找(BinarySearch)的查找过程是：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。     例如：已知如下11个数据元素的有序表(关键字即为数据元素的值)：    现要查找关键字为21和85的数据元素。    假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即mid=(low+high)2。在此例中，low和high的初值分别为1和11，即1，11为待查范围。     先看给定值key=21的查找过程：        ST.elemmid.key与给定值key相比较，因为ST.elemmid.key>key，说明待查元素若存在，必在区间low，mid-1的范围内，则令指针high指向第mid-1个元素，重新求得mid=(1+5)2=3        仍以ST.elemmid.key和key相比，因为ST.elemmid.key<key，说明待查元素若存在，必在mid+1，high范围内，则令指针low指向第mid+1个元素，求得mid的新值为4，比较ST.elemmid.key和key，因为相等，则查找成功，所查元素在表中序号等于指针mid的值。    再看key=85的查找过程。        此时因为下界low>上界high，则说明表中没有关键字等于key的元素，查找不成功。    折半查找算法如下：    int Search_Bin(SSTable ST，KeyType key)    /在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。    low=1; high=ST.lenqth； /置区间初值    while (low<=high)        mid = (low+high)/2        if EQ(key, ST.elemmid.key) return mid; /找到待查元素        else if LT(key, ST.elem.mid.key) high = mid - 1; /继续在前半区间进行查找              else low = mid + 1; /继续在后半区间进行查找            return 0; /顺序表中不存在待查元素     /Search_Bin    折半查找的性能分析:    先看上述11个元素的表的具体例子。 从上述查找过程可知：找到第个元素仅需比较1次；找到第和第个元素需比较2次；找到第、和个元素需比较3次；找到第、需比较4次。这个查找过程可用图9.2所示的二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树，从判定树上可见，查找21的过程恰好是走了一条从根到结点的路径，和给定值进行比较的关键字个数为该路径上的结点数或结点在判定树上的层次数。 图9.2 描述查找过程的判定树    折半查找的平均查找长度是多少呢?     为讨论方便起见，假定有序表的长度，n=2k-1(反之，k=log2(n+1)，则描述折半查找的判定树是深度为k的满二叉树。树中层次为1的结点有1个，层次为2的结点有 2个，层次为k的结点有2k-1个。假设表中每个记录的查找概率相等(Pi=1/n)，则查找成功时折半查找的平均查找长度     对任意的n，当n较大(n>50)时，可有下列近似结果 ASL=log2(n+1)-1 (96)     可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构(对线性链表无法进行折半查找)。以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有斐波那契查找和插值查找。    9.1.3 静态树表的查找     上一小节对有序表的查找性能的讨论是在“等概率”的前提下进行的，即当有序表中各记录的查找概率相等时，按图9.2所示判定树描述的查找过程来进行折半查找，其性能最优。如果有序表中各记录的查找概率不等，情况又如何呢?     先看一个具体例子。假设有序表中含5个记录，并且已知各记录的查找概率不等，分别为p1=0.1，p2=0.2，p3=0.1，p4=0.4和p5=0.2。则按式(9-1)的定义，对此有序表进行折半查找，查找成功时的平均查找长度为：      5    PiCi = 0.1* 2+0.2* 3+0.1*1+0.4* 2+0.2* 3 = 2.3    i=1    但是，如果在查找时令给定值先和第4个记录的关键字进行比较，比较不相等时再继续在左子序列或右子序列中进行折半查找，则查找成功时的平均查找长度为：     5    PiCi=0.1* 3+0.2* 2+0.1* 3+0.4*1+0.2* 2=1.8     i=1    这就说明，当有序表中各记录的查找概率不等时，按图9.2所示判定树进行折半查找，其性能未必是优的。那末此时应如何进行查找呢?换句话说，描述查找过程的判定树为何类二叉树时，其查找性能最佳? 如果只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和PH值       n    PH=wihi (9-7)        i=1取最小值的二叉树。其中：n为二叉树上结点的个数(即有序表的长度)；hi为第i个结点在二叉树上的层次数；结点的权wi=cpi(i=1，2，n)，其中pi为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。由于构造静态最优查找树花费的时间代价较高，因此在此介绍一种构造近似最优查找树的有效算法。已知一个按关键字有序的记录序列 (rl, rl+1, , rh) (9-8)     其中 rl.key<rl+1.key<<rh.key    与每个记录相应的权值为 wl, wl+1, , wh (9-9)     现构造一棵二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树(Nearly Optimal Search Tree)。    构造次优查找树的方法是：首先在式(98)所示的记录序列中取第i(lih)个记录构造根结点ri，使得              h    i-1     Pi=|wj-wj| (9-10)          j=i+1 j=l    取最小值(Pi=MinPj)，然后分别对子序列rl, rl+1,ri-1和ri+1,.,rh 两棵次优查找树，并分别设为根结点ri的左子树和右子树。     由于在构造次优查找树的过程中，没有考察单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与它相邻的关键字的权值小。此时应作适当调整：选取邻近的权值较大的关键字作次优查找树的根结点。    大量的实验研究表明，次优查找树和最优查找树的查找性能之差仅为12，很少超过3，而且构造次优查找树的算法的时间复杂度为O (nlogn)，因此它是构造近似最优二叉查找树的有效算法。    9.1.4 索引顺序表的查找    若以索引顺序表表示静态查找表，则Search函数可用分块查找来实现。 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建守一个“索引表” 。例如，图8.6所示为一个表及其索引表，表中含有18个记录，可分成三个子表(Rl，R2，R6)、(R7，R8，R12)、(Rl3，Rl4，R18)，对每个子表(或称块)建立一个索引项， 图9.6     其中包括两项内容：关键字项(其值为该子表内的最大关键字)和指针项(指示该子表的第一个记录在表中位置)。索引表按关键字有序，则表或者有序或者分块有序。    所谓“分块有序”指的是第i个子表中所有记录的关键字均大于第i-1个子表中的最大关键字。    因此，分块查找过程需分两步进行。先确定待查记录所在的块(子表)，然后在块中顺序查找。假设给定值key=38，则先将key依次和索引表中各最大关键字进行比较，因为 22<key<48，则关键字为38的记录若存在，必定在第二个子表中，由于同一索引项中的指针指示第二个子表中的第一个记录是表中第7个记录，则自第7个记录起进行顺序查找，直到ST.elem10.key=key为止。假如此子表中没有关键字等于key的记录(例如： key=29时自第7个记录起至第12个记录的关键字和key比较都不等)，则查找不成功。    由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找的算法即为这两种查找算法的简单合成。     分块查找的平均查找长度为 ASLbs=Lb+Lw (9-14)，其中：Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的平均查找长度。    一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含有s个记录，即b=ceil(n/s) ；又假定表中每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。若用顺序查找确定所在块，此时的平均查找长度不仅和表长n有关，而且和每一块中的记录个数s有关。在给定n的前提下，s是可以选择的。容易证明，ASL比顺序查找有了很大改进，但远不及折半查找。若用折半查找确定所在块，则分块查找的平均查找长度可以得到提高。9.2 动态查找表（2学时）    我们将讨论动态查找表的表示和实现。动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于 key的记录，则查找成功返回，否则插入关键字等于key的记录。以下是动态查找表的定义。    抽象数据类型动态查找表的定义如下：     ADT DynamicSearchTable     数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。    数据关系R：数据元素同属一个集合。     基本操作P：      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(&DT，key)；        初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。        操作结果：若DT中存在其关键字等于key的数据元素，则删除之。      TraverseDSTable(DT，Visit()；        初始条件：动态查找表DT存在，Visit是对结点操作的应用函数。        操作结果：按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦visit()败，则操作失败。     ADT DynamicSearchTable    9.2.1 二叉排序树和平衡二叉树    一、二叉排序树及其查找过程    什么是二叉排序树?    二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。    二叉排序树又称二叉查找树，根据上述定义的结构特点可见，它的查找过程和次优二叉树类似。即当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。     通常，可取二叉链表作为二叉排序树的存储结构，则上述查找过程如算法 9.5(a)所描述。 BiTree SearchBST (BiTree T，KeyType key) /在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针    if( (!T)|EQ(key，T>data.key)      return (T)； /查找结束    else if LT(key，T>data.key)          return(SearchBST(T>lchild，key)； /在左子树中继续查找          else           return(SearchBST(T >rchild，key)；/ 在右子树中继续查找/SearchBST    算法 95(a)图9.7 二叉排序树示例     例如：在图9.7所示的二叉排序树中查找关键字等于100的记录（树中结点内的数均为记录的关键字）。首先以 key=100和根结点的关键字比较，因为key>45，则查找以45为根的右子树，此时右子树不空，且key>53，则继续查找以53为根的右子树，由于key和53的右子树根的关键字100相等，则查找成功，返回指向结点100的指针值。    二、二叉排序树的插入和删除    和次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此，需将上一小节的二叉排序树的查找算法改写成算法9.5(b)，以便能在查找不成功时返回插入位置。插入算法如算法9.6所示。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 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)；/在右子树中继续查找/SearchBST算法 9.5(b) Status Insert BST(BiTree &T，ElemType e)/当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE，否则返回FALSE    if(!SearchBST(T，e.key，NULL，p) /查找不成功        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为左孩子                else p>rchild=s /被插结点*s为右孩子        return TRUE；            else return FALSE; /树中已有关键字相同的结点，不再插入/ Insert BST算法 9.6    若从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为45，24，53，45，12，24，9，则生成的二叉排序树如图9.8所示。 图9.8 二义排序树的构造过程     容易看出，中序遍历二叉排序树可得到一个关键字的有序序列(这个性质是由二叉排序树的定义决定的)。这就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。不仅如此，从上面的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其它记录。它表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。    同样，在二叉排序树上删去一个结点也很方便。删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。    那末，如何在二叉排序树上删去一个结点呢?    假设在二叉排序树上被删结点为*p(指向结点的指针为p)，其双亲结点为*f(结点指针为f)，且不失一般性，可设*p是*f的左孩子。    下面分三种情况进行讨论：    (1)若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。    (2)若*p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。    (3)若*p结点的左子树和右子树均不空。显然，此时不能如上简单处理。从图9.9 (b)可知，在删去*p结点之前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，在删去*p之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图9.9(c)所示；其二是令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。如图9.9(d)所示，当以直接前驱*s替代*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。 图9.9 在二叉排序树中删除*p(a)*f为根的子树；(b)删除*p之前；(c)删除*p之后，PR作为*s右子树的情形；(d)删除*p之后，*s替代的情形     三、二叉排序树的查找分析    在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1(或结点所在层次数)，因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。例如：图9.10中(a)和(b)的两棵二叉排序树中结点的值都相同，但前者由关键字序列(45，24，53，12，37，93)构成，而后者由关键字序列(12，24，37，45，53，93)构成。(a)树的深度为3，而(b)树的深度为6。    因此，含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉树蜕变为单枝树。树的深度为n，其平均查找长度和顺序查找相同，这是最差的情况。显然，最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。    四、平衡二叉树     平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的有子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。如图9.11(a)为两棵平衡二叉树，而图9.11(b)为两棵不平衡的二叉树，结点中的值为该结点的平衡因子。 图9.11 平衡与不平衡的二叉树及结点的平衡因子     我们希望由任何初始序列构成的二叉排序树都是AVL树。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(其中N为结点个数)。由此，它的平均查找长度也和logN同数量级。    如何使构成的二叉排序树成为平衡树呢?先看一个具体例子(参见图9.12)。假设表中关键字序列为(13，24，37，90，53)。 图8.12    一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小根结点的指针为a(即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为下列四种情况：    (1)单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。     (2)单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作。     (3)双向旋转(先左后右)平衡处理：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需进行两次旋转 (先左旋后右旋)操作。     (4)双向旋转(先右后左)子衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。     上述四种情况中，(1)和(3)对称，(2)和(4)对称。旋转操作的正确性容易由“保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序”证明之。无论哪一种情况，在经过平衡旋转处理之后，以*b或*c为根的新子树为平衡二叉树，而且它的深度和插入之前以*a为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。     在平衡二叉树上插入一个新的元素的递归算法描述及实现见课本P235238。    9.2.2 B-树和B+树     一、B-树及其查找    B-树是一种平衡的多路查找树，它在文件系统中很有用。在此先介绍这种树的结构及其查找算法。