数据结构查找.ppt

《数据结构查找.ppt》由会员分享，可在线阅读，更多相关《数据结构查找.ppt（77页珍藏版）》请在沃文网上搜索。

1、1第第8章章 查找查找l1、查找表、查找表也叫检索也叫检索，是由同一类型的数据元素（或记，是由同一类型的数据元素（或记录）构成的集合。由于录）构成的集合。由于“集合集合”中的数据元素之间存在完全中的数据元素之间存在完全松散的关系，因此查找表是一种非常灵便的数据结构。松散的关系，因此查找表是一种非常灵便的数据结构。l2、查找表的操作、查找表的操作l查找某个查找某个“特定特定”的数据元素是否在查找表中；的数据元素是否在查找表中；l检索某个检索某个“特定特定”的数据元素的各种属性；的数据元素的各种属性；l在查找表中插入一个数据元素；在查找表中插入一个数据元素；l从查找表中删除某个数据元素。从查找表中

2、删除某个数据元素。2l3、静态查找表、动态查找表、静态查找表、动态查找表l若对查找表只作前两种统称为若对查找表只作前两种统称为“查找查找”的操作，则此的操作，则此类查找为类查找为静态查找表静态查找表。l若在查找过程中同时插入查找表中不存在的数据元素，若在查找过程中同时插入查找表中不存在的数据元素，或从查找表中删除已存在的某个数据元素，则称此类表或从查找表中删除已存在的某个数据元素，则称此类表为为动态查找表。动态查找表。l4、关键字、次关键字、关键字、次关键字l关键字：关键字：是数据元素（或记录）中某个数据项的值，用是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）

3、。若此关它可以标识（识别）一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字键字可以唯一地标识一个记录，则称此关键字为主关键为主关键字字。反之，则称此关键字为。反之，则称此关键字为次关键字次关键字。第第8章章 查找查找3l5、查找、查找l根据给定的某个值，在查找表中确定一个其关键字等于给定根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。值的记录或数据元素。若表中存在这样的一个记录，则称查若表中存在这样的一个记录，则称查找是成功的找是成功的，此时查找的结果为给出整个记录的信息，或指，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；示该

4、记录在查找表中的位置；l6、查找方法评价、查找方法评价l查找速度、占用存储空间多少、算法本身复杂程度查找速度、占用存储空间多少、算法本身复杂程度l平均查找长度平均查找长度ASL(Average Search Length)：为确定记录在为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值表中的位置，需和给定值进行比较的关键字的个数的期望值叫叫查找算法的查找算法的平均查找长度。平均查找长度。l若表中不存在关键字等于给定值的记录若表中不存在关键字等于给定值的记录，则称查找不成功。，则称查找不成功。此时查找的结果可给出一个此时查找的结果可给出一个“空空”记录或记录或“空空”指针。指针。第

5、第8章章 查找查找4i例例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii比较次数比较次数=5l比较次数：比较次数：l查找第查找第n个元素：个元素：1l查找第查找第n-1个元素：个元素：28.1 静态查找表静态查找表l一、顺序表的查找（顺序查找）一、顺序表的查找（顺序查找）l1、顺序查找、顺序查找 从表中最后一个记录开始，逐个进行记录的关键从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成

6、功，找到所查找记录；反之，若直至第一个记录，其则查找成功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。不成功。l查找第查找第1个元素：个元素：nl查找第查找第i个元素：个元素：n+1-il查找失败查找失败：n+152、查找操作的性能分析、查找操作的性能分析l对于含有对于含有n个记录的表，查找成功时的平均查找长度为：个记录的表，查找成功时的平均查找长度为：l其中其中:n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，且个记录的概率，且 ，Ci为找到该记录时，曾和给定值

