《算法与数据结构》第7章 检索及基本算法ppt课件

1、算法与数据构造第7章 检索及根本算法第7章 检索及根本算法 7.1 检索的概念7.2 线性表的检索7.3 树表的检索7.4 哈希检索检索的概念 n检索searching也称作查找，是一种常用的根本运算。n人们几乎每天都要做检索的任务，如在号码薄中查找某单位或某个人的号码，在字典中查找某个词的含义或读法，在图书馆查找某本书刊的编号，上网在各种数据库中查找某些需求的文献资料等等。n在言语翻译的编译程序中要对符号表查找，在数据库系统中要用SQL言语为各种运用设计查找程序，如此等等。 检索的概念(续) n简言之，检索就是在“大量信息中查找一个“特定的信息。n这里的大量信息是检索所依赖的数据构造，称之为

2、检索表search table；n检索表是由同一类型的数据元素或记录组成的集合。n由于集合是一种松散型数据构造，数据元素除了同属于一个集合外再无别的关系，所以检索表是一种非常灵敏的数据构造。 检索的概念(续) n对检索表常做的运算和操作有：n 查找某个特定的数据元素能否在检索表中；n 检索某个特定的数据元素的各种属性；n 在检索表中插入一个数据元素；n 从检索表中删去某个数据元素。n假设对查找表只作前两种统称为“检索的操作，称此类检索表为静态检索表static search table；n假设在检索的过程中同时插入表中不存在的数据元素，或者从检索表中删除已存在的某个数据元素，称此类检索表为动态

3、检索表dynamic search table。 检索的概念(续) n 所谓特定的信息，是指关键字值等于给定值的信息，信息的单位是数据元素或记录。n 关键字key是数据元素或记录中某个数据项的值，用它可以标识一个数据元素或记录。显然，在一个记录中的每个数据项都可以作为标识该记录的关键字。如人事档案记录构造为：n 它含有五个关键字，其中性别这个关键字标识了一个职工的性别情况。检索的概念(续) n主关键字primary key是指能独一标识一个数据元素或记录的关键字。如上述记录中身份证号码是主关键字，可以独一标识一条记录；而姓名、性别、年龄、工资级别不能独一标识一条记录，它们都不是主关键字。n辅关

4、键字secondary key是用以标识假设干数据元素或记录的关键字，也称作次关键字或从关键字。如上述记录中的姓名、性别、年龄、工资级别都是辅关键字。检索的概念(续) n检索，就是根据给定的某个值，在检索表中查找一个关键字等于给定值的记录的运算或操作。n假设在检索表中存在这样的记录，那么称检索胜利，检索的结果是找到记录的全部信息或找到记录在检索表中的位置；n假设检索表中不存在关键字值等于给定值的记录，那么称检索失败，给出在检索表中无要查找的记录的信息提示，并在动态检索时插入关键字等于给定值的记录于检索表中。检索的概念(续) n 在检索表中查找某个数据元表或记录的过程，依赖于这个数据元表或记录在

5、查找表中所处的位置；对检索表的检索方法取决于检索表中数据元表或记录的组织战略。n如在字典中查找一个英文单词，由于字典是按字母顺序编排的，所以不需从第一个单词顺序查找，而只是按待查单词中每个字母在字母表中的位置快速找到该单词；n而在数据元素或记录之间无任何关系组织起来的集合中查找，那么需求从第一个元素或记录开场依次顺序查找。检索的概念(续) n 在计算机中进展检索是对已存入计算机中的数据进展检索，取决于采用何种数据构造来组织检索表；往往需求在数据元素或记录之间人为地加上一些关系，即用非集合构造如数组、文件、二叉树、散列表等构造来组织检索表，以便按某种规律来进展检索。n依数据组织方式不同，检索分为

6、线性表检索、树表检索和散列表检索等。n 衡量一个检索算法的优劣，主要根据在检索过程中给定值和关键字的比较操作次数。为此，我们引入平均检索长度的概念。平均检索长度n检索算法的平均检索长度average search length，即在检索过程中用给定值和关键字进展比较的平均比较次数，n或者说是为找到具有给定值关键字的记录所需求的比较次数的平均值。n它是为确定记录在检索表中的位置，需求和给定值进展比较的关键字个数的期望值。平均检索长度续n 对于含有n个记录的检索表，检索胜利时的平均检索长度为 n其中，Pi为检索第i个记录的概率，且 ；普通在不特殊阐明的情况下均以为是等概率，即检索每个记录的概率相等

7、， 。nCi为找到第i个记录需求和给定值比较的关键字的个数，它随检索方法的不同而不同。 第7章 检索及根本算法 7.1 检索的概念7.2 线性表的检索7.3 树表的检索7.4 哈希检索线性表的检索n 在检索表的数据组织方式中，线性表是最根本的，也是最常用的一种组织方式。本节主要讨论在顺序存储构造实现的线性表上的检索算法，其类型定义描画为n typedef structn keytype key; /*关键字类型*/n elemtype other; /*其它域*/n sqlist;n sqlist Rn+1; /*顺序表*/n本节引见的线性表检索方法有顺序检索、二分法检索、黄金点检索、精算点检

