典型查找算法编程.ppt

典型查找算法编程
现在学习的是第1页，共30页
第8章 典型查找算法
实例：学生分配座位
静态查找
动态查找
散列查找
本章总结
现在学习的是第2页，共30页
实例：学 L，表中元素的下界为0，-1。[mid](mid=（(上界+下界)/2）的关键字同给定值K进行比较。若相等，则查找成功，返回该元素的下标mid；若K<[mid].key，则说明待查元素若存在只能在左子表(下标从0到mid－1的范围)中，只要在左子表中继续折半查找即可；若K>[mid].key，则说明待查元素若存在只能在右子表(下标从mid+1到n－1的范围)中，只要在右子表中继续二分查找即可。重复执行，直到找到关键字为K的元素或当前查找区间为空(即表明查找失败)为止。
现在学习的是第13页，共30页
实现算法： （略）
二叉判定树：表示折半查找的查找过程。树中的每个结点表示表中一个元素，每棵子树的根结点表示当前查找区间的中间点元素，它的左子树和右子树分别对应该区间的左子表和右子表。
二叉判定树是一棵二叉排序树。
二分查找的平均查找长度为：
现在学习的是第14页，共30页
分块查找
分块查找(索引顺序查找) 基本思想：
首先把一个线性表(即主表)按照一定的函数关系或条件划分成若干个逻辑子表，为每个子表分别建立一个索引项，由所有子表的索引项构成一个索引表。当进行分块查找时，先根据所给的关键字查找索引表，从中查找出给定值K刚好小于等于索引值的那个索引项，找到待查块，然后再到主表中查找该块，从中查找待查的记录。

实现算法： （略）
索引表是有序的，所以在索引表上既可以采用顺序查找，也可以采用折半查找，而每个块中的记录排列是任意的，所以在块内只能采用顺序查找。
现在学均查找长度为：
设将长度为n的表均匀分成b块，每块有s个记录，则b=[n/s]，查找表中每条记录的概率相等，则每块查找的概率为1/b，块中每条记录的查找概率为1/s。则顺序查找索引表时：
现在学习的是第16页，共30页
动态查找
二叉排序树查找
二叉平衡树
动态查找表特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功；否则插入关键字为key的元素。
现在学习的是第17页，共30页
二叉排序树查找
二叉排序树(二叉搜索树、二叉查找树) ：
或者是一棵空树，或是一棵有如下特性的非空二叉树：
l   若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字。
l   若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字。
l  左、右子树本身又各是一棵二叉搜索树。
结论：二叉排序树中序遍历得到的必是一个有序序列。
现在学习的是第18页，共30页
二叉排序树的查找过程（递归查找过程）：
查找一个给定值为k的结点，若二叉树不为空，首先将它与根结点进行比较，若K与根结点相等，查找成功；若K小于根结点，则表示若K存在，应在其左子树中；否则若K存在，应在其右子树中。对左、右子树同样按上述过程先与子树的根结点进行比较，根据比较的结果定下一步的操作。若在查找过程中遇到叶子结点，还没有找到待找结点，则表示二叉排序树中不存在该结点，查找不成功。
实现算法： （略）
现在学习的是第19页，共30页
时间复杂度：
分析：在二叉排序树上进行查找的过程中，根结点为待查结点时，给定值同树中结点的比较次数仅为一次，待查结点位于最后一层时，比较的次数为树的深度。
普通情况下，对二叉排序树进行查找的时间复杂度为O( )；
最差情况下(二叉排序树为一棵单支树)，其时间复杂度为O(n)。
现在学衡树
二叉平衡树(AVL树)：
或者是一棵空树，或者是一棵具有如下性质的非空二叉树：
它的左子树和右子树都是二叉平衡树，且左子树和右子树的深度之差的绝对值不大于1。二叉平衡树中结点的左子树的深度减去它的右子树的深度的值定义为平衡因子BF，则BF的值只可能为－1、0和1。
现在学习的是第21页，共30页
对二叉排序树插入结点而构造平衡二叉树的规律：
设最小子树根结点的指针为a，则失去平衡后进行调整的规律：
LL型：单向右旋平衡处理
RR型：单向左旋平衡处理
LR型：双向旋转(先左后右)平衡处理
RL型：双向旋