7、比较过的关键字的个数。为找到该记录时，曾和给定值比较过的关键字的个数。l从顺序查找的过程可见，从顺序查找的过程可见，Ci取决于所查找记录在表中的位置。取决于所查找记录在表中的位置。查找表中最后一个记录是，仅需比较一次，而查找表中第一查找表中最后一个记录是，仅需比较一次，而查找表中第一个记录时，则需比较个记录时，则需比较n次。一般情况下次。一般情况下Ci等于等于n-i+1。6ASL=nP1+(n-1)P2+2Pn-1+Pnl从上式可知，在不等概率查找的情况下，从上式可知，在不等概率查找的情况下，ASLss 在在 PnPn-1P2P1时取极小值。时取极小值。l应对记录的查找概率进行排序，使表中记录

8、按查找概率由应对记录的查找概率进行排序，使表中记录按查找概率由小到大重新排列，以便提高查找效率。小到大重新排列，以便提高查找效率。l查找概率无法事先测定，则查找过程采取的改进办法是，查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。置上。7l顺序查找的缺点是顺序查找的缺点是平均查找长度较大平均查找长度较大，特别是当，特别是当n很大时，很大时，查找效率低。然而，它有很大的优点是：查找效率低。然而，它有很大的优点是：算法简单且适应算法简单且适应面广。面广。l当查找不成功时的情形不忽视时，查找算

9、法的平均查找长当查找不成功时的情形不忽视时，查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。查找长度之和。l对于顺序查找，不论给定值对于顺序查找，不论给定值key为何值，查找不成功时和为何值，查找不成功时和给定值进行比较的关键字个数均为给定值进行比较的关键字个数均为n+1。假设查找成功与假设查找成功与不成功的可能性相同不成功的可能性相同，对每个记录的查找概率也相等，则，对每个记录的查找概率也相等，则 ，此时顺序查找的平均查找长度为：，此时顺序查找的平均查找长度为：一、顺序表的查找（顺序查找）一、顺序表的查找（

10、顺序查找）8l1、折半查找、折半查找 折半查找的查找过程是：先确定待查记录折半查找的查找过程是：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。每次将待查记录所在区间缩小一半。该记录为止。每次将待查记录所在区间缩小一半。二、有序表的查找（折半查找）二、有序表的查找（折半查找）l算法实现：假设表长为算法实现：假设表长为n，low、high和和mid分别指向待查元分别指向待查元素所在区间的上界、下界和中点素所在区间的上界、下界和中点,k为给定值，初始时，令为给定值，初始时，令low=1,high=n,mid=(low

11、+high)/2 l让让k与与mid指向的记录比较指向的记录比较l若若k=rmid.key，查找成功查找成功l若若krmid.key，则则low=mid+1l重复上述操作，直至重复上述操作，直至lowhigh时，时，查找失败查找失败。9lowhighmid例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 8

12、0 88 92lowhighmidCh7_2.c例如：已知如下例如：已知如下11个数据元素的有序表（个数据元素的有序表（05，13，19，21，37，56，64，75，80，88，92），现要查找关键字），现要查找关键字为为21和和70 的数据元素。的数据元素。1、折半查找、折半查找10例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10

13、115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh112、折半查找的性能分析、折半查找的性能分析l先先看看上述上述11个元素的表的具体例子。每一个的比较次数。个元素的表的具体例子。每一个的比较次数。l这个查找过程可用图这个查找过程可用图8.1所示的二叉所示的二叉树来描述。树中每个结点表示表中树来描述。树中每个结

14、点表示表中一个记录，结点中的值为该记录在一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找表中的位置，通常称这个描述查找过程的过程的二叉树为判定树。二叉树为判定树。81121074193651 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92l从判定树上可见，查从判定树上可见，查21的过程恰好是走了一条从根到结点的过程恰好是走了一条从根到结点（4）的路径，）的路径，和给定值进行比较的关键字个数为该路径上的和给定值进行比较的关键字个数为该路径上的结点数或结点结点数或结点4在判定树上的层次数。在判定树上的层次数。12l二分法查找在查

