数据结构第9章查找3动态查找表ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:第第9 9章章 查找查找查找的根本概念静态查找表动态查找表哈希表:vB-树树 (B-Trees) 9.2 动态查找表动态查找表 B-树是二叉查找树的自然推行，是为磁盘存储而设计的一种平衡多路查找树。:vB-树树 (B-Trees) 9.2 动态查找表动态查找表:vB-树树 (B-Trees) 9.2 动态查找表动态查找表:B-树的定义树的定义 一棵 m 阶的 B- 树，或为空树或为满足以下特性的 m 叉树： F111271FF391991F64534

2、73FFFFFFF a b c d e f g h (1)、树中每个结点至多有 m 棵子树； (2)、假设根结点不是叶子结点，那么至少有两棵子树；(3)、除根之外的一切非终端结点至少有 m/2 棵子树； 阶 m 可以事先恣意指定， 一旦指定后就固定不变。 (4)、一切的非终端结点的构造为：n, A0, K1, A1, K2, A2, , Kn, An 其中，Ki ( i = 1, , n ) 为按升序陈列的关键字； Ai (i = 0, , n) 为指向子树 根结点的指针，且 Ai 所指子树中一切结点的关键字均小于 ki，An 所指子树 中一切结点的关键字均大于 kn

3、，n ( 对于根结点 1nm 1, 对于其它结点 m/2 1 n m 1) 为关键字的个数或 n +1 为子树个数。 (5)、一切叶子结点在同一个层次上，且不含有任何信息。可 以看作是外部结点或查找失败的结点，实践上这些结点不 存在，指向这些结点的指针为空。 :B-树的特点树的特点B- 树特点 平衡 多路 查找 树中一切叶子结点均不带信息且在树的同一层次上； 根结点或为叶子结点，或至少含有两棵子树； 一切非叶子结点均含有 n m/2 nm棵子树。 在 m 阶的 B- 树上，每个非终端结点能够含有： n 个关键字 Ki1inn m n 个指向记录的指针 Di1in n+1 个指向子树的指针 Ai

4、0in非叶子结点中的多个关键字均自小至大有序陈列； Ai -1 所指子树上一切关键字均小于 Ki ； Ai 所指子树上一切关键字均大于 Ki 。 :B-树的查找树的查找 F111271FF391991F6453473FFFFFFF a b c d e f g h 47 47 从根结点出发，沿指针搜索结点和在结点内进展顺序或折 半查找两个过程交叉进展。 假设查找胜利，那么前往指向被查关键字所在结点的指针和关键 字在结点中的位置；:vB-树上查找关键字树上查找关键字479.2 动态查找表动态查找表1 135351 118181 111111 127271 139393 3

5、4747535364641 199992 243437878一棵4阶的B-树4753434735:vB-树的插入树的插入9.2 动态查找表动态查找表 设要插入关键值为k的记录，指向k所在记录的指针为p 首先找到k应插入的叶子结点，将k和p插入。然后，判别被插入结点能否满足m叉B-树的定义，即插入后结点的分支数能否大于m(结点的关键字数能否m-1)，假设不大于，那么插入终了；否那么，要把该结点分裂成两个。方法是： 恳求一个新结点，由指针p指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，假设

6、双亲结点在插入后也要分裂，那么在分裂后再往上插入。: 538545 243 12375053 9061 70 95插入插入30 30 373030插入插入85 85 8585617070 9070703 3阶阶B-B-树树:12 37 70 插入1212 37 70324459037 703 12 244590插入24371245 70 90插入90插入45371245 7037 70124590371270从空树开场,插入关键字,创建一棵 3阶B-树37插入3737 703 124590插入31270324459037B-树的创建树的创建 37 , 70 , 12 , 45 , 90 , 3

7、 , 24 空树37 70插入70分裂分裂分裂分裂:vB-树的删除树的删除9.2 动态查找表动态查找表 假设为最下层的非终端结点，且关键字个数不少于m/2，那么删除完成；否那么，要进展“合并结点的操作。 假设删除的关键字为非终端结点中的Ki，那么可以指针Ai所指子树的最小关键字Y替代Ki，然后删除相应结点的Y，实践问题转化为删除最下层非终端结点中的关键字的情形。:vB-树的删除树的删除9.2 动态查找表动态查找表分为3种情况： a.被删除关键字所在结点的关键字不小于 m/2 b.被删除关键字所在结点的关键字等于 m/2 -1，而兄弟 m/2 -1 c.被删除关键字所在结点的关键字与其兄弟结点的

8、关键字数目均等于 m/2 -1:v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433753 901005061,7045243 123753 901005061 70删除12 (1)被删关键字所在结点中的关键字数目不小于m/2 ，那么只需从该结点中删去该关键字Ki和相应指针Ai，树的其它部分不变。:v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433753 901005061,70452433761 901005370删除50(2)被删关键字所在结点中的关键字数目等于m/2

9、-1 ，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于m/2 -1 ，那么需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。 :v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433761 901005370删除53(3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于m/2 -1 。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，那么在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一

10、同，合并到 Ai所指兄弟结点中(假设没有右兄弟，那么合并至左兄弟结点中)。45243379010061 70:vB+树树9.2 动态查找表动态查找表B+树是B-树的一种变型, 它和B-树的差别是:1.有n棵子树的结点含有n个关键字。2.叶子结点含有全部关键字及指向对应记录的指针, 且叶子结点间按关键字有序顺序链接。3.一切分支结点可看作索引, 结点中仅含其子树(根结点)中的最大(小)关键字。:vB+树树9.2 动态查找表动态查找表:vB+树树9.2 动态查找表动态查找表B+树是B-树的变体，也是一种多路搜索树：1.其定义根本与B-树同，除了：2.非叶子结点的子树指针与关键字个数一样；3.非叶子结点的子树指针Pi，指向关键字值属于Ki, Ki+1)的子树B-树是开区间；5.为一切叶子结点添加一个链指针；6.一切关键字都在叶子结点出现；:vB+树树9.2 动态查找表动态查找表B-树B+树:vB+树的搜索树的搜索9.2 动态查找表动态查找表 B+的搜索与B-树也根本一样，区别是B+树只需到达叶子结点才命中B-树可以在非叶子结点命中，其性能也等价于在关键字选集做一次二分