8、索和分块检索等。7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索顺序检索n 顺序检索sequential search是一种最简单的根本检索方法。n其根本思绪为：n从表的一端开场，用给定值逐个与表中各记录的关键字值比较。n假设找到某个关键字值等于给定值的记录，那么检索胜利，并给出该记录在表中的位置；n假设检索完好个表仍未找到关键字值等于给定值的记录，那么检索失败，并给出失败信息。n 顺序检索方法既适用于线性表的顺序存储构造，也适用于线性表的链式存储构造。顺序检索举例n以顺序存储构造为例，设数据元素存放在数组中下标

9、从1到n的记录中，0号记录位置留作监视哨，从下标为n的一端开场向另一端检索，顺序检索算法可描画如下：nint seqsearch(sqlist R,keytype k) n int i=n;n R0.key=k; /*设置R0为监视哨*/n while(Ri.key != k)n i-;n return i; /*前往检索结果i*/n 顺序检索举例续n 算法中设置监视哨R0，可以使得在检索胜利和检索失败时的处置一致，在检索失败时也能在监视哨位置找到关键字值为k的记录，可省去在while循环中的位置越界检查i=1。n假设从R0处向后顺序检索，监视哨可设置在Rn处。n算法执行之后，非0的函数值表示

10、待查找记录在数组中的位置下标；假设函数值为0阐明检索表中没有要查找的记录。顺序检索续n对于具有n个记录的检索表，假设待查找记录在Rn处，需求和给定值k比较一次，即Cn=1；n假设待查找记录在Rn-1处，需求和给定值k比较两次，即Cn-1=2；n普通地，假设待查找记录在Ri处，需和给定值k比较n-i+1次，即Ci=n-i+1。n因此，在等概率的情况下顺序检索的平均检索长度为顺序检索续n在检索胜利时顺序检索的平均比较次数约为表长的一半。n在检索失败时，顺序检索需求进展n+1次的比较。n当n很大时，平均检索长度也很大，检索效率较低，这是顺序检索的主要缺陷。n但由于顺序检索对表的存储构造和元素存放次序

11、没有要求，且算法简单，在许多实践运用中常被采用。 7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索二分法检索n二分法检索binary search，也称作折半检索，它是一种效率较高的检索方法。它要求检索表是用顺序存储构造表示，且数据元素的存放要按关键字值有序陈列。n二分法检索的根本思想是：n在有序表中先取中间位置作为比较对象，假设给定值与中间记录的关键字值相等，那么检索胜利；n假设给定值小于中间记录的关键值那么在表的左半区查找，n假设给定值大于中间记录的关键字值那么在表的右半区查找。n就这样经过一次的比较减少一半

12、的检索区间，在每一个检索区间都是选取中间位置作为比较对象，不断地反复这样的检索过程直到检索胜利，或者检索区间已无记录时检索失败。二分法检索举例n例如：知一个含15个记录的有序表，其关键字序列如下：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n如今要检索给定值k为19、46和11的记录，其检索过程如下：n用low和high分别表示检索区间的下界和上界；n用mid指示中间位置，即mid=(low +high)/2；n检索开场时low=1，high=n；即检索区间为1，n。二分法检索举例检索k=18n检索k=18的过程：n 07 10 14 18 21

13、23 25 29 31 35 38 42 46 49 52n nlow=1 mid=8 high=15n检索开场时，low=1，high=15，mid=(1+15)/2=8。由于k=1829=R8.key，所以应在右半区继续检索；此时low=mid+1=8+1=9，mid= (9+15)/2=12，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=9 mid=12 high=15n由于k=4642=R14.key，所以应在当前区间的右半区继续检索； 二分法检索举例检索k=46(续)n此时low=12+1 =13，mid=(13+15)

14、/2=14，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=13mid=14high=15n由于k=4649=R14.key，所以应在当前区间的左半区继续检索；此时high=mid-1= 14-1=13，mid=(13+13)/2=13，即：n07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=13n mid=13n high=13 n由于k=46=R13.key，此时检索46胜利。二分法检索举例检索k=11n检索k=11的过程：n 07 10 14 18 21 23 25 29

15、31 35 38 42 46 49 52n nlow=1 mid=8 high=15n由于k=1129=R8.key，应在左半区继续检索；此时high= mid-1=8-1=7，mid= (1+7)/2=4，即：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=1 mid=4 high=7n由于k=1110=R2.key，应在当前区间的右半区继续检索；此时low=2+1=3，mid= (3+3)/2=3，即：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=3n mid=3n h