15、找成功时进行比较的关键字个数最多不超过二分法查找在查找成功时进行比较的关键字个数最多不超过树的深度，而具有树的深度，而具有n个结点的判定树的深度为个结点的判定树的深度为 log2n+1。所。所以折半查找法在查找成功时和给定值进行比较的关键字个数以折半查找法在查找成功时和给定值进行比较的关键字个数至多为至多为 log2n+1l对于任意的对于任意的n，当，当n较大（较大（n50时），可有下列近似结果：时），可有下列近似结果：l可见，折半查找的效率比顺序查找高，但折半查找只适用于可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。有序表，且限于顺序存储结构。l树中层数为树

16、中层数为1的结点有的结点有1个，层数为个，层数为2的结点有的结点有2个，层数为个，层数为h的结点有的结点有2h-1个。假设表中每个记录的查找概率个。假设表中每个记录的查找概率 ，则查，则查找成功时折半查找的平均查找长度为：找成功时折半查找的平均查找长度为：131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表索引表查查38三、索引顺序表的查找（分块查找）三、索引顺序表的查找（分块查找）l若以索引顺序表表示静态查找表，则若以

17、索引顺序表表示静态查找表，则search函数可用分块函数可用分块查找来实现。查找来实现。分块查找又称索引顺序查找分块查找又称索引顺序查找，这是顺序查找的，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需要建立一种改进方法。在此查找法中，除表本身以外，尚需要建立一个一个“索引表索引表”。例如：下图所示为一个表及其索引表，表。例如：下图所示为一个表及其索引表，表中含有中含有18个记录，可分成三个子表（个记录，可分成三个子表（R1，R2，R6）、）、（R7，R8，R12）、（）、（R13，R14，R18）。）。14l分块查找方法分块查找方法 所谓所谓“分块有序分块有序”指的是第指的是第2

18、个子表中所有个子表中所有记录的关键字均大于第记录的关键字均大于第1子表中的最大关键字，第子表中的最大关键字，第3子表中子表中的所有关键字均大于第的所有关键字均大于第2字表中的最大关键字，依次类推，字表中的最大关键字，依次类推，分快查找过程需分两步进行。先确定待查记录所在的块分快查找过程需分两步进行。先确定待查记录所在的块（子表），然后在块中顺序查找。（子表），然后在块中顺序查找。l此时的平均查找长度不仅和表长有关，而且和每一块中此时的平均查找长度不仅和表长有关，而且和每一块中的记录个数的记录个数s有关。有关。l分块查找的平均长度为：分块查找的平均长度为：ASLbS=Lb+Lwl其中其中Lb为查

19、找索引表确定所在块的平均查找长度，为查找索引表确定所在块的平均查找长度，Lw为为在在块中查找元素的平均查找长度。块中查找元素的平均查找长度。三、索引顺序表的查找（分块查找）三、索引顺序表的查找（分块查找）15顺序查找顺序查找二分法查找二分法查找分块查找分块查找ASL最大最大最小最小两者之间两者之间表结构表结构有序表有序表无序表无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构顺序存储结构顺序存储结构线性链表线性链表查找方法的比较查找方法的比较168.2 动态查找表动态查找表l动态查找表的特点：动态查找表的特点：表结构本身是在查

20、找过程中动态地生成表结构本身是在查找过程中动态地生成的，即对于给定值的，即对于给定值key，若，若表中存在其关键字等于表中存在其关键字等于key的的记录，记录，则查找成功返回，否则插入关键字等于则查找成功返回，否则插入关键字等于key的记录。的记录。l一、二叉树排序树及其查找过程一、二叉树排序树及其查找过程l1、什么是二叉排序树？、什么是二叉排序树？l二叉排序树或是一棵空树；或是具有下列性质的二叉树：二叉排序树或是一棵空树；或是具有下列性质的二叉树：l（1）若它的左子树不空，则左子树上所有结点的值均小）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；于它的根结点的值；l（2）若它

