第九章 查找-2.ppt

《第九章 查找-2.ppt》由会员分享，可在线阅读，更多相关《第九章 查找-2.ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、平衡二叉树平衡二叉树起因：提高查找速度，避免最坏情况出现。如右图情况的出现起因：提高查找速度，避免最坏情况出现。如右图情况的出现DABCFEGGEDBACF平衡二叉树平衡二叉树平衡因子（平衡度）：平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。结点的平衡度是结点的左子树的高度右子树的高度。平衡二叉树：平衡二叉树：每个结点的平衡因子都为每个结点的平衡因子都为 1、1、0 的二叉树。的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。141253928635360501718730+1+1-1-1-100000000是平衡树是

2、平衡树不是平衡树不是平衡树145392863536050171830+1+2-1-100000+1-1平衡二叉树平衡二叉树 平衡树的平衡树的 Adelson 算法的本质特点：算法的本质特点：以插入为例：以插入为例：在左图所示的平衡树中插入数据为在左图所示的平衡树中插入数据为 2 的结点。的结点。插入之后仍应保持平衡分类二叉树的性质不变。插入之后仍应保持平衡分类二叉树的性质不变。平衡树平衡树如何用最简单、最有效的办法如何用最简单、最有效的办法保持平衡分类二叉树的性质不保持平衡分类二叉树的性质不变？变？平衡二叉树平衡二叉树141253928635360501718730+1+1-1-1-10000

3、0000141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点解决方案：解决方案：不不涉及到危机结点的父结点，涉及到危机结点的父结点，即以危机结点为根的子树的高即以危机结点为根的子树的高度应保持不变（左图为度应保持不变（左图为 3）新新结点插入后，找到第一个平结点插入后，找到第一个平衡度不为衡度不为 0 的结点（如左图结的结点（如左图结点点9）即可。新插入的结点和第）即可。新插入的结点和第一个平衡度不为一个平衡度不为 0 的结点（也的结点（也可能是危机结点）之间的结点可能是危机结点）之间的结点在在调整中，仅调整

4、那些在平衡调整中，仅调整那些在平衡度变化的路径上的结点（如：度变化的路径上的结点（如：3 5 9），其它结点不予调整。），其它结点不予调整。仍仍应保持分类二叉树的性质不应保持分类二叉树的性质不变。变。平衡二叉树平衡二叉树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点23597122359712平衡二叉树平衡二叉树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点关键：将导致出现危机结点的情况全部分析，关键：将导致出现

5、危机结点的情况全部分析，就可以使得平衡分类二叉树的性质保持不变就可以使得平衡分类二叉树的性质保持不变14932528635360501718730+1+1-1-1-100000001200平衡二叉树平衡二叉树 左改组（新插入结点出现在危机结点的左子树上进行的调整）的左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：情况分析：1、LL 情况：（情况：（LL：表示新插入结点在危机结点的左表示新插入结点在危机结点的左子树的左子树上）子树的左子树上）AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高

6、度为 h+1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h+1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB平衡二叉树平衡二叉树LR,LL,RL,RR 书书p235 左改组（新插入结点出现在危机结点的左子树上进行的调整）的左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：情况分析：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的表示新插入结点在危机结点的左子树的右子树上）左子树的右子树上）情况情况A：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点改组前：改组前：高度为高度为 h+1

7、 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改组后：改组后：高度为高度为 h+1 中序序列：中序序列：ABBLARCCLCRA 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析：2、LR 情况：（情况：（LR：表示新插入结点在危机结点的左子树的右子树上）表示新插入结点在危机结点的左子树的右子树上）情况情况B：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点

8、危机结点改组前：改组前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL改组后：改组后：高度为高度为 h+1 中序序列：中序序列：AABBLARCCRCL为什么采用为什么采用B_ 树和树和 B+树：树：大量数据存放在外存中，通常存放在硬盘中。由于是海量大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次访问外存。但数据，不可能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。

9、所以，主要矛盾硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。变为减少访外次数。在在 1970 年由年由 R bayer 和和 E macreight 提出用提出用B_ 树作为树作为索引组织文件。提高访问速度、减少时间。索引组织文件。提高访问速度、减少时间。B_ 树和树和 B+树树502510751535609020304055708095索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上文件访问示意图：索引文件、数据文件存在盘上B_ 树和树和 B+树树B_ B_ 树是一种多分支数，首先介绍树是一种多分支数，首先介