16、igh=3n由于k=1114=R3.key，应在当前区间的左半区继续检索；此时high=mid-1= 3-1=23=low，左半区已没有元素不存在区间了，检索k11失败。 二分法检索过程可用C言语描画 n二分法检索过程可用C言语描画为如下算法：n int binarysearch (sglist R,keytype k)n int low,mid,high;n low=1; high=n;n while(low=high)n mid=(low+high)/2;n if(k=Rmid.key)n return mid;n else n if(k100，那么可有如下近似结果： 二分法检索过程分析续

17、 n由此可见，二分法检索的效率比顺序检索高得多，如n=127时，顺序检索ASL64而二分法那么为ASL6。n二分法检索只适用于检索表为顺序存储构造之下的有序表，即这种较高的检索效率是以对检索表预先按关键字值大小排序为代价的，所以二分法检索适宜于一旦建立很少变动而又需求经常检索的检索表。 7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索黄金分割点检索n黄金分割点检索gold-partition search，简称黄金点检索。它是利用我国著名数学家华罗庚院士当年推行优选法时引见的黄金分割点的概念，即利用黄金分割数0.

18、618把检索区间分为两个不等的区间。n每次用给定值与黄金点上的记录的关键字比较，假设相等检索胜利，假设给定值小于黄金点关键字值，继续在黄金点之前的区间检索；假设给定值大于黄金点关键字值，继续在黄金点之后的区间检索。n经过黄金点逐次减少检索区间，直到检索胜利，或区间已无记录检索失败时止。 黄金分割点检索举例n 例如，仍以前面的15个记录为例，检索k46的黄金分割点检索过程为：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=1 mid=9 high=15n开场时low=1，high=15，mid=low+0.618*(high-low+1

19、)-1=1+0.618*(15-1+1)-1=9.329。给定值k=4631=R9.key，在黄金点之后的区间继续检索。此时low=9+1=10，mid=10+0.618*(15-10+1)-1=12.70813。即：n 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52n n low=10 mid=13 high=15n 由于k=46=R13.key 检索胜利。一个用二分法检索需4次比较的任务，黄金分割点检索只需两次比较就完成了。黄金分割点检索算法描画 int goldpartsearch(sqlist R,keytype k) int low,mid,

20、high; low=1; high=n; while(low=high) /*逐次减少区间检索*/ mid=low+0.618*(high-low+1)-1+0.5; if(k=Rmid.key) return mid; else if(kRmid.key) high=mid-1; /*修正区间上界*/ else low=mid+1; /*修正区间下界*/ return 0;黄金分割点检索续n 该算法的时间性能与二分法相比，在平均性能上优于二分法，但依然是；在最坏情况下，每次比较之后都在较大的区间内继续检索，比二分法差；在最好情况下，每次比较之后都在小区间内继续检索，比二分法好。n 所谓黄金分

21、割点，就是利用Fibonacci数列对检索表分割得到的一系列位置。Fibonacci数列的定义为： 黄金分割点检索续n留意察看“Fibonacci数列及其相邻项的比值表中给出的F(n)/F(n+1)的值，从n=6之后根本上稳定在0.618处。n因此，我们可以对长度为F(n)的检索表，第一次用F(n-1)处记录的关键字同给定值比较；由F(n-1)分割的两个区间的长度分别为F(n-2)-1和F(n-3)，又都可以利用Fibonacci数列找出新的分割点；如此不断进展下去，就可获得检索胜利或失败的结果。n然而，检索表的长度很难是某个Fibonacci数列或接近Fibonacci数的值；其次即就是Fi

22、bonacci数，也还得为Fibonacci检索预备一张Fibonacci数表或经过循环递推求出每次要用的Fibonacci数，所以说利用Fibonacci数列设计检索算法不如直接运用黄金分割数0.618设计检索算法方便。 7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索精算点检索n对于有序的检索表，假设记录的关键字值不仅有序，而且分布均匀或比较均匀，我们能不能很快地完成关键字值等于给定值记录的检索义务呢？回答是一定的，下面将要引见的精算点检索就可以处理这个问题。n所谓精算点检索precise computing

23、 search，也称作插值检索。它是利用检索区间有序关键字值范围和给定值的大小比例关系估算检索位置的一种检索方法。 精算点检索续n当关键字值分布均匀时应满足下式：n其中k为给定值，mid为估算位置，low和high分别为检索区间下界和上界位置，经整理可得估算公式为： n当给定值k等于Rmid.key那么检索胜利；否那么假设kRmid.key那么在mid之后检索。 精算点检索续n在关键字值均匀分布时，如呈等差数列时一次比较便可检索胜利；在关键字值分布比较均匀时，假设一次比较不能找到也会在mid位置附近，这两种情况的检索长度与检索表的大小n无关，所以称之为精算点检索。n假设关键字值分布不均匀，可减

24、少检索区间继续用前面的估算公式确定检索点检索，其检索性能也优于黄金分割点检索和二分法检索。精算点检索举例n例如，对于前述的15个记录的检索表，检索k=14的记录，low=1，high=15， ，R3.key=14等于给定值，一次比较检索胜利；又如检索k=29时， ，一次比较Rn.key=29等于给定值检索胜利；再如检索k=46时 ， ， 一 次 比 较R13.key=46等于给定值检索胜利；等等。 精算点检索举例续n既然在关键字值分布较均匀时，即使一次比较不能检索胜利也会在mid位置附近，在算法设计时就只需一次计算mid的值。n假设k=Rmid.key，那么一次比较检索胜利；n假设kRmid.

25、key，那么可由mid后一个记录开场向后顺序检索，直到检索胜利或某个记录的关键字值大于给定值k时检索失败。 精算点检索算法描画 n这种与顺序检索相结合的精算点检索算法可描画如下：n int precisesearch(sqlist R,keytype k)n int low,mid,high;n low=1; high=n;n mid=low+(k-Rlow.key)*(high-low)/n (Rhigh.key-Rlow.key)+0.5;n if(k=Rmid.key)n return mid; n elsen if(kk)n mid-; 精算点检索算法描画续 if(Rmid.key=k

26、) return mid; /*检索胜利前往位置*/ else return 0; /*检索失败前往0*/ else mid+; /*假设给定值大于mid时在mid后检索*/ while(Rmid.keyk) /*向后顺序检索*/ mid+; if(Rmid.key=k) return mid; /*检索胜利前往位置*/ else return 0; /*检索失败前往0*/ 精算点检索算法分析n该算法中的两个当型循环，在关键字值分布较均匀的情况下，检索长度与检索表的长度n无关，平均检索长度趋近于某个常数；n在关键字值分布不均匀的情况下，检索长度在最坏的情况下也不会超越二分法检索和黄金分割点检索

27、；n精算点检索是平均性能最好的检索方法，对于检索表较大和分布较均匀时，运用精算点检索特别适宜。7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索精算点检索算法分析n 分块检索blocking search，又称作索引检索，它是顺序检索的一种改良方法，其效率介于顺序检索和二分法检索之间。n 分块检索不要求检索表中一切记录关键值有序陈列，但要求把检索表分成假设干块之后各块之间按关键字值大小有序。n即分块检索要求检索表的特点是：块间有序，块内无序。n所谓块间有序是指块间升序或块间降序。n在块间升序时，每一块中一切记录的关

28、键字值均大于和该块相邻的前一块中最大的关键字值；n在块间降序时，每一块中一切记录的关键字值均小于和该块相邻的前一块中最小的关键字值。精算点检索算法分析续n 在分块检索中，除检索表本身之外，还需求建立一张索引表。如以下图给出了一张块间升序的检索表的索引表，每个块在索引表中有一个索引项，每个索引项中包含有该块中最大的关键字值和该块第一个记录在检索表中的位置。n本例中检索表分为三块，各块中最大关键字值依次为22、48和86，各块中第一个记录在检索表中的位置依次为1、7和13；第二块中的最小关键字值24大于第一块中的最大关键字值22，第三块中的最小关键字值49大于第二块中的最大关键字值48。精算点检索

29、算法分析续n以下图中给出了一张块间降序的检索表的索引表，每个块在索引表中也是一个索引项，但索引项中包含的是块中最小的关键字值和该块第一个记录在检索表中的位置。n该例中检索表分为四块，各块中最小关键字值依次为47、32、22和9，各块中第一个记录在检索表中的位置依次是1、6、11和16；第二块中的最大关键字值45小于第一块中最小的关键字值47，第三块中的最大关键字值31小于第二块中的最小关键字值32，第四块中的最大关键字值20小于第三块中最小的关键字值22。 精算点检索的根本思想n分块检索的根本思想是：n首先根据给定值在索引表中检索，以确定待查找记录所属的块；n由于索引表是有序表，所以可以用二分

30、法检索，也可以用顺序检索或其它检索方法进展。n然后在确定的块内检索关键字值等于给定值的记录，由于块内记录无序陈列，所以只能用顺序检索方法进展。精算点检索举例n例如，要在前例“块间升序的检索表及其索引表例如中检索k=38的记录：n先将k依次和索引表中各个最大关键字进展比较，由于22k48，所以k=38的记录假设存在必在第二个块中；n然后从第二个块的起始地址开场顺序检索，直到R10.key=k时检索胜利。n再如检索k=76的记录：n将k和索引表中各个最大关键字值比较，由于48k50那么在右子树中继续检索；再用80和右子树的根70比较，8070那么继续在当前根结点70的右子树中检索；当再次和新的当前

31、根结点比较时二者相等检索胜利，前往指向当前根结点的指针。n又如检索k=15的记录时，由于15小于根结点50，在其左子树继续检索；15又小于左子树的根结点40，继续在当前根结点40的左子树中检索；15也小于当前根结点40的左子树的根结点20，当在20的左子树中继续检索时发现20的左子树为空，检索失败前往NULL。 二叉检索树的二叉链表类型n 设二叉检索树以如下描画的二叉链表作为存储构造：n typedef struct noden keytype key; /*关键字域*/n elemtype other; /*其它数据域*/n struct node *lchild, *rchild;n /*

32、左右孩子指针域*/n bstnode; /*定义结点类型bstnode*/n typedef bstnode *bstlist; n /*定义二叉检索树表类型bstlist*/二叉检索树的检索算法描画 n 二叉检索树的检索算法可描画如下：n bstlist bstsearch(bstlist t,keytype k)n bstlist p ; n p=t; n if(p=NULL)|(p-key=k)n return p; n elsen if(p-keyrchild,k);n elsen return bstsearch(p-lchild,k);n /*bstsearch end*/2.二叉

33、检索树的构造过程和插入操作 n对于一组关键字无序的记录，构造其相应的二叉检索树的方法是：从一棵空的二叉检索树开场，每当读入一个记录就生成一个结点，然后按关键字值的大小插入到当前的二叉检索树之中；当一切记录的结点都已插入二叉检索树中时便构造终了。n虽然，插入操作是构造二叉检索树的关键操作。要保证在一棵二叉检索树中插入一个结点之后，依然满足二叉检索树的定义。其插入过程为：n假设二叉检索树为空，那么插入结点作为新的根结点；n假设二叉检索树非空，那么在非空的二叉检索树中检索插入结点；假设检索胜利就不用插入，否那么插入结点作为新的叶结点，并成为检索途径上最后一个结点的左孩子或右孩子。 二叉检索树的构造过

34、程和插入操作(续)n为了实现这一插入过程，在二叉检索树非空时需求知道检索途径上的最后一个结点位置，才可以准确地把插入结点作为左孩子或右孩子插入二叉检索树中；为此；需求在检索过程中设一指针变量记下当前结点的前趋即双亲结点位置。n插入算法的方式化描画如下：n bstlist insertbst(bstlist t,keytype k)n bstlist s,p,q; n if(t=NULLl)n p=(bstlist)malloc(sigeof(bstnode);n p-key=k; p-lchild=NULL; p-rchild=NULL;n p-other=data; n return p;

35、二叉检索树的构造过程和插入操作(续) p=t; while(p!=NULL) q=p; if(p-key=k) /*检索胜利不用插入*/ return t; /*前往原二叉检索树*/ else if(p-keyrchild; else p=p-lchild; p=(bstlist)malloc(sizeof(bstnode); 二叉检索树的构造过程和插入操作(续) p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; if(kq-key) q-rchild=p; else q-lchild=p; return t; 二叉检索(排序)树构造过程

36、举例 n从空树出发经过一系列的检索插入操作之后，就可生成一棵二叉检索树。一个无序序列可以经过构造一棵二叉检索树而变成一个有序序列即中序遍历次序序列，构造的过程就是对无序序列进展排序的过程，所以又称作二叉排序树。n设关键字序列为45，22，57，18，29，92，生成二叉检索树即二叉排序树的过程如以下图所示。 3.二叉树检索树的删除操作 n在二叉检索树中删除一个结点，相当于在检索表中删除一个记录，不能把以待删除结点为根结点的子树全部删去，并且要保证删除某个结点后的二叉树依然是一棵二叉检索树。下面，我们分三种情况讨论如何在二叉检索树中删除一个结点。n 待删除结点是度为0的叶子结点n 删除一个叶子结

37、点*p，不破坏整棵树的构造，只需将其双亲结点*f与*p之间相链接的指针域置为空即可：n f-lchild=NULL; 或 f-rchild=NULL;二叉树检索树的删除操作续 待删除结点是度为1的单枝结点 即待删除结点只需左子树或只需右子树的情况，如以下图所示。此时只需将待删除结点*p的独一后继结点左孩子或右孩子直接链接到其双亲结点*f的相应位置即左链域或右链域上即可： (a) f-lchild=p-lchild; 或 (b) f-lchild=p-rchild; 或 (c) f-rchild=p-lchild; 或 (d) f-rchild=p-rchild;二叉树检索树的删除操作续 待删除

38、结点是度为2的双枝结点 即待删除结点既有左子树又有右子树的情况， 如以下图所示，为了坚持二叉检索树的特性，通常有如下四种做法。 二叉树检索树的删除操作方法一 n方法一：找出待删除结点*p的中序前趋结点*q，把*q的关键字域和数据域的值赋给*p的相应域，即：n p-key=q-key; p-other=q-other;n然后删除其中序前趋结点*q，由于*p的中序前趋*q是*p左子树上的最右下结点，所以*q必是叶子结点或单左枝结点，如以下图所示；其删除方法见和。 二叉树检索树的删除操作方法二 n方法二：找出待删除结点*p的中序后继结点*q，把*q的关键字域和数据域的值赋给*p的相应域，即：n p-

39、key=q-key; p-other=q-other;n然后删除其中序后继结点*q。由于*p的中序后继*q是*p右子树上的最左下结点，所以*q必是叶子结点或单右枝结点，如以下图所示；其删除方法见和。 二叉树检索树的删除操作方法三 n方法三：将待删除结点*p的右子树链接到它的中序前趋结点即左子树上的最右下结点*q的右孩子域上，然后把它的左子树直接链接到其双亲结点*f的左或右孩子域上。即：n q-rchild=p-rchild; n f-lchild或f-rchild=p-lchild; 二叉树检索树的删除操作方法四 n 方法四：将删除结点*p的左子树链接到它的中序后继即右子树上的最左下结点*q的

40、左孩子域上，然后把它的右子树直接链接到其双亲结点*f的左或右孩子域上。即：n q-lchild=p-lchild; n f-lchild或f-rchild=p-rchild;二叉树检索树的删除操作续n前两种方法是以删除待删除结点*p的中序前趋或中序后继*q来实现删除结点*p之目的，不需求知道待删除结点的双亲结点位置；n后两种方法是直接删除待删除结点*p，不仅需求知道其中序前趋或中序后继*q的位置，还需求在检索待删除结点*p的同时记住其双亲结点的位置。二叉树检索树的删除操作续n 方法一和方法三中*p的中序前趋*q即左子树中的最右下结点可以如下确定：n q=p-lchild;n while(q-r

41、child!=NULL)n q=q-rchild;n而方法二和方法四中*p的中序后继*q即右子树中的最左下结点确实定方法为：n q=p-rchild;n while(q-lchild!=NULL)n q=q-lchild;二叉检索树的删除算法描画 n下面我们给出采用方法四删除双枝结点时的二叉检索树的删除算法描画如下：n bstlist deletebst(bstlist t,keytype k)n bstlist p,q,r,f;n p=t; n f=NULL;n while(p!=NULL)&(k!=p-key) n f=p;n if(kkey)n p=p-lchild;n else

42、n p=p-rchild;n 二叉检索树的删除算法描画续 if(p=NULL) break; /*检索失败时不用删除中断执行*/ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待删除的*p为叶子结点或单枝结点时*/ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild;二叉检索树的删除算法描画续 if(p!=q) q-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f

43、-rchild=r; return t; /*前往删除操作后的二叉检索树*/ /*deletebst end*/4.二叉检索树的检索性能分析n在二叉检索树上检索关键字值等于给定值k的记录，正好是走了一条从根结点到关键字值为k的结点的途径，和给定值k的比较次数为途径长度加1或结点所在层次数，和二分法检索类似，其比较次数不超越树的深度。n然而，用二分法检索一个长度为n的检索表其检索过程的二叉树表示是独一的，而含有n个结点的二叉检索树却不独一。 二叉检索树的检索性能分析举例n例如，如以下图给出了结点值都一样的两棵二叉检索树，由于构造时的关键字序列不同，前者深度为3，而后者深度为7；在等概率的情况下，

44、前者的平均检索长度为ASL=(1+2+2+3+3+3+3)/7=17/7，后者的平均检索长度为ASL=(1+2+3+4+5+6+7)/7= 28/7=4。 二叉检索树的检索性能分析续n 因此，含有n个结点的二叉检索树的平均检索长度和二叉检索树的形状有关，领先后插入的关键字按值有序时，构造的二叉检索树蜕变为单枝树；n升序时为单右枝二叉树，降序时为单左枝二叉树；n树的深度为n，平均检索长度为(n+1)/2和顺序检索一样，这是最差的情况。最好的情况是二叉检索树的形状和二分法检索过程得到的树一样，树的高度和 完 全 二 叉 树 的 高 度 一 样 ， 其 平 均 检 索 长 度为 。二叉检索树的检索性

45、能分析续n如今我们思索在普通情况下二叉检索树的平均检索长度，假设在含有n个结点的二叉树中，有i个结点关键字值小于根结点的关键字值，n-i-1个结点关键字值大于根结点的关键字值。n在等概率检索的情况下平均检索长度为：n其中，p(i)为含有i个结点的二叉检索树的平均检索长度；p(i)+1为检索左子树中每个结点所用比较次数的平均值，p(n-i-1)+1为检索右子树中每个结点所用比较次数的平均值。 二叉检索树的检索性能分析续n由于根结点的左子树中有0个，1个，n-1个结点的情况是等概率的，对上式取平均值得：n用数学归纳法可以证明， ，即二叉检索树的平均长度为 。7.3 树表的检索7.3.1 二叉检索树

46、7.3.2 二叉检索树的平衡性调整7.3.3 B树和B+树平衡因子n平衡因子balance factorn二叉树上任一结点的平衡因子，定义为该结点的左子树深度减去右子树深度的差。n如以下图中给出了一些二叉树，其结点上所示数值为该结点的平衡因子值。平衡二叉树n平衡二叉树balance binary treen假设一棵二叉树中一切结点的平衡因子的绝对值不超越1，那么称该二叉树为平衡二叉树；平衡二叉树也称作AVL树。n显然，AVL树要么是一棵空树，要么其左右子树深度不超越1且都是AVL树；只需二叉树上有一个结点的平衡因子的绝对值大于1，该二叉树就是不平衡的。如前例图中，(a)和(b)都是平衡二叉树即

47、AVL树，而(c)和(d)都不是平衡二叉树即非AVL树。 平衡二叉树续n由于AVL树具有良好的形状，其左右子树的深度差不超越1；对于给定的结点数目n，AVL树的平均深度接近于完全二叉树的深度 ；n所以我们希望由任何初始序列构成的二叉检索树都是AVL树，使得其平均检索长度接近于 。 n如何使构造的二叉树成为AVL树呢？Adelson-Velskii和Landis提供了一个动态地坚持二叉检索树平衡性的方法；n其根本思想是在构造二叉检索树的过程中，每当插入一个结点后都去检查能否由于该结点的插入而破坏了二叉检索树的平衡性；假设出现绝对值超越1的平衡因子，那么需求在坚持二叉检索树特性的前提下经过调整使之

48、到达新的平衡。 平衡二叉树续n在普通情况下，设在插入结点的过程中使二叉检索树失去平衡的最小子树的根结点为a，即a为离插入结点最近且平衡因子绝对值超越1的祖先结点；n因插入结点的位置不同而失去平衡需求调整的规律可归纳为如下四种情况：nLL型平衡旋转右单旋型 nRR型平衡旋转左单旋型 nLR型平衡旋转先左后右双旋型 nRL型平衡旋转先右后左双旋型 1.LL型平衡旋转右单旋型n这种失衡是由于在结点a的左孩子b的左子树上插入结点，使结点a的平衡因子由1增至2而呵斥的。n其调整战略是以a的左孩子b为轴心顺时针旋转即向右旋转一次；使结点a成为其左孩子b的右孩子，而b的右子树成为a的左子树，如以下图所示。这

49、种调整战略既使结点的平衡因子满足AVL树的要求，又坚持了二叉检索树的特性即中序遍历次序为上升序列。 2.RR型平衡旋转左单旋型n这种失衡是由于在结点a的右孩子b的左子树上插入结点，使a的平衡因子由-1变成-2而呵斥的；n其调整战略是以a的右孩子b 为轴心逆时针旋转即向左旋转一次；使a成为b的左孩子，而b的左子树成为a的右子树，如以下图所示。 3. LR型平衡旋转先左后右双旋型 n这种失衡是由于在结点a的左孩子b的右子树上插入结点，使a的平衡因子由1增至2呵斥的。n设c是b的右孩子，插入结点的位置有三种能够性：nc就是插入结点，这是由于插入前b为叶子结点且a无右孩子而产生的一种能够；n插入结点在

50、c的左子树上；n插入结点在c的右子树上。 LR型平衡旋转续 n对这三种导致LR型失衡的情况，其调整战略是一致的：n即以a的左孩子b的右孩子c为轴心，先逆时针即向左旋转一次，再顺时针即向右旋转一次；使c的左子树成为b的右子树，c的右子树成a的左子树，b成为c的左孩子而a成为c的右孩子，以“插入在c的左子树上为例，两次旋转的调整过程如以下图所示。 4. RL型平衡旋转先右后左双旋型 n这种失衡是由于在结点a的右孩子b的左子树上插入结点，使a的平衡因子由-1变成-2呵斥的，设c是b的左孩子，插入结点位置的三种能够性如以下图所示：RL型平衡旋转续 n对这三种导致RL型失衡的情况，其调整战略为：n以a的

51、右孩子b的左孩子c为轴心，先顺时针即向右旋转一次，再逆时针即向左旋转一次；使c的左子树成为a的右子树，c的右子树成为b的左子树，a成为c的左孩子而b成为c的右孩子。以“插入在c的左子树上为例，两次旋转的调整过程如以下图所示：构造平衡二叉检索树举例 n例如，对于一组记录其关键字序列为18，5，10，15，12，11，20，要建立一棵平衡的二叉检索树，其构造过程如以下图所示： 构外型平二叉检索树的算法n 在设计构造平衡的二叉检索树的算法时，需求先为每个结点添加一个平衡因子域，然后在二叉检索树构造算法的根底上做几点修正：n 插入一个结点后，要修正树中各结点平衡因子的值；n 判别能否因插入结点产生失衡

52、，在失衡时找到失衡的最小子树；n 判别失衡类型并做相应的调整处置。n在平衡的二叉检索树上进展检索的过程，和在二叉检索树上的检索过程一致，在检索过程中和给定值比较的次数不会超越树的深度，而含有n个结点的平衡二叉检索树的最大深度为 ，n 其中 。7.3 树表的检索7.3.1 二叉检索树7.3.2 二叉检索树的平衡性调整7.3.3 B树和B+树B树n B树是一种平衡的多路检索树，是文件系统包括大型数据库文件系统中的一种重要的数据组织构造。n 一棵m阶B树，或者为空树，或者为满足以下特性的m叉树：n 树中每个结点至多有m棵子树即至多有m-1个关键字；n 除非根结点为叶子结点，否那么至少有两棵子树即至少

53、有一个关键字；n 除根结点之外的一切非终端结点至少有棵子树；B树续 一切的非终端结点中包含以下信息： n，A0，k1，A1，k2，kn，An 其中： nnm-1为关键字的个数，即子树个数为n+1； ki1in为关键字，且kiki+11in； Ai0in为指向其子树的根结点的指针，且Ai0in所指子树中一切结点的关键字值都小于ki+1，An所指子树中一切结点的关键字值都大于kn； 一切叶子结点在同一个层次上，且不含有任何信息可以看作是外部结点或检索失败的结点；实践上这些结点不存在，指向这些结点的指针为NULL。B树示全例n以下图给出了一棵4阶 B树的例如： B树的插入操作n在B树上插入一个关键字

54、，不是象在二叉检索树中那样添加一个叶子结点，而是在B树的最底层的某个非终端结点中添加一个关键字。n假设该结点中关键字的个数小于m-1个那么插入完成；否那么添加后关键字个数由m-1个变为m个与B树定义不符，需求进展结点的“分裂以满足B树定义。n结点的分裂方法为，把中间一个关键字拿出来插入到该结点的双亲结点上，前后两部分各自构成一个结点；双亲结点中也能够有m个关键字，就需求继续分裂结点，直到插入到某个关键字个数小于m-1的祖先结点。n由这种分裂过程可见，B树是由底向上生长的。 B树的插入操作举例nB树的插入过程如以下图所示，图中只画出了非终端结点，省去了最底层的叶子结点。 B树的删除操作n 在B树

55、上删除一个关键字和插入关键字类似也是由底向上的调整过程，n先找到该关键字所在的结点并删除这个关键字。n假设找到的结点是最底层的非终端结点，当关键字个数大于那么删除完成，否那么删除后关键字个数由个变为个与B树定义不符，需求进展结点的“合并以满足B树定义。n合并的方法是把删除了关键字的结点同其左兄弟结点或右兄弟结点合并，连同它们的双亲结点中的相关关键字项一块合并重新分配，在其双亲结点不满足B树定义时继续向上调整直到根结点。n假设找到的待删除关键字所在结点不是底层非终端结点，那么是将该关键字用其B树中的后继替代，而删除其后继的信息。B树的删除操作举例nB树的删除过程如以下图所示： B树的检索操作n在

56、B树中进展检索的过程是：n首先在根结点中所包含的关键字中检索给定的关键字，假设找到那么检索胜利，否那么确定待检索关键字所在的子树，并在该子树中继续检索，直到检索胜利或指针为空时检索失败。n例如，在前例中的一棵4阶B树中检索关键字值为61的记录，因根结点中不存在此关键字，那么到大于39的子树中检索；又由于子树的根结点中没有此关键字，而506180，故再到s所指子树中检索，在这个结点中含有61的关键字值那么检索胜利。n又如在此4阶B树中检索关键字值为75的记录，也是沿前面的这一条道路检索，由于s所指结点中没有值为75的关键字而检索失败。 B树的检索操作续n B树的检索是在B 树上找结点和在结点中找

57、关键字两个根本操作的交叉进展过程，待查关键字所在结点在B树中的层次是决议B树检索效率的首要要素，最坏的情况下是含n个关键字的m阶B树的最大深度。n由B树定义，第一层至少有1个结点，第二层至少有2个结点；由于除根结点外的每个非终端结点至少有n 棵子树，那么第三层至少有2 个结点；依此类推，第h+1层至少有 个结点；而h+1层为叶子结点。假设m阶B树有n个关键字，那么叶子结点即查找不胜利的结点数为n+1，由此有 B+树 nB+树是运用于文件系统中的B树的一种变形树，它与B树的差别主要在于：n 有n棵子树的结点中含有n个关键字；n 一切叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点

58、以关键字递增顺序链接；n 一切的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大或最小关键字。B+树举例 n如以下图给出了一棵3阶B+树。n通常B+树上有两个指针，一个指向根结点，一个指向关键字值最小的叶子结点。n因此，对于B+树既可从根结点开场多级索引顺序检索，又可以从最小关键字开场顺序检索。 B+树的操作 n在B+树上进展插入、删除和检索的过程与B树根本类似。n在检索过程中在非终端结点上找到给定值后并不终止，而是继续向下直到叶子结点；因此无论是检索胜利还是检索失败，每次检索都是走了一条从根结点到叶子结点的途径。nB+树的插入仅在叶子结点上进展，当叶子结点中关键字个数大于m时也要分裂

59、成两个结点，并且其双亲结点中同时也包含这两个结点的关键字最大值。nB+树的删除也在叶子结点中进展，其在非终端结点中的值可以作为分界关键字存在；当然在删除后假设使结点中关键个数小于 时也要进展结点的合并操作。 第7章 检索及根本算法 7.1 检索的概念7.2 线性表的检索7.3 树表的检索7.4 哈希检索哈希检索 n在前两节引见的线性表检索和树表检索方法后，由于记录在检索表中的位置是随机的或按关键字值大小次序陈列的，记录的存储位置和其关键字值之间不存在某种确定的关系，存储位置依赖于关键字的初始随机序列或在检索表中其它关键字值的大小。n所以在检索时需求进展一系列的关键字值与给定值之间的比较，其检索

60、效率和检索过程中进展的比较次数有关。n本节引见一种直接利用关键字值计算记录在检索表中的存储位置来进展检索的方法哈希Hash检索技术。 7.4 哈希检索7.4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法7.4.3 地址冲突的消解战略7.4.4 哈希表的检索算法及性能分析哈希检索与哈希表 n哈希检索技术的初衷是组织理想形状的检索表。n检索表的理想形状是：把记录的关键字值与记录在检索表中的存储位置建立起某种一对一的关系，这种一对一的关系可以用关于关键字的一个函数h(key)来表示，这样就可以不用进展关键字与给定值的比较，而是直接根据给定的关键字值来直接计算得到记录在检索表中的存储地址。 哈希检索与