21、的右子树不空，则右子树上所有结点的值均）若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；大于或等于它的根结点的值；l（3）它的左、右子树也分别为二叉排序树。）它的左、右子树也分别为二叉排序树。17一、二叉树排序树及其查找过程一、二叉树排序树及其查找过程l 2、查找过程、查找过程90782410061373531245l例如右图所示为二叉排序树。例如右图所示为二叉排序树。l若二叉排序树为空，则查找不成功；否则若二叉排序树为空，则查找不成功；否则l（1）若给定值等于根结点的关键字，则查找）若给定值等于根结点的关键字，则查找成功；成功；l（2）若给定值小于根结点的关键字，则继续在

22、左子）若给定值小于根结点的关键字，则继续在左子树上进行查找；树上进行查找；l（3）若给定值大于根结点的关键字，则继续在右子树上进）若给定值大于根结点的关键字，则继续在右子树上进行查找。行查找。18查找过程举例：查找过程举例：100、4090782410061373531245一、二叉树排序树及其查找过程一、二叉树排序树及其查找过程19二、二叉排序树的插入与删除二、二叉排序树的插入与删除l1、二叉排序树的插入、二叉排序树的插入l二叉排序树是一种动态树表。其特点是：树的结构通常不是二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，一次生成的，而是在查找过程中，当树中

23、不存在关键字等于当树中不存在关键字等于给定值的结点时再进行插入给定值的结点时再进行插入。新插入的结点一定是一个新添。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时，查找路径上访问的最加的叶子结点，并且是查找不成功时，查找路径上访问的最后一个结点的左孩子或右孩子结点。后一个结点的左孩子或右孩子结点。l举例：若从空树出发，经过一系列的查找插入操作之后，可举例：若从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为生成一棵二叉树。设查找的关键字序列为45，24，53，45，12，24，90，则生成的二叉排序树如图所示。二叉排序，则生成的二叉排序树如图所示。二叉

24、排序树生成：从空树出发，经过一系列的查找、插入操作之后，树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。可生成一棵二叉排序树。20l容易看出，中序遍历二叉树可得到容易看出，中序遍历二叉树可得到一个关键字的有序序列。这就是说，一个关键字的有序序列。这就是说，一个无序序列可以通过构造一棵二一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排造树的过程即为对无序序列进行排序的过程。序的过程。l从上面的插入过程还可以看到，每次插入的新的结点都是二叉从上面的插入过程还可以看到，每次插入的新的结点都是二叉排序树上

25、新的叶子结点，则在进行插入操作时，不必移动其它排序树上新的叶子结点，则在进行插入操作时，不必移动其它记录，仅需要改动某个结点的指针，由空变为非空即可。这就记录，仅需要改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其它记录。相当于在一个有序序列上插入一个记录而不需要移动其它记录。它表明，它表明，二叉排序树既拥有类似折半查找的特性，又采用了链二叉排序树既拥有类似折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。表作存储结构，因此是动态查找表的一种适宜表示。24455312901、二叉排序树的插入、二叉排序树的插入212、二叉排序树的删

26、除、二叉排序树的删除l对于一般的二叉树来说，删除树中一个结点是没有意义的。对于一般的二叉树来说，删除树中一个结点是没有意义的。然而，对于二叉排序树，删去树上一个结点相当于删去有然而，对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后，依旧保序序列中的一个记录，只要在删除某个结点之后，依旧保持二叉排序树的特性即可。持二叉排序树的特性即可。l（1）*P为叶子结点为叶子结点l那么，如何在二叉排序树上删去一个结点呢？假设在二叉那么，如何在二叉排序树上删去一个结点呢？假设在二叉排序树上被删结点为排序树上被删结点为*P，其双亲结点为其双亲结点为*F，且不失一般性，且不失

27、一般性，可设可设*P是是*F的左孩子。要删除二叉排序树中的的左孩子。要删除二叉排序树中的P结点，分结点，分三种情况：三种情况：l即即PL和和PR均为空树。由于删去叶子结点不破坏整棵树的均为空树。由于删去叶子结点不破坏整棵树的结构，则结构，则只需修改其只需修改其P双亲双亲F的指针的指针lF-lchild=NULL或或F-rchild=NULL。22SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1)l（2）*P只有左子树只有左子树PL或右子树或右子树PRl此时只要令

