[理学]《数据结构与算法》第八章 查找.ppt

Chapter 8Search 折半查找判定树的构造方法 对于平衡二叉树来说，它的深度和logn是同数量级的，因此我们希望任何初始序列构成的二叉排序树都是AVL树。 如何使构成的二叉排序树成为平衡二叉树呢？可以通过对结点的旋转操作来实现。下面讨论一般的情况。 【例】 假设一组记录的关键字分别为{18，27，1，20，22，6，10，13，41，15，25}，选取关键字与记录位置间的函数为f(key)=key %11。 思考：能否不用比较，通过关键码直接确定 存储位置？ Hash函数---关键字与记录位置间的函数。 Hash地址--据Hash函数计算出的存储位置。 Hash表--存储记录的查找表,该表中根据Hash函数计算出的存储位置。 基于Hash表的查找称为Hash查找。 1) 若二叉排序树为空树，新插入的结点为根结点； 2) 若二叉排序树非空，新插入的结点必为一个新的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 例： 二叉排序树的插入 40 50 45 12 53 3 37 99 24 插入 40， 插入 50， 是 37 的右孩子。 是 53 的左孩子。 例：设查找的关键字序列为 {45, 24, 53, 45, 12, 24, 90}， 可生成二叉排序树如下： 中序遍历二叉排序树可得到一个关键字的有序序列。 二叉排序树生成：从空树出发，经过一系列的查找、 插入操作，可生成一棵二叉排序树。 45 53 24 90 12 二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构。 要求：删除某个结点后，保持二叉排序树的特性。 删除二叉排序树中的 ?p 结点，分三种情况讨论： 1) ?p 为叶子结点。因删除叶子结点不破坏树的结构，故只需修改 ?p 双亲 ?f 的指针。 二叉排序树的删除 F P Q F P Q F - lchild=NULL F-rchild=NULL 2) ?p 只有左子树或右子树： ?p 只有左子树，用 ?p 的左孩子代替 ?p； 中序遍历：PL P F Q 中序遍历： PL F Q F P PL Q F PL Q 中序遍历：Q F PL P 中序遍历：Q F PL F P PL Q F PL Q ?p 只有右子树，用 ?p 的右孩子代替 ?p； F P PR Q F PR Q 中序遍历： P PR F Q 中序遍历： PR F Q 中序遍历：Q F P PR 中序遍历：Q F PR F P PR Q F PR Q 中序：CL C …QL Q SL S P PR F 中序：CL C …QL Q SL S PR F 3) ?p 左、右子树均非空： F P C PR CL Q QL S SL F C PR CL Q QL S SL 用 ?p 的直接前驱取代 ?p F C PR CL Q QL S SL 用 ?p 的直接后继取代 ?p 若 ?p 的左子树无右子树， 用 ?p 的左子树取代 ?p。 中序遍历：CL C P PR F 中序遍历：CL C PR F F P C PR CL F C PR CL F P C PR CL Q QL S SL F C PR CL Q QL S SL 中序：CL C …QL Q SL S P PR F 中序：CL C …QL Q SL S PR F 二叉排序树上查找某关键字等于给定值的结点过 程，其实就是走了一条从根到该结点的路径。 30 80 20 90 85 40 35 88 32 50 35 比较的关键字次数 此结点所在层次数 最多的比较次数 树的深度 = = 二叉排序树的查找分析 查找关键字：35 二叉排序树的平均查找长度： 45 24 12 37 53 93 (45, 24, 53, 12, 37, 93) 53 45 12 24 37 93 折半查找判定树 二叉排序树 插入的 n 个元素从一开始就有序， —— 变成单支树的形态！ 此时树的深度为 n; ASL = (n + 1) / 2 查找效率与顺序查找情况相同。 含有 n 个结点的二叉排序树的平均查找长度和树的形态有关 与折半查找中的判定树相同。 （形态比较均衡）。树的深度为：?log 2n ? + 1; 45 24 12 37 53 93 45 24 12 37 53 93 最坏情况 最好情况 有 n 个关键字的二叉排序树的平均查