10、绍 m m 阶阶 B_ B_ 树：树：定义：定义：m m 阶阶 B_ B_ 树满足或空，或：树满足或空，或：A A、根结点要么是叶子，要么至少有两个儿子根结点要么是叶子，要么至少有两个儿子B B、除根结点和叶子结点之外，每个结点的儿子个数除根结点和叶子结点之外，每个结点的儿子个数 为为:m/2=s=mm/2=s=mB_ 树和树和 B+树树定义参照书定义参照书p238C、有有 s 个儿子的非叶结点具有个儿子的非叶结点具有 n=s 1 个关键字，即个关键字，即:s=n+1 这些结点的数据信息为：这些结点的数据信息为：（n,A0,K1,R1,A1,K2,R2,A2,Kn,Rn,An）这里：这里：n：

11、关键字的个数关键字的个数A0：K1 且且 Kn 的结点的地址（指在该的结点的地址（指在该 B_ 树中）树中）注意：注意：K1=K2=.=KnD、所有的叶子结点都出现在同一层上，不带信息（可认为所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。外部结点或失败结点）。B_ 树和树和 B+树树m=4 阶阶 B_ 树。树。除根结点和叶子结点之外，每个结点的儿除根结点和叶子结点之外，每个结点的儿子个数至少为子个数至少为 m/2=2 个；结点的关键字个数至少为个；结点的关键字个数至少为 1。该。该 B_ 树的深度为树的深度为 4。叶子结点都在第。叶子结点都在第 4 层上。层上。1，99

12、3，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)B_ 树和树和 B+树树查找过程，类似于二叉树的查找。如查找关键字为查找过程，类似于二叉树的查找。如查找关键字为 Key Key 的记的记录。录。从根开始查找，如果从根开始查找，如果 KiKi=Key =Key 则查找成功，则查找成功，RiRi 关键字为关键字为 Key Key 的记录的地址。的记录的地址。若若 KiKi Key Ki+1;Key Ki+1;查找查找 Ai Ai 指向的结点指向的结点若若 Key K1;K

13、ey Key KnKn;查找查找 AnAn指向的结点指向的结点若找到叶子，则查找失败。若找到叶子，则查找失败。注意：每次查找将去掉注意：每次查找将去掉 （s-1s-1）/s/s 个分支，比二分查找快得个分支，比二分查找快得多。多。B_ 树的查找代价分析：树的查找代价分析：设关键字的总数为设关键字的总数为 N，求求 m阶阶 B_ 树的最大层次树的最大层次 L。公式公式：Llog m/2（N+1）/2）+1设设 N 1000，000 且且 m256，则则 L m-1,则该结点满。必须分裂成两个结点。则该结点满。必须分裂成两个结点。否则不满否则不满，结束。结束。如结点原为：如结点原为：（m-1,A0

14、,(K1,A1),(K2,A2),(Km-1,Am-1)）插入一个关键字之后变为：插入一个关键字之后变为：（m,A0,(K1,A1),(K2,A2),(Km,Am)）该结点将进行分裂：该结点将进行分裂：.(K m/2 ,p).（m/2-1,A0,(K1,A1),(K m/2 ,A m/2 )）（）（m-m/2,A m/2 ,(Km,Am)）生成新结点生成新结点 p,将原结点的后半部分复制过去。若分裂一直进行到根结点，将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。树可能长高一层。B_ 树的插入操作树的插入操作例如：例如：3 阶阶 B_ 树的插入操作。树的插入操作。m=3,m

15、/2 -1=1;至少至少 1 个关键字，二个关键字，二个儿子结点。个儿子结点。3，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入插入B_ 树和树和 B+树树插入方法见插入方法见p241-2431、查找具有给定键值的关键字、查找具有给定键值的关键字 Ki 2、如果在如果在第第 L 层，层，且关键字不少于且关键字不少于m/2可直接删除（注意：可直接删除（注意：第第 L+1 层为叶子结层为叶子结

16、 点），转点），转 4。3、否则，则首先生成、否则，则首先生成“替身替身”。用右子树中的最左面的结。用右子树中的最左面的结 点的关键字值，即处于第点的关键字值，即处于第 L 层上的最小关键字值取代。层上的最小关键字值取代。然后，删除第然后，删除第 L 层上的该关键字。层上的该关键字。B_ 树的删除操作树的删除操作4、从第、从第 L 层开始进行删除。层开始进行删除。A、不动：若删除关键字值的那个结点的关键字的个数仍不动：若删除关键字值的那个结点的关键字的个数仍处于处于m/2-1和和 m-1之间。则结束。之间。则结束。B、借：若删除关键字值的那个结点的关键字的个数原为借：若删除关键字值的那个结点的