28、此时只要令PL或或PR直接成为其双亲结点直接成为其双亲结点*F的左子树即可，显的左子树即可，显然，作此修改也不破坏二叉树的特性。然，作此修改也不破坏二叉树的特性。23中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQPRPl（2）*P只有左子树只有左子树PL或右子树或右子树PR24l（3）*P左、右子树均非空左、右子树均非空FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL

29、 Q SL S PR F(5)l在删除在删除*P之前，中序遍历二叉树得到的序列为之前，中序遍历二叉树得到的序列为CLCQLQSLSPPRF，删除删除*P之后，为保持其它元之后，为保持其它元素之间的相对位置不变，可以有两种：其素之间的相对位置不变，可以有两种：其 一是令一是令*P的直的直接前驱（或直接后继）替代接前驱（或直接后继）替代*P，然后再从二叉排序树中删然后再从二叉排序树中删去它的直接前驱（或直接后继），如下图所示。去它的直接前驱（或直接后继），如下图所示。25l其二是令其二是令*P的左子树为的左子树为*F的左子树，而的左子树，而*P的右子树为的右子树为*S的右子树，如下图所示。的右子树

30、，如下图所示。FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)S26l删除算法例例805012060110150557053删除删除508060120110150557053删除删除60805512011015053701042581354删除删除1084255134删除删除58425413Ch5_10.c27 三、二叉排序树的查找分析三、二叉排序树的查找分析 l二分法查找长度为二分法查找长度为n的表的判定树是唯一的，而含有的表的判定树是唯一的，而含有n个结点个结点的二

31、叉排序树却不是唯一的。由关键字序列的二叉排序树却不是唯一的。由关键字序列45,24,53,12,37,93构造而得的二叉排序树构造而得的二叉排序树(a)，455393243712a241237455393blASL=（1+2+2+3+3+3）/6=14/6l由关键字序列由关键字序列12,24,37,45,53,93构造而得的二叉排序树构造而得的二叉排序树 lASL=（1+2+3+4+5+6）/6 =21/628l因此，因此，含有含有n个结点的二叉排序树的平均查找长度和树的形个结点的二叉排序树的平均查找长度和树的形态有关态有关。当先后插的关键字有序时，构成的二叉排序树蠕变。当先后插的关键字有序时

32、，构成的二叉排序树蠕变为单支树。树的深度为为单支树。树的深度为n，其，其平均查找长度为（平均查找长度为（n+1）/2，和顺序查找相同，这是最差的情况，显然，最好的情况是二和顺序查找相同，这是最差的情况，显然，最好的情况是二叉排序树的形态和二分法查找的判定树相同，其平均查找长叉排序树的形态和二分法查找的判定树相同，其平均查找长度和度和log2n成正比。那么，它的平均性能如何？成正比。那么，它的平均性能如何？l由此可见，在随机的情况下，二叉排序树的平均查找长度由此可见，在随机的情况下，二叉排序树的平均查找长度和和log n是等数量级的。然而，在某些情况下（有人研究是等数量级的。然而，在某些情况下（

33、有人研究证明，这种情况出现的概率约为证明，这种情况出现的概率约为46.5%）。尚需在构成二）。尚需在构成二叉排序树的过程中进行叉排序树的过程中进行“平衡化处理平衡化处理”，成为二叉平衡树。，成为二叉平衡树。三、二叉排序树的查找分析三、二叉排序树的查找分析 29四、平衡二叉树四、平衡二叉树l1、平衡二叉树、平衡二叉树l平衡二叉树，它或者是一棵空树，或者是具有下列性质的二平衡二叉树，它或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过和右子树高度之差的绝对值不超过1。l若将二叉

