数据结构 第7章 查找 更新【ppt】 .ppt

开场白 19 04 2020 1 内容提要 查找概论静态查找表动态查找表哈希表 19 04 2020 2 查找概论 19 04 2020 3 查找表 searchtable 同一类型的数据元素 或记录 构成的集合 关键字 key 数据元素中某个数据项的值 又称键值 若某关键字可以唯一地标记一个记录 则称主关键字 primarykey 对于可以识别多个数据元素的关键字 称为次关键字 secondarykey 查找 searching 就是根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素 或记录 查找表的种类 19 04 2020 4 静态查找表 staticsearchtable 只作查找操作的查找表 主要操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素和各种属性 应用 查字典 查个人信息等动态查找表 dynamicsearchtable 在查找过程中同时插入查找表中不存在的数据元素 或者从查找表中删除已经存在的某个数据元素 主要操作 1 查找时插入数据元素 2 查找时删除数据元素应用 清理网站的注册用户等查找结构 为提高查找效率而专门为查找操作设置的数据结构如 线性表 树 散列表等 内容提要 查找概论静态查找表动态查找表哈希表 19 04 2020 5 顺序表查找 顺序查找 sequentialsearch 又叫线性查找 是最基本的查找技术 从表中第一个 或最后一个 记录开始 逐个进行记录的关键字和给定值比较 若某个记录的关键字和给定值相等 则查找成功 找到所查的记录 如果直到最后一个 或第一个 记录 其关键字和给定值比较都不等 则表中没有所查记录 查找不成功 19 04 2020 6 顺序表查找算法 19 04 2020 7 顺序查找 a为数组 n为要查找的数组个数 key为要查找的关键字 朴素版 intsequential search int a intn intkey inti for i 1 i n i if a i key returni return0 有哨兵顺序查找 改进版 intsequential search2 int a intn intkey inti a 0 key 设置a 0 为关键字值 我们称之为 哨兵 for i n a i key i returni 返回0则说明查找失败 有哨兵顺序查找 教科书版 intsearch seq sstablest keytypekey st elem 0 key key for i st length eq st elem i key key i returni 静态查找表 typedefstruct elemtype elem intlength sstable 查找操作的性能分析 平均查找长度 averagesearchlength 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值 对于含有n个记录的表 查找成功时的平均查找长度为 其中 pi为查找表中第i个记录的概率 且顺序查找分析 假设n st length 则顺序查找的平均查找长度为假设每个记录的查找概率相等 即则等概率情况下顺序查找的平均查找长度为假设各个记录的查找概率不相等且已知 记录该如何排列才能提高检索效率 如果查找概率预先未知 如何提高检索效率 如果考虑查找不成功的情况 平均查找长度如何计算 假设查找成功与不成功的可能性相同 19 04 2020 8 有序表查找 书架上的书有序排放 查找起来比无序排列来得快 有序表查找算法折半查找插值查找斐波那契查找 19 04 2020 9 折半查找及算法实现 19 04 2020 10 intbinary search int a intn intkey intlow high mid low 1 high n while lowa mid low mid 1 elsereturnmid return0 调用参数 a 0 1 16 24 35 47 59 62 73 88 99 n 10key 62 折半查找技术 又称二分查找 它的前提是线性表中的记录必须是关键码有序且采用顺序存储 基本思想是 在有序表中 取中间记录作为比较对象 若给定值与中间记录的关键字相等 则查找成功 若小于 则在中间记录的左半区继续查找 否则在右半区继续查找 不断重复 直到查找成功 或失败 99 88 73 62 59 47 35 24 16 1 0 a 下标 9 8 7 6 5 4 3 2 1 0 10 low high mid low mid high mid low mid 时间复杂度 o logn 折半查找的性能分析 19 04 2020 11 47 大了 小了 73 大了 小了 24 大了 小了 1 大了 小了 35 大了 小了 16 47 59 大了 小了 88 大了 小了 62 99 调用参数 a 0 1 16 24 35 47 59 62 73 88 99 n 10key 62 平均搜索长度 注意 对于需要频繁执行插入删除的数据集 不建议使用 插值查找及算法实现 19 04 2020 12 intinterpolation search int a intn intkey intlow high mid low 1 high n while lowa mid low mid 1 elsereturnmid return0 调用参数 a 0 1 16 24 35 47 59 62 73 88 99 n 10key 16折半查找需要查找几次 插值查找呢 为什么一定要折半 而不是折四分之一或者其他呢 插值查找 根据要查找的关键字key与查找表中最大最小记录的关键字比较后使用插值公式计算下一步查找范围的查找方法 时间复杂度 o logn 注意 适合数据分布均匀情况 若极度不均则不是合适选择 斐波那契查找 基本思想 当key a mid 时 查找成功 当keya mid 时 新范围是第mid 1个到第high个 此时范围个数为f k 2 1个 19 04 2020 13 low mid high f k 1 f k 1 1 f k 2 1 34 9 21 8 13 7 8 6 5 5 3 4 2 3 1 2 1 1 0 0 f 下标 0 7 斐波那契查找的代码实现 19 04 2020 14 intfibonacci search int a intn intkey intlow high mid i k low 1 high n k 0 while n f k 1 k for i n ia mid low mid 1 k k 2 else if mid n returnmid elsereturnn 99 88 73 62 59 47 35 24 16 1 0 34 9 21 8 13 7 8 6 5 5 3 4 2 3 1 2 1 1 0 0 f 下标 a 下标 9 8 7 6 5 4 3 2 1 0 10 11 12 99 99 调用参数 a 0 1 16 24 35 47 59 62 73 88 99 n 10key 59 low high mid k 6 high mid low 4 mid high 3 mid 思考 三种mid的不同计算方式有什么影响 k 1 k 1 k 1 k 1 线性索引查找 问题 如何从几千万条记录中快速查找到需要的数据 方法 建立索引 即把一个关键字与它对应的记录相关联 一个索引由多个索引项构成 每个索引项至少需包含关键字和其对应的记录在存储器中的位置等信息 索引结构 线性索引 将索引项集合组织为线性结构 也称索引表 我们将介绍三种线性索引 树形索引多级索引 19 04 2020 15 稠密索引 引子 对于经常在家里找不到东西的人 用一个小本子记录家里物品的位置将非常有帮助 稠密索引 将每个记录对应一个索引项索引项有序 以便使用有序查找算法查找 数据量过大时产生性能问题 19 04 2020 16 分块索引 引子 图书馆里的藏书是怎样分类摆放的 分块索引 把数据集的记录分成若干块 使得 块内无序 块间有序 平均查找长度分析假设n个记录被平均分成m块 每块t条记录设lb为查找索引表的平均查找长度 则lb m 1 2设lw为块中查找记录的平均查找长度 则lw t 1 2分块索引查找的平均查找长度为 aslw lb lw n t t 2 1最佳情况是m t即n mt t2则aslw t 1 19 04 2020 17 倒排索引 引子 搜索引擎如何达成这样快的查找效率呢 是在网页全文中查找匹配吗 倒排技术 invertedindex 最简单最基础的搜索技术 基于索引表 索引项包括 次关键码 和 记录号表 其中 记录号表存储具有相同次关键码的所有记录的记录号 可以是指向记录的指针或者该记录的主关键字 例如 有两篇短文 booksandfriendsshouldbefewbutgood agoodbookisagoodfriend 19 04 2020 18 内容提要 查找概论静态查找表动态查找表哈希表 19 04 2020 19 二叉排序树 之前介绍的线性表查找方法中 折半查找具有很高的效率 o logn 但是它使用的是顺序存储结构 查找表中的数据增 删都不方便 于是 我们考虑树形结构 19 04 2020 20 二叉排序树 binarysorttree 又称二叉查找 搜索 树 binarysearchtree 其定义为 二叉排序树或者是空树 或者是满足如下性质的二叉树 若它的左子树非空 则左子树上所有结点的值均小于根结点的值 若它的右子树非空 则右子树上所有结点的值均大于根结点的值 左 右子树本身又各是一棵二叉排序树 上述性质简称二叉排序树性质 bst性质 故二叉排序树实际上是满足bst性质的二叉树 二叉排序树的特点 19 04 2020 21 由bst性质可得 二叉排序树中任一结点x 其左 右 子树中任一结点y 若存在 的关键字必小 大 于x的关键字 二叉排序树中 各结点关键字是惟一的 按中序遍历该树所得到的中序序列是一个递增有序序列 注意 实际应用中 不能保证被查找的数据集中各元素的关键字互不相同 所以可将二叉排序树定义中bst性质 1 里的 小于 改为 大于等于 或将bst性质 2 里的 大于 改为 小于等于 甚至可同时修改这两个性质 二叉排序树结点定义 19 04 2020 22 二叉排序树用的头文件 文件名 bstree h include includetypedefintdatatype typedefstructnode 二叉排序树结点定义 datatypekey 结点值 structnode lchild rchild 左 右孩子指针 bsnode typedefbsnode bstree 二叉排序树的查找运算 19 04 2020 23 include bstree h 二叉排序树的递归查找 在根指针t所指二叉排序树中递归地查找某关键字等于key的数据元素 若查找成功 则返回指向该数据元素结点的指针 否则返回空指针 bstreesearchbst bsnode t datatypex if t null x t key returnt if xkey 递归地在左子树中检索 returnsearchbst t lchild x else 递归地在右子树中检索 returnsearchbst t rchild x 对于一棵给定的二叉排序树 树中的查找运算很容易实现 其算法可描述如下 1 当二叉树为空树时 检索失败 2 如果二叉排序树根结点的关键字等于待检索的关键字 则检索成功 3 如果待检索的关键字小于二叉排序树根结点的关键字 则用相同的方法继续在根结点的左子树中检索 4 如果待检索的关键字大于二叉排序树根结点的关键字 则用相同的方法继续在根结点的右子树中检索 二叉排序树的查找算法性能分析 在二叉排序树上进行检索的方法与二分检索相似 和关键字的比较次数不会超过树的深度 因此 在二叉排序树上进行检索的效率与树的形状有密切的联系 在最坏的情况下 含有n个结点的二叉排序树退化成一棵深度为n的单支树 类似于单链表 它的平均查找长度与单链表上的顺序检索相同 即asl n 1 2 在最好的情况下 二叉排序树形态比较匀称 对于含有n个结点的二叉排序树 其深度不超过log2n 此时的平均查找长度为o log2n 19 04 2020 24 例如 对于右图中的两棵二叉排序树 其深度分别是4和10 在检索失败的情况下 在这两棵树上的最大比较次数分别是4和10 在检索成功的情况下 若检索每个结点的概率相等 则对于图 a 所示的二叉排序树其平均查找长度为 asla 对于图 b 所示的二叉排序树其平均查找长度为 aslb 1 2 3 4 5 6 7 8 9 10 10 5 5 b a 二叉排序树的插入运算 19 04 2020 25 voidinsertbst bstree 假设待插入的数据元素为x 则二叉排序树的插入算法可以描述为 若二叉排序树为空 则生成一个关键字为x的新结点 并令其为二叉排序树的根结点 否则 将待插入的关键字x与根结点的关键字进行比较 若二者相等 则说明树中已有关键字x 无须插入 若x小于根结点的关键字 则将x插入到该树的左子树中 否则将x插入到该树的右子树中去 将x插入子树的方法与在整个树中的插入方法是相同的 如此进行下去 直到x作为一个新的叶结点的关键字插入到二叉排序树中 或者直到发现树中已有此关键字为止 二叉排序树的建立 19 04 2020 26 bstreecreatbst 根据输入的结点序列 建立一棵二叉排序树 并返回根结点的地址 bstreet null datatypekey printf n请输入一个以 1为结束标记的结点序列 n scanf d 返回建立的二叉排序树的根指针 对于输入实例 30 20 40 10 25 45 创建二叉排序树的过程如下 a 空树 30 b 插入30 c 插入20 d 插入40 e 插入10 f 插入25 g 插入45 思考 对于输入实例 30 20 10 25 40 45 或 30 40 45 20 10 25 生成的二叉排序树一样吗 如果是 10 20 25 30 40 45 或 45 40 30 25 20 10 呢 二叉排序树的删除 一 原则 从二叉排序树中删除一个结点 不能把以该结点为根的子树都删去 并且还要保证删除后所得的二叉树仍然满足bst性质删除操作的一般步骤 1 进行查找 查找时 令p指向当前访问到的结点 parent指向其双亲 其初值为null 开始查找 若树中找不到被删结点则返回 否则p指向被删结点 2 删去 p 删 p时 应将 p的子树 若有 仍连接在树上且保持bst性质不变 根据二叉排序树的结构特征 删除 p可以分四种情况来考虑 待删除结点为叶结点待删除结点只有左子树 而无右子树待删除结点只有右子树 而无左子树待删除结点既有左子树又有右子树 19 04 2020 27 二叉排序树的删除 二 情况1 待删除结点为叶结点 则直接删除该结点即可 若该结点同时也是根结点 则删除后二叉排序树变为空树 下图给出了一个删除叶结点的例子 19 04 2020 28 二叉排序树的删除 三 情况2 待删除结点只有左子树 而无右子树 根据二叉排序树的特点 可以直接将其左子树的根结点替代被删除结点的位置 即如果被删结点为其双亲结点的左孩子 则将被删结点的唯一左孩子收为其双亲结点的左孩子 否则收为其双亲结点的右孩子 下图给出了一个例子 19 04 2020 29 二叉排序树的删除 四 情况3 待删除结点只有右子树 而无左子树 与情况2类似 可以直接将其右子树的根结点替代被删除结点的位置 即如果被删结点为其双亲结点的左孩子 则将被删结点的唯一右孩子收为其双亲结点的左孩子 否则收为其双亲结点的右孩子 下图给出了一个例子 19 04 2020 30 二叉排序树的删除 五 情况4 待删除结点既有左子树又有右子树 根据二叉排序树的特点 可以用被删除结点中序下的前趋 或后继 结点代替被删除结点 同时删除其中序下的前趋 或后继 结点 而被删除的中序下的前趋 后继 结点必然无右 左 子树 因而问题转换为第2种情况或第3种情况 19 04 2020 31 二叉排序树的删除 六 情况4续 除此之外 还可以直接将被删结点的右子树代替被删除结点 同时将被删除结点的左子树收为被删结点右子树中序首点的左孩子 也可以直接将被删除结点的左子树代替被删除结点 同时将被删结点的右子树收为被删结点左子树中序尾点的右孩子 下图给出示例 19 04 2020 32 二叉排序树的删除的代码实现 19 04 2020 33 若二叉排序树t中存在关键字等于key的数据元素时 则删除该数据元素结点 并返回true 否则返回false statusdeletebst bitree 从二叉排序树中删除结点p 并重接它的左或右子树 statusdelete bitree 思考 这段代码针对情况4采用了那种删除办法 二叉排序树中结点的删除操作的主要时间在于查找被删除结点及查找被删结点的右子树的中序首点上 而这个操作的时间花费与树的深度密切相关 因此 删除操作的平均时间亦为o log2n 平衡二叉树 二叉排序树上实现的插入 删除和查找等基本操作的平均时间虽然为o log2n 但在最坏情况下 二叉排序树退化成一个具有单个分支的单链表 此时树高增至n 这将使这些操作的时间相应地增至o n 为了避免这种情况发生 人们研究了许多种动态平衡的方法 包括如何建立一棵 好 的二叉排序树 如何保证往树中插入或删除结点时保持树的 平衡 使之既保持二叉排序树的性质又保证树的高度尽可能地为o log2n 平衡二叉树又称为avl树 它或是一棵空树 或是具有下列性质的二叉树 它的左子树和右子树都是平衡二叉树 且左子树和右子树高度之差的绝对值不超过1 此处规定二叉树的高度是二叉树的树叶的最大层数 也就是从根结点到树叶的最大路径长度 空的二叉树的高度定义为 1 相应地 二叉树中某个结点的左子树高度与右子树高度之差称为该结点的平衡因子 或平衡度 由此可知 平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树 19 04 2020 34 思考 这两棵树是不是平衡二叉树 平衡二叉树结点定义 19 04 2020 35 typedefstruct elemtypedata 结点的数据域intbf 结点的平衡因子structbstnode lchild rchild 左 右孩子指针 bstnode bstnode definelh1 左高 defineeh0 等高 definerh 1 右高 平衡二叉树的插入算法 g m adelson velskii和e m landis在1962年提出了动态保持二叉排序树平衡的一个有效办法 后称为adelson方法 下面介绍adelson方法如何将一个新结点k插入到一棵平衡二叉排序树t中去 adelson方法由三个依次执行的过程 插入 调整平衡度和改组所组成 1 插入 不考虑结点的平衡度 使用在二叉排序树中插入新结点的方法 把结点k插入树中 同时置新结点的平衡度为0 2 调整平衡度 假设k0 k1 km k是从根k0到插入点k路径上的结点 由于插入了结点k 就需要对这条路径上的结点的平衡度进行调整 调整方法是 从结点k开始 沿着树根的方向进行扫描 当首次发现某个结点kj的平衡度不为零 或者kj为根结点时 便对kj与km 1之间结点进行调整 令调整的结点为ki j i m 若k在ki的左子树中 则ki的平衡度加1 若k在ki的右子树中 则ki的平衡度减1 此时 kj 1 kj 2 km 1结点不会失去平衡 唯一可能失去平衡的结点是kj 若kj失去平衡 即kj的平衡因子不是 1 0和1时 便对以kj为根的子树进行改组 且保证改组以后以kj为根的子树与未插入结点k之前的子树高度相同 这样 k0 k1 kj 1的平衡度将保持不变 这就是为何不需要对这些结点进行平衡度调整的原因 反之 若kj不失去平衡 则说明 新结点k的加入并未改变以kj为根的子树的高度 整棵树无需进行改组 3 改组 改组以kj为根的子树除了满足新子树高度要和原来以kj为根子树的高度相同外 还需使改造后的子树是一棵平衡二叉排序树 19 04 2020 36 avl树插入结点失去平衡的调整方法 一 下面具体讨论avl树上因插入新结点而导致失去平衡时的改组方法为叙述方便 假设在avl树上因插入新结点而失去平衡的最小子树的根结点为a 即a为距离插入结点最近的 平衡因子不是 1 0和1的结点 失去平衡后的改组操作可依据失去平衡的原因归纳为下列四种情况分别进行 ll型平衡旋转rr型平衡旋转lr型平衡旋转rl型平衡旋转 19 04 2020 37 avl树插入结点失去平衡的调整方法 二 1 ll型平衡旋转 由于在a的左孩子的左子树上插入新结点 使a的平衡度由1增至2 致使以a为根的子树失去平衡 如下图所示 此时应进行一次顺时针旋转 提升 b 即a的左孩子 为新子树的根结点 a下降为b的右孩子 同时将b原来的右子树br调整为a的左子树 19 04 2020 38 voidr rotate bstree p lc lc p avl树插入结点失去平衡的调整方法 三 2 rr型平衡旋转 由于在a的右孩子的右子树上插入新结点 使a的平衡度由 1变为 2 致使以a为根的子树失去平衡 如下图所示 此时应进行一次逆时针旋转 提升 b 即a的右孩子 为新子树的根结点 a下降为b的左孩子 同时将b原来的左子树bl调整为a的右子树 19 04 2020 39 voidl rotate bstree p rc rc p avl树插入结点失去平衡的调整方法 四 3 lr型平衡旋转 由于在a的左孩子的右子树上插入新结点 使a的平衡度由1变成2 致使以a为根的子树失去平衡 如下图所示 此时应进行两次旋转操作 先逆时针 后顺时针 即 提升 c 即a的左孩子的右孩子 为新子树的根结点 a下降为c的右孩子 b变为c的左孩子 c原来的左子树cl调整为b现在的右子树 c原来的右子树cr调整为a现在的左子树 19 04 2020 40 a 2 b 1 lr型 c 1 a 2 p lc p rc t l rotate t lchild r rotate t avl树插入结点失去平衡的调整方法 五 4 rl型平衡旋转 由于在a的右孩子的左子树上插入新结点 使a的平衡度由 1变成 2 致使以a为根的子树失去平衡 如下图所示 此时应进行两旋转操作 先顺时针 后逆时针 即 提升 c 即a的右孩子的左孩子 为新子树的根结点 a下降c的左孩子 b变为c的右孩子 c原来的左子树cl调整为a现在的右子树 c原来的右子树cr调整为b现在的左子树 19 04 2020 41 a 2 rl型 r rotate t rchild l rotate t a 2 p lc t p rc 平衡二叉树的插入算法描述 综上所述 在平衡的二叉排序树t上插入一个新的数据元素x的算法可描述如下 一 若avl树t为空树 则插入一个数据元素为x的新结点作为t的根结点 树的深度增1 二 若x的关键字和avl树t的根结点的关键字相等 则不进行插入 三 若x的关键字小于avl树t的根结点的关键字 则将x插入在该树的左子树上 并且当插入之后的左子树深度增加1时 分别就下列不同情况进行分情形处理 1 若avl树的根结点的平衡因子为 1 右子树的深度大于左子树的深度 则将根结点的平衡因子调整为0 并且树的深度不变 2 若avl树的根结点的平衡因子为0 左 右子树的深度相等 则将根结点的平衡因子调整为1 树的深度同时增1 3 若avl树的根结点的平衡因子为1 左子树的深度大于右子树的深度 则当该树的左子树的根结点的平衡因子为1时需进行ll型平衡旋转 当该树的左子树的根结点的平衡因子为 1时需进行lr型平衡旋转 四 若x的关键字大于avl树t的根结点的关键字 则将x插入在该树的右子树上 并且当插入之后的右子树深度增加1时 需要分别就不同情况进行处理 其处理操作和 三 中所述相对称 读者可以自行分析 19 04 2020 42 平衡二叉树插入新结点的过程示例 19 04 2020 43 结点序列 120 80 30 90 45 60 逐个插入一棵空的avl树的过程如下 b 树 一 前面所讨论的查找算法都是在内存中进行的 它们适用于较小的文件 而对较大的 不能一次全部放在内存而不得不存放在外存储器上的文件就不合适了 1972年r bayer和e m mccreight提出了一种称为b 树的多路平衡查找树 它能减少硬盘的读取次数 适合在磁盘等直接存取设备上组织动态的查找表 b 树的定义 b 树是一种平衡的多路查找树 在文件系统中 已经成为索引文件的一种有效结构 并得到泛的应用 一棵m阶 m 3 b 树 或为空树 或为满足下列特性的m叉树 1 树中每个结点至多有m棵子树 2 若根结点不是叶子结点 则至少有两棵子树 待续 19 04 2020 44 b 树 二 一棵m阶 m 3 b 树 或为空树 或为满足下列特性的m叉树 续前 3 所有的非终端结点中包含下列信息 n p0 k1 p1 k2 p2 kn pn 其中 ki 1 i n 为关键字 且ki ki 1 1 i n pj 0 j n 为指向子树根结点的指针 且pj 0 j n 所指子树中所有结点的关键字均小于kj 1 pn所指子树中所有结点的关键字均大于kn n m 2 1 n m 1 为关键字的个数 n 1为子树个数 4 除根结点之外所有非终端结点至少有 m 2 棵子树 也即每个非根结点至少应有 m 2 1个关键字 5 所有的叶子结点都出现在同一层上 并且不带信息 可以看作是外部结点或查找失败的结点 实际上这些结点不存在 指向这些结点的指针为空 19 04 2020 45 基于b 树的查找操作 19 04 2020 46 25080 root 22040 25570 查找75 查找18 基于b 树的插入操作 一 在b 树中插入关键字k的方法是 首先在树中查找k 若找到则直接返回 假设不处理相同关键字的插入 否则查找操作必失败于某个叶子结点上 利用函数btree search 的返回值 p及 pos可以确定关键字k的插入位置 即将k插入到p所指的叶结点的第pos个位置上 若该叶结点原来是非满 结点中原有的关键字总数小于m 1 的 则插入k并不会破坏b 树的性质 故插入k后即完成了插入操作 例如 在下图 a 所示的5阶b 树的某结点 假设为p结点 中插入新的关键字150时 可直接得到图 b 所示的结果 19 04 2020 47 2100190 3100150190 在关键字个数不满的结点中插入关键字 b a 基于b 树的插入操作 二 若p所指示的叶结点原为满 则k插入后keynum m 破坏了b 树的性质 1 故须调整使其维持b 树的性质不变 调整的方法是将违反性质 1 的结点以中间位置的关键字key m 2 为划分点 将该结点 即p m p0 k1 p1 km pm 分裂为两个结点 左边结点为 m 2 1 p0 k1 k m 2 1 p m 2 1 右边结点为 m m 2 p m 2 k m 2 1 km pm 同时把中间关键字k m 2 插入到双亲结点中 于是双亲结点中指向被插入结点的指针pre改成pre k m 2 pre 三部分 指针pre指向分裂后的左边结点 指针pre 指向分裂后的右边结点 由于将k m 2 插入双亲时 双亲结点亦可能原本为满 若如此 则需对双亲做分裂操作 分裂过程的例子如下图所示 19 04 2020 48 一棵5阶b 树的生长过程 如果初始时b 树为空树 通过逐个向b 树中插入新结点 可生成一棵b 树 下图说明了一棵5阶b 树的生长过程 19 04 2020 49 681516 68 15 1622 6810 15 16182232 a 插入6 8 15 16 6810 1520 1618 2232 681012 1520 161819 22324050 681012 152040 161819 2232 5056 f 插入56 68 9152040 161819 22263236 50525556 1012 68 915 161819 2226 50525556 1012 3638 20 3240 h 插入38 b 插入22 c 插入10 18 32 d 插入20 e 插入12 19 40 50 g 插入9 26 36 52 55 基于b 树的删除操作 一 在b 树上删除一个关键字 首先找到该关键字所在结点及其在结点中的位置 具体可分为两种情况 1 若被删除结点ki在最下层的非终端结点 即叶子结点的上一层 里 则应删除ki及它右边的指针pi 删除后若结点中关键字数目不少于 m 2 1 则删除完成 否则要进行 合并 结点的操作 2 假若待删结点ki是最下层的非终端结点以上某层的结点 根据b 树的特性可知 可以用ki右边指针pi所指子树中最小关键字y代替ki 然后在相应的结点中删除y 或用ki左边指针pi 1所指子树中最大关键字x代替ki 然后在相应的结点中删除x 例如删除下左图所示3阶b 树中的关键字50 可以用它右边指针所指子树中最小关键字60代替50 尔后转化为删除叶子上面一层的结点中的60 删除后得到的b 树如下右图所示 19 04 2020 50 基于b 树的删除操作 二 因此 下面主要讨论删除b 树叶子上面一层结点中的关键字的方法 具体分三种情形 1 被删关键字所在叶子上面一层结点中的关键字数目不小于 m 2 则只需要从该结点中删去关键字ki和相应的指针pi 树的其它部分不变 19 04 2020 51 例 删除下左图所示3阶b 树中的60与115 基于b 树的删除操作 三 2 被删关键字所在叶子上面一层结点中的关键字数目等于 m 2 1 而与该结点相邻的右兄弟结点 或左兄弟结点 中的关键字数目大于 m 2 1 则需要将其右兄弟的最小关键字 或其左兄弟的最大关键字 移至双亲结点中 而将双亲结点中小于 或大于 该上移关键字的关键字下移至被删关键字所在的结点中 例如从下左图中删除关键字90 结果如右图所示 19 04 2020 52 例 删除下左图所示3阶b 树中的90 基于b 树的删除操作 四 3 被删关键字所在叶子上面一层结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于 m 2 1 则第 2 种情况中采用的移动方法将不奏效 此时须将被删关键字所有结点与其左或右兄弟合并 不妨设该结点有右兄弟 但其右兄弟地址由双亲结点指针pi所指 则在删除关键字之后 它所在结点中剩余的关键字和指针加上双亲结点中的关键字ki一起合并到pi所指兄弟结点中 若没有右兄弟 则合并至左兄弟结点中 我们用两个例子进行说明 19 04 2020 53 基于b 树的删除操作 五 例如 从下左图中删去关键字120 则应删去120所在结点 并将双亲结点中的150与200合并成一个结点 删除后的树如下右图所示 如果这一操作使双亲结点中的关键字数目小于 m 2 1 则依同样方法进行调整 最坏的情况下 合并操作会向上传播至根 当根中只有一个关键字时 合并操作将会使根结点及其两个孩子合并成一个新的根 从而使整棵树的高度减少一层 19 04 2020 54 例 删除下左图所示3阶b 树中的120 基于b 树的删除操作 六 例如 在下左图中删除关键字8 此关键字所在结点无左兄弟 只检查其右兄弟 然而右兄弟关键字数目等于 m 2 1 此时应检查其双亲结点关键字数目是否大于等于 m 2 1 但此处其双亲结点的关键字数目等于 m 2 1 从而进一步检查双亲结点兄弟结点关键字数目是否均等于 m 2 1 这里关键字28所在的结点的右兄弟结点关键字数目正好等于 m 2 1 因此将28和40结合成一个结点 50和85结合成一个结点 使得树变矮 删除结点8后的结果如下右图所示 19 04 2020 55 例 删除下左图所示3阶b 树中的8 b 树遍历面临的问题 假设下图所示的这棵b树的每个结点都属于硬盘的不同页面 为了中序遍历所有的元素 就得遵循 页面2 页面1 页面3 页面1 页面4 页面1 页面5 这样的顺序 频繁地访问硬盘 导致效率很低 如何解决这个问题呢 19 04 2020 56 3 3 5 8 n k1 k2 k3 2 1 2 2 4 2 6 7 1 9 页面1 页面2 页面3 页面4 页面5 a0 a1 a2 a3 b 树 为了解决b 树面临的遍历等基本问题 在原有b树结构基础上加了新的元素组织方式 于是产生了b 树 b 树是应文件系统所需而设计的一种b树的变形树 严格意义上已经不是我们数据结构课上定义的树了 一棵b阶的b 树和m阶的b树的差异在于 有n棵子树的结点中包含有n个关键字 所有的叶子结点包含全部关键字的信息 及指向含这些关键字记录的指针 叶子结点本身依关键字的大小自小而大顺序链接 所有分支结点可以看成是索引 结点中仅含有其子树种的最大 或最小 关键字 注意 b 树的插入 删除过程与b树类似 只不过插入和删除操作都需要在叶子结点进行 19 04 2020 57 3 5 8 1 2 3 4 5 6 7 8 9 9 内容提要 查找概论静态查找表动态查找表哈希表 19 04 2020 58 散列表检索 一 在已经介绍过的线性表 树等数据结构中 记录存储在结构中的相对位置是随机的 因而相应的检索是通过若干次的比较以寻找指定的记录 接下来将介绍一种新的存储结构 散列存储 它既是一种存储方式 又是一种常见的检索方法 19 04 2020 59 散列存储的基本思想是以关键码的值为自变量 通过一定的函数关系 称为散列函数 或称哈希 hash 函数 计算出对应的函数值来 以这个值作为结点的存储地址 将结点存入计算得到的存储单元里去 按这个思想 采用散列技术将记录存储在一块连续的存储空间中 这块连续存储空间称为散列表或哈希表 关键字对应的记录存储位置称为散列地址 散列表检索 二 散列过程 在存储时 通过散列函数计算记录的散列地址 并按此散列地址存储该记录 当查找记录时 通过同样的散列函数计算记录的散列地址 按此散列地址访问该记录 散列技术的特点记录间不存在逻辑关系 只和关键字有关 最适合求解查找与给定值相等的记录 不适合范围查找 或者那种同一个关键字对应很多记录的情况 散列表实例 已知线性表的关键字集合为 s and begin do end for go if then until 则可设哈希表为 charht 26 8 哈希函数h key 的值 可取关键字key中第一个字母在字母表中的序号 0 25 即h key key 0 a 19 04 2020 60 散列技术的冲突问题 散列存储中经常会出现对于两个不同关键字xi xj 却有h xi h xj 即对于不同的关键字具有相同的存放地址 这种现象称为冲突或碰撞 碰撞的两个 或多个 关键字称为同义词 相对于函数h而言 负载因子 反映了散列表的装填程度 其定义为 当 1时冲突是不可避免的 因此 散列存储必须考虑解决冲突的办法 综上所述 对于hash方法 需要研究下面两个主要问题 1 选择一个计算简单 并且产生冲突的机会尽可能少的hash函数 2 确定解决冲突的方法 19 04 2020 61 散列表中结点的数目 基本区域能容纳的结点数 散列函数的构造 19 04 2020 62 构造哈希函数时的几点要求 哈希函数的定义域必须包括需要存储的全部关键字 如果哈希表允许有m个地址时 其值域必须在0到m 1之间 哈希函数计算出来的地址应能均匀分布在整个地址空间中 若key是从关键字集合中随机抽取的一个关键字 哈希函数应能以同等概率取0到m 1中的每一个值 哈希函数应是简单的 能在较短的时间内计算出结果 散列函数的构造方法 一 19 04 2020 63 1 除留余数法选择一个适当的正整数p 用p去除关键字 取所得得余数作为散列地址 即 hash key key pp m这个方法的关键是选取适当的p 选择p最好不要是偶数 也不要是基数的幂 一般地选p为小于或等于散列表长度m的某个最大质数比较好 例如m 8 16 32 64 128 256 512 1024p 7 13 31 61 127 251 503 1019适用情况 除留余数法的地址计算公式简单 而且在很多情况下效果较好 因此是一种常用的构造散列函数的方法 例如s 5 21 65 22 69 若m 7且h x x 7 则可以得到如下表所示的hash表 0123456 散列函数的构造方法 二 19 04 2020 64 2 直接定址法散列函数是关键码的线性函数 即 h key a key b a b为常数 适用情况 事先知道关键码 关键码集合不是很大且连续性较好 例 关键码集合为 10 30 50 70 80 90 选取的散列函数为h key key 10 则散列表为 10 30 50 70 80 90 散列函数的构造方法 三 19 04 2020 65 3 数字分析法根据关键码在各个位上的分布情况 选取分布比较均匀的若干位组成散列地址 适用情况 能预先估计出全部关键码的每一位上各种数字出现的频度 不同的关键码集合需要重新分析 例 关键码为8位十进制数 散列地址为2位十进制数 813465328137224281387422813013678132281781338967 散列函数的构造方法 四 19 04 2020 66 4 平方取中法对关键码平方后 按散列表大小 取中间的若干位作为散列地址 平方后截取 适用情况 事先不知道关键码的分布且关键码的位数不是很大 例 散列地址为2位 则关键码123的散列地址为 1234 2 1522756 散列函数的构造方法 五 19 04 2020 67 5 折叠法将关键码从左到右分割成位数相等的几部分 将这几部分叠加求和 取后几位作为散列地址 适用情况 关键码位数很多 事先不知道关键码的分布 例 设关键码为25346358705 散列地址为三位 253463587 05 1308移位叠加 253364587 50 1254间界叠加 散列函数的构造方法 六 19 04 2020 68 6 随机数法选择一个随机函数 取关键字的随机函数值作为它的散列地址 即 h key random key 适用情况 通常 当关键字长度不等时采用此法构造散列地址比较恰当 处理散列冲突的方法 一 1 开放定址法开放定址法的基本做法是在发生冲突时 按照某种方法继续探测基本表中的其它存储单元 直到找到一个开放的地址 即空位置 为止 显然这种方法需要用某种标记区分空单元与非空单元 开放定址法的一般形式可表示为 hi k h k di modm i 1 2 k k m 1 其中 h k 为键字为k的直接哈希地址 m为哈希表长 di为每次再探测时的地址增量 当di 1 2 3 m 1时 称为线性探测再散列 当di 12 12 22 22 k2 k2 k m 2 时 称为二次探测再散列 当di 随机数序列时 称为随机探测再散列 19 04 2020 69 例如 有数据 654 638 214 357 376 854 662 392 现采用数字分析法 取得第二位数作为哈希地址 将数据逐个存放入大小为10的散列表 此处为顺序表 中 若采用线性探测法解决地