17、关键字的个数原为m/2-1。而它们的左或右邻居结点的关键字的个数而它们的左或右邻居结点的关键字的个数 m/2-1;则借一个关键字过来。处理结束。则借一个关键字过来。处理结束。C、并：若该结点的左或右邻居结点的关键字的个数为并：若该结点的左或右邻居结点的关键字的个数为m/2-1;则执行合并结点的操作。则执行合并结点的操作。B_ 树的删除操作树的删除操作参见参见p244-245第第 L 层：找到了被删结点的替身。层：找到了被删结点的替身。B_ 树的删除操作树的删除操作（.(Ki,Ai),(Ki+1,Ai+1),.）（A0,(K1,A1)）（A0,(K1,A1)）K1L 例如：例如：3 阶阶 B_

18、树的删除操作。树的删除操作。m=3,m/2 -1=1;至少至少 1 个关个关键字，二个儿子结点。键字，二个儿子结点。3244553 90371005061，70被删关键字被删关键字3244561 90371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445 903710061，70假定再删除该关键假定再删除该关键字字3，2445 9010061，703，24 45 9010061，70并并并并并并并：和父结点的一个关键字、及邻居合并。有并：和父结点的一个关键字、及邻居合并。有可能进行到根，使可能进行到根，使B_ 树的深度降低一层！树的深度降低

19、一层！哈希查找表哈希查找表前述的查找方法建立在前述的查找方法建立在“比较比较”的基础上，查找的次数依赖的基础上，查找的次数依赖于查找过程中进行比较的次数。于查找过程中进行比较的次数。问题：能否不用比较就能直接计算出记录的存储地址，从而问题：能否不用比较就能直接计算出记录的存储地址，从而找到所要的结点？找到所要的结点？-采用散列（采用散列（hashhash）方法。方法。散列表和查找散列表散列表-是根据设定的散列函数和相应解决冲突的方法将一组关键是根据设定的散列函数和相应解决冲突的方法将一组关键字映射到一个有限的地址集，并以关键字在地址集中字映射到一个有限的地址集，并以关键字在地址集中的像作为记录

20、到表中的存储位置，这种表叫做哈希表。的像作为记录到表中的存储位置，这种表叫做哈希表。散列（又称杂凑、哈希）的基本思想：散列（又称杂凑、哈希）的基本思想：以结点的键值以结点的键值k k为自变量，通过一定的函数关系为自变量，通过一定的函数关系h h计算出计算出对应的函数值对应的函数值h(k),h(k),把这个值解释为结点的存储地址把这个值解释为结点的存储地址（散列地址），将结点存入该地址中去。（散列地址），将结点存入该地址中去。函数函数h h-散列函数散列函数 h(k)-h(k)-散列地址散列地址基本区基本区-分配给散列表的分配给散列表的连续连续存储空间。存储空间。哈希查找表哈希查找表将将 31

21、个常用的英文单词，映射到个常用的英文单词，映射到 M 存区。设存区。设 m=41,映射是等可能性的。映射是等可能性的。哈希表哈希表014039A、AND、YOU:总的可能分总的可能分布为布为 4131，不冲突的分布为，不冲突的分布为 A41 ；不冲突的可能性为不冲突的可能性为 1/10,000,0003131简短的结论：简短的结论：选取好的选取好的 hashing 函数非常困难，不冲突的可能性非常小函数非常困难，不冲突的可能性非常小.冲突冲突:若若 ki !=kk;但但 f(ki)=f(kk)减少冲突的方法：好的减少冲突的方法：好的 hashing 函数减少负载系数函数减少负载系数 哈希表哈希

22、表014039哈希查找表哈希查找表哈希表哈希表014039hashing 函数函数直接地址法直接地址法：取关键字或关键字的某个线性函数值为哈希地取关键字或关键字的某个线性函数值为哈希地址址H(key)=key 或或 H(key)=a key b 如：如：k1,k2 分别有值分别有值 10、1000；选；选10、1000 作为存放地址。简单、不经济。作为存放地址。简单、不经济。除留余数法：除留余数法：H(key)=key MOD p 或或 H(key)=key MOD p+c 这里这里 p=m 最常用，余数总在最常用，余数总在 0 p-1 之间。之间。哈希查找表哈希查找表hashing 函数函数

23、 除留余数法：除留余数法：H(key)=key MOD p 或或 H(key)=key MOD p+c 这里这里 p=m最常用，余数总在最常用，余数总在 0 p-1 之间。通常选之间。通常选 m 的最大质的最大质数。如：数。如：m=1024,则则 p=1019 选取选取 p 为质数的理由：为质数的理由：设设key 值都为奇数，选值都为奇数，选p为偶数；则为偶数；则 H(key)=key MOD p，结结果为奇数，一半单元被浪费掉。果为奇数，一半单元被浪费掉。设设key 值都为值都为 5 的倍数，选的倍数，选p为为 95；则；则 H(key)=key MOD p，结果为：结果为：0、5、10、1