34、树上结点的平衡因子若将二叉树上结点的平衡因子BF(Balance Factor)定义为该定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是上所有结点的平衡因子只可能是-1，0，1。只要二叉树上有。只要二叉树上有一个结点的平衡因子的绝对值大于一个结点的平衡因子的绝对值大于1，则这棵树就不是平衡二，则这棵树就不是平衡二叉树。叉树。l平衡二叉树的优点：平衡二叉树的优点：它的平均查找长度和它的平均查找长度和logN同数量级。同数量级。301、平衡二叉树、平衡二叉树1100平衡二叉树平衡二叉树不平衡二叉树不平衡二叉

35、树0100-11-10100-120100-20-131l构造二叉平衡（查找）树的方法是：在插入过程中，采用平构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。衡旋转技术。l例如例如:依次插入的关键字为依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转2、如何使二叉排序树成为平衡二叉树、如何使二叉排序树成为平衡二叉树32426589426895向左旋转一次继续插入关键字继续插入关键字 933l二叉树的平衡处理调整的规律可归纳为下列四种情况二叉树的平衡处理调整的规律可归纳为下列四种情况1B2ABLhARh-1BRh-1插入结点0A0B

36、BLBRARLLl（1）单向右旋平衡处理）单向右旋平衡处理 由于在结点由于在结点*a的左子树根结点的的左子树根结点的左子树上插入结点，左子树上插入结点，*a的平衡因子由的平衡因子由1增加到增加到2，致使以，致使以*a为为根结点的子树失去平衡，则需要进行一次向右的顺时针旋转根结点的子树失去平衡，则需要进行一次向右的顺时针旋转操作，如图所示。操作，如图所示。l中序遍历：中序遍历：BL B BR A AR34l（2）单向左旋平衡处理）单向左旋平衡处理-1B-2ABRhALh-1插入结点RR0A0BALBLBRBLh-1l由于在由于在*a的右子树根结点的右子树上插入结点，的右子树根结点的右子树上插入结

37、点，*a的平衡因的平衡因子由子由-1变为变为-2，致使以，致使以*a为根结点的子树失去平衡，则需要为根结点的子树失去平衡，则需要进行一次向左的逆时针旋转操作，如图所示。进行一次向左的逆时针旋转操作，如图所示。l中序遍历：中序遍历：AL A BL B BR35l（3）双向旋转（先左后右）平衡处理）双向旋转（先左后右）平衡处理-1B2ACLh-1ARh-1h-1BL插入结点0B0CBLCLCRLRAR-1A1Ch-2CR中序遍历：B CL C CR A ARl由于在由于在*a的左子树根结点的右子树上插入结点，的左子树根结点的右子树上插入结点，*a的平衡因的平衡因子由子由1增加到增加到2，致使以，致

38、使以*a为根结点的子树失去平衡，则需要为根结点的子树失去平衡，则需要进行两次旋转（先左旋后右旋）操作，如图所示。进行两次旋转（先左旋后右旋）操作，如图所示。36l（4）双向旋转（先右后左）平衡处理）双向旋转（先右后左）平衡处理-1B-2ACLh-1h-1AL插入结点0A0CALCLCRRLBR-1B1CBRh-1CRh-2中序遍历：ALACLCCRBBRl由于在由于在*a的右子树根结点的左子树上插入结点，的右子树根结点的左子树上插入结点，*a的平衡因的平衡因子由子由-1增加到增加到-2，致使以，致使以*a为根结点的子树失去平衡，则需为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作

39、，如图所示。要进行两次旋转（先右旋后左旋）操作，如图所示。373、在平衡树的二叉排序树、在平衡树的二叉排序树BBS上插入一个新的数据元素上插入一个新的数据元素l（1）若）若BBST为空树，则插入一个数据元素为为空树，则插入一个数据元素为e的新结的新结点作为点作为BBST的根结点，树的深度加的根结点，树的深度加1；l（2）若）若e的的关键字和关键字和BBST的根结点的关键字相等时，的根结点的关键字相等时，则不进行插入；则不进行插入；l（3）若）若e的关键字小于的关键字小于BBST的根结点的关键字，而且的根结点的关键字，而且在在BBST的左子树中不存在和的左子树中不存在和e相同关键字的结点，则相同

