第七章查找技术.doc

第七章 查找技术 一、基本术语 1.记录/关键码：查找问题中的数据元素称为记录；标识一个记录的某个数据项称为关键码；能唯一标识一个记录的关键码称为主关键码 2.查找：在具有同类型记录的集合中找出给定条件的记录 3.静态查找：不涉及插入和删除操作的查找 4.动态查找：设计插入和删除操作的查找 5.查找结构：专门为查找操作设计的数据结构 ??(1)线性表：适用静态查找，主要采用顺序查找技术、折半查找技术 ??(2)树表：适用动态查找，主要采用二叉排序树查找技术 ??(3)散列表：适用静态查找和动态查找，主要采用散列技术 6.查找算法的时间性能：用平均查找长度来度量(关键码比较次数的期望) ??(1)对于查找成功：平均查找长度=查找成功对应的关键码比较次数=所有结点的比较次数之和/结点的个数 ??(2)对于查找失败：平均查找长度=查找失败对应的关键码比较次数=所有外结点的比较次数之和/外结点的个数 二、线性表的查找技术 1.顺序查找：应用于顺序存储和链式存储，平均查找长度为O(n) 2.折半查找：要求表中记录按关键码有序并采用顺序存储，平均查找长度为O(log2n) 3.折半查找判定树 ??(1)判定树：描述折半查找过程的的二叉树，称为折半查找判定树，简称判定树，一个结点对应一个记录，结点的值对应记录在表中的位置 ??(2)判定树的构造方法： ????第一步：确定结点值的区间：若有序表长度为n，则结点值的区间为[1,n] ????第二步：确定根结点的值：mid=(1+n)/2； ????第三步：确定左子树的区间：[1,mid-1]，和右子树的区间：[mid+1,n]； ????第四步：确定左、右子树根结点的值：左mid=(1+mid-1)/2；右mid=(mid+1+n)/2；返回第三步 ??(3)判定树的性质： ?????①判定树是二叉排序树，且结点个数相同的判定树一样 ?????②任意两个叶子所处层数最多差1，n个结点的判定树的深度为[long2n]+1 ??(4)判定树的平均查找长度 ????结点的比较次数=该结点所在层数 ????外结点：在每个结点的空指针域加上一个实际不存在的结点，长度为n的有序表有n+1个外结点? ? ?? 外结点的比较次数=外结点的根结点所在层数 ?? ?①查找成功时的平均查找长度=所有结点的比较次数之和/有序表的长度 ??? ②查找失败时的平均查找长度=所有外结点的比较次数之和/外结点的个数 4.示例：画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度 树表的查找技术 1.二叉排序树：左子树结点值比根结点小，右子树结点值比根结点大 2.二叉排序树的构造方法： ??第一步：从空树构造一棵二叉排序树，将第一个关键码作为二叉排序树的根结点 ??第二步：依次插入结点，满足左比根小、右比根大的规则 3.二叉排序树中删除结点的方法： ??第一步：找到一个大于待删除结点的最小值或小于待删除结点的最大值的结点s ??第二步：用结点s替换待删除结点 ??第三步：删除结点s 4.平衡二叉树 ??(1)平衡二叉树：二叉排序树中所有结点的左右子树深度最多相差1 ???结点的平衡因子：该结点的左子树深度-右子树深度 ? ? 最小不平衡子树：以距离插入结点最近且平衡因子绝对值大于1的结点为跟的子树 ??(2)构造平衡二叉树的方法 ????第一步：插入一个结点，计算此时所有结点的平衡因子， ????????若不存在绝对值大于1，则没有失去平衡，返回第一步； ????????若发现某结点的平衡因子绝对值大于1，进入第二步； ????第二步：找出最小不平衡子树的根结点A，判断新插结点与根结点A是下面哪种类型 的调整，并做相应调整 ????? LL型：新插结点在A的左孩子的左子树上----顺时针旋转最小不平衡子树，调整 最小不平衡子树的支撑点 ?? ???RR型：新插结点在A的右孩子的右子树上----逆时针旋转最小不平衡子树，调整 最小不平衡子树的支撑点 ????? LR型：新插结点在A的左孩子的右子树上----先逆时针旋转左孩子，调整左孩子 的支撑点；再顺时针旋转最小不平衡子树，调整最小不平衡子树的支撑点 ????? RL型：新插结点在A的右孩子的左子树上----先顺时针旋转右孩子，调整右孩子 的支撑点；再逆时针旋转最小不平衡子树，调整最小不平衡子树的支撑点 ??? 第三步：计算此时所有结点的平衡因子， ???????若不存在绝对值大于1，则调整成功，返回第一步； ???????若发现某结点的平衡因子绝对值大于1，返回第二步，继续调整； ? 散列表的查找技术 1.散列技术：在记录的存储位置和关键码之间建立一