[理学]数据结构第9章.ppt

9.1 静态查找表 9.2 动态查找表 9.3 哈希（Hash）表 (1)B树(B-树) I. B树的定义：一棵m叉(或称m阶)B树，或者是空树，或者是满足下面特性的m叉排序树(lchildparentrchild)： ①每个结点至多有m棵子树， ②如根结点不是叶，至少有两棵子树， ③除根之外，所有非终端结点至少有┌m/2┐ (m/2向上取整)棵子树 ,以后记为[m/2] ④所有的非终端结点含有信息至少[m/2]-1个关键字 Ai是子树指针，Ki是关键字，结点内部关键字有序 ⑤所有叶结点都在同一层次 ，叫做失败结点。 (1)B树(B-树) II. B树的查找： 过程演示 (1)B树(B-树) III. B树的插入：先查找插入的位置，必然在最低一层结点有序插入！但结点的插入可能会导致结点被撑破，需要分两种情况处理： (1)如果插入关键字后,叶子结点中的关键字数量=m-1，则插入操作完毕。 (2)如果插入后，叶子结点中的关键字数量是m，则需要将叶子结点一分为2，成为2个叶子，中间的关键字携带着新叶子结点的指针上升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题了。 这个问题的处理仍需要按照(1)(2)两种情况处理，一直到增加关键字的结点未满或者新生成根结点为止。 (1)B树(B-树) IV. B树的删除：先找到要删除的关键字，如果查找失败，删除操作终止。如果查找成功，则区分两种情况处理： (1)如果关键字位于非叶子结点中，则利用它的直接后继替代它，然后删除它的直接后继。它的直接后继是它的右子树最左端的叶子结点的最左边的关键字。问题就转化为第二种情况。 (2)如果关键字位于叶子结点中，删除操作仍需要分两种情况处理： ①删除后，结点关键字数量=[m/2]-1，删除完成。 ②删除后，结点关键字数量[m/2]-1， 若该结点的左右兄弟结点中有一个关键字数大于[m/2]-1，则将其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。所谓的“借”个关键字，但借关键字同时，也要借该关键字左边或右边的子树指针！ 若该结点的左右兄弟结点的关键字数都等于[m/2]-1，则将其与一个兄弟结点合并，双亲结点中，左右兄弟中间的关键字下移到合并的结点中去。 重复上面2步，直到不再发生合并为止。 ①删除后，结点关键字数量=[m/2]-1，删除完成。 ②删除后，结点关键字数量[m/2]-1， 若该结点的左右兄弟结点中有一个关键字数大于[m/2]-1，则将其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。所谓的“借”个关键字，但借关键字同时，也要借该关键字左边或右边的子树指针！ 若该结点的左右兄弟结点的关键字数都等于[m/2]-1，则将其与一个兄弟结点合并，双亲结点中，左右兄弟中间的关键字下移到合并的结点中去。 重复上面2步，直到不再发生合并为止。 (2)B+树 B-树的变形 根结点(非叶时)至少有两个结点 除根外，非叶结点至少有[m/2]棵子树 最多有m棵子树,非叶结点都是索引，含有子树中的最大或最少关键字 含有n个关键字的非叶结点有n棵子树 所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针 哈希查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系. 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表. 哈希查找——又叫散列查找，利用哈希函数进行查找的过程. 从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1?key2，但H(key1)=H(key2)的现象. 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况 平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种