40、关键字的结点，则插入在插入在BBST的左子树上，并且当插入之后的左子树深的左子树上，并且当插入之后的左子树深度增加（度增加（+1）时，分别就不同情况处理之。）时，分别就不同情况处理之。38l*BBST的根节点的平衡因子为的根节点的平衡因子为1（左子树的深度大于右子树的（左子树的深度大于右子树的深度）：深度）：l*BBST的根节点的平衡因子为的根节点的平衡因子为-1（右子树的深度大于左子树（右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为的深度）：则将根结点的平衡因子更改为 0，BBST的深的深度不变；度不变；l*BBST的根节点的平衡因子为的根节点的平衡因子为0（左、右子树的深度相等

41、）：（左、右子树的深度相等）：则将根结点的平衡因子更改为则将根结点的平衡因子更改为 1，BBST的深度加的深度加1；l若若BBST的左子树根结点的平衡因子为的左子树根结点的平衡因子为-1，则需进行先，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理向左、后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变。树的深度不变。l若若BBST的左子树根节点的平衡因子为的左子树根节点的平衡因子为1，则需要进行，则需要进行单向右旋平衡处理，并且在右旋处理之后，将根结点单向右旋平衡处理，并且在右旋处理之后

42、，将根结点和其右子树根结点的平衡因子更改为和其右子树根结点的平衡因子更改为0，树的深度不变，树的深度不变39l（4）若）若e的关键字大于的关键字大于BBST的根结点的关键字，而且在的根结点的关键字，而且在BBST的右子树中不存在和的右子树中不存在和e 有相同关键字的结点，则将有相同关键字的结点，则将e 插入在插入在BBST的右子树上，并且当插入之后的右子树深度增的右子树上，并且当插入之后的右子树深度增加（加（+1）时，分别就不同情况处理之。其处理操作和（）时，分别就不同情况处理之。其处理操作和（3）中所述相对称。中所述相对称。409.3 哈希表（散列表哈希表（散列表）9.3.1 基本概念基本概

43、念 1.散列散列 也称为杂凑或哈希。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为哈希表或散列表。散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散散列列查查找找是是通通过过计计算算哈哈希希函函数数来来得得到到待待查查关关键键字字的的地地址址，理论上讲，在哈希表中查找元素无须进行关键字间的比较。例如，要找关键字为k的元素，则只需求出函数值H(k)，H为给定的哈希函数，H(k)代表关键字k在存贮区中的地址。41 假假设设有有一一批批关关键键字字序序列列18,75,60,43,54,90,4618,

44、75,60,43,54,90,46，给给定定哈哈希希函函数数H(k)=k%13，存存贮贮区区的的内内存存地地址址从从0 0到到1515，则则可可以以得得到到每每个个关关键键字字的的散散列列地址为：地址为：H(18)=18%13=5 H(75)=75%13=10 H(60)=60%13=8 H(43)=43%13=4 H(54)=54%13=2 H(90)=90%13=12 H(46)=46%13=7 于于是是，根根据据散散列列地地址址，可可以以将将上上述述7 7个个关关键键字字序序列列存存贮贮到到一一个个一一维维数数组组HTHT（哈希表或散列表）中，具体表示为：哈希表或散列表）中，具体表示为：