24、5、90奇数。奇数。4/5 的单元被浪费掉。的单元被浪费掉。hashing 函数函数折叠法及位移法：折叠法及位移法：key=381，412，975 选取选取 768 或或 570 作为散列地址作为散列地址（在（在 m 1000 情况下情况下）。）。381 412 9751 768 975 214 381 1 570hashing 函数函数基数转换法基数转换法：key=236076 基数为基数为10，看成是，看成是 13 进制的。进制的。则：（则：（236075）13 8 4154 7；选取；选取 4154 作为散列地址作为散列地址（在（在 m 10000 情况下情况下）。）。平方取中法：平方取

25、中法：（4731）2 223 82 361；选取选取 82（在（在 m 100 情况下情况下）。）。选择哈希函数考虑因素：选择哈希函数考虑因素：o（1）计算哈希函数所需时间）计算哈希函数所需时间o(2)关键字的长度关键字的长度o（3）哈希表的长度）哈希表的长度o（4）关键字的分布情况）关键字的分布情况o（5）记录的查找频率）记录的查找频率冲突的解决办法冲突的解决办法冲突：冲突：初级冲突：不同关键字值的结点得到同一个散列地址。初级冲突：不同关键字值的结点得到同一个散列地址。若对于不同的键值若对于不同的键值k1和和k2,且且k1k2,但但h(k1)=h(k2)，即具即具有相同的散列地址，称为冲突。

26、有相同的散列地址，称为冲突。二次聚集：同不同散列地址的结点争夺同一个单元。二次聚集：同不同散列地址的结点争夺同一个单元。结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到 O（n）级代价。级代价。同义词同义词-发生冲突的两个或多个键值。发生冲突的两个或多个键值。H(17)=6H(60)=5H(29)=7 H(38)=5012345678910Hashing 表表17602938381.1.开放定址法开放定址法假定采用的假定采用的 hashing hashing 函数为：函数为：H(key)=key MOD 11 H(key)=key MOD 11 假定假定的关键字序列为：的关键字序列

27、为：1717、6060、2929、38 38 ；它们的散列过程；它们的散列过程为：为：处理冲突的方法处理冲突的方法当散列当散列 38 38 时发生冲突，同时发生冲突，同 6060争夺第争夺第 5 5 个单元解决个单元解决办法：办法：Hi=(H(key)+di)MOD m i=1,2Hi=(H(key)+di)MOD m i=1,2、k(k=m-1)k(k=m-1)H(key)H(key)为哈希函数为哈希函数 M M为哈希表表长为哈希表表长didi为增量序列为增量序列 （1 1）di=1di=1，2 2，3 3m-1 m-1 线性探测再散列线性探测再散列 （2 2）二次探测再散列二次探测再散列

28、（3 3）di=di=伪随机数序列伪随机数序列 伪随机探测再散列伪随机探测再散列hashing 函数函数2.再再 hashing hashing 法法：出现冲突时，采用多个出现冲突时，采用多个不同不同 hashing hashing 函数计算散列地址，函数计算散列地址，直到找到空单元为止。直到找到空单元为止。冲突的解决办法冲突的解决办法3.链地址法链地址法：将具有同一散列地址的结点保存于将具有同一散列地址的结点保存于 M 存区的各自的链表之存区的各自的链表之中。书上介绍的是外链法，通常用于组织存在于外存设备上中。书上介绍的是外链法，通常用于组织存在于外存设备上的数据文件。的数据文件。10012

29、3456789K1K2K3K4K5K6同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。冲突的解决办法冲突的解决办法4.公共溢出区法公共溢出区法：将发生冲突的结点都存放在一个公共溢出区内。将发生冲突的结点都存放在一个公共溢出区内。通常用于组通常用于组织存在于外存设备上的数据文件。织存在于外存设备上的数据文件。M M 存区只存放一个记录。存区只存放一个记录。发生冲突的记录都存放在公共溢出区内。发生冲突的记录都存放在公共溢出区内。M M 存区和公共溢出存区和公共溢出区都可以分配几个磁道或柱面作为存储空间。区都可以分配几个磁道或柱面作为存储空间。冲突的解决办法冲突的解决办法012345678910K1K2K3K4K5K2K3K5K6基本区（基本区（M 存区存区）公共溢出区公共溢出区