45、HT012345678910 11 12 54 43 1846 60 75 90 13 14 15 例如例如429.3 哈希表（散列表哈希表（散列表）因此，一个散列结构是一块地址连续的存储空间，它与一个称为散列函数的函数相关联，该函数是数据记录的关键字到地址空间的映射。v这种存储空间的使用方式，使得这种存储空间的使用方式，使得(1)存储记录时，通过散列函数计算出记录的存储位置并按此存储位置存储记录 记录位置记录位置 Hash(Hash(记录的关键字记录的关键字)Hash：关键字关键字 地址地址(2)访问记录时，同样利用散列函数计算存储位置，然后根据所计算出的存储位置访问记录439.3 哈希表（

46、散列表哈希表（散列表）2.散列技术中的主要问题散列技术中的主要问题 表面上看，设置了散列函数后，只需作简单的函数计算就可以实现元素的定位及查找操作，但事实上没有这么简单，概括起来，主要有以下两个问题：(1)(1)冲突冲突 一般情况下，设计出的散列函数很难是单射的，即不同的关键字对应到同一个存储位置，这样就造成了冲突冲突(碰撞碰撞)。此时，发生冲突的关键字互为同义词。(2)(2)散列函数的设计散列函数的设计 设计一个简单、均匀、存储空间利用率高、冲突少的散列函数是关键。449.3 哈希表（散列表哈希表（散列表）3.散列过程散列过程 散列的一般使用方法是，首先根据具体问题的特点(数据集的特点、存储

47、空间的限制等)设计散列函数和解决冲突的方法，然后执行以下过程：(1)提取需要插入或访问的记录的关键字，用散列函数计算出存储位置addr。(2)如果是存储(插入)记录，且addr处已被其他记录占用(插入冲突)，则转(4)；否则将记录存入该位置，结束。(3)如果是访问(查找、删除、修改等)记录，则检查addr处的记录是否为要访问的记录，若不是(定位冲突)，则转(4)；否则读取该记录进行相应的处理，结束。459.3 哈希表（散列表哈希表（散列表）(1)提取需要插入或访问的记录的关键字，用散列函数计算出存储位置addr。(2)如果是存储(插入)记录，且addr处已被其他记录占用(插入冲突)，则转(4)

48、；否则将记录存入该位置，结束。(3)如果是访问(查找、删除、修改等)记录，则检查addr处的记录是否为要访问的记录，若不是(定位冲突)，则转(4)；否则读取该记录进行相应的处理，结束。(4)按既定的冲突处理策略处理冲突。若是插入冲突，则冲突处理是要找一个空闲位置以插入记录；若是定位冲突，则冲突处理是继续查找所要求的记录，确定记录是否在散列结构中，若是则返回该元素的位置信息，否则返回特殊标志。469.3 哈希表（散列表哈希表（散列表）9.3.2 散列函数的构造方法散列函数的构造方法 “好”的散列函数是指：对于关键字集合中的任意一个关键字，经散列函数映像到地址集合中任意一个地址的概率是相等的，称此

49、类散列函数为均匀的哈希函数。常用的散列函数构造方法有：1直接定址法直接定址法 可表示为H(key)=a*key+b，其中a、b均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，会将造成大量存贮单元的浪费。471、直接定址法、直接定址法地址地址01020325年龄年龄12325人数人数3000200050001050l例如：有一个从例如：有一个从1岁到岁到100岁的人口数字统计表，年龄作为岁的人口数字统计表，年龄作为关键字，哈希函数取关键字自身。关键字，哈希函数取关键字自身。48l又又如：有一个解放后出生的人口调查表，关键字是年如：有一个解放后出生的人

50、口调查表，关键字是年份，哈希函数取关键字加一常数：份，哈希函数取关键字加一常数：l h(key）=key+(-1948)地址地址010203.22年份年份1949195019511970人数人数15000l这样，若要查这样，若要查1970年出生的人数，则只要查（年出生的人数，则只要查（1970-1948）=22项即可。由于直接定址所得地址集合和关键项即可。由于直接定址所得地址集合和关键字集合的大小相同，因此不会发生冲突，字集合的大小相同，因此不会发生冲突，但实际中能使但实际中能使用这种哈希函数的情况很少。用这种哈希函数的情况很少。1、直接定址法、直接定址法499.3 哈希表（散列表哈希表（散列