第6章查找表.ppt

第 6 章 查找表 6.1 基本概念 6.1.2 查找表的基本概念 6.2 静态查找表的实现6.2.1 顺序表上的查找 6.2.2 有序表上的查找(二分查找) 6.2.3 索引顺序表上的查找 6.3 树表 6.3.1 二叉排序树 2．二叉排序树的插入 3．二叉排序树的删除 6.3.2 平衡二叉排序树 6.4 散列表 6.4.1 散列函数的构造法 6.4.2 动态查找表在开散列表上的实现(拉链法) 6.4.3 动态查找表在闭散列表上的实现 1. 线性探测法 2. 二次探测法 3. 多重散列法(略)4. 公共溢出区法(略) 6.4.4 开散列表与闭散列表的比较 ∧ ∧ ∧ ∧ ∧ ∧ 11 12 10 9 8 7 6 5 4 3 2 1 0 ∧ 13 15 ∧ 68 ∧ 44 ∧ 49 ∧ 41 06 ∧ 19 64 38 ∧ 25 12 对任何键值K，设H(K)=d，再设闭散列表的容量为m，则线性探测法生成的后继散列地址序列为　　　　　?d+1, d+2, ... , m-1 , 0 , ... , d-1　用线性探测法生成后继散列地址计算简单，但同时也引出新的问题。例如，当需插入K1而发生冲突时，若位置d+1空闲，K1将被存入此位置。假如后来又要插入K2，且H(K2)=d+1,结果，本来不是同义词的K1与K2反而发生了“冲突”。这种非同义词之间对同一个散列地址的争夺现象称为“堆积”。 1．二叉排序树上的查找 (1)若查找树为空，则查找失败；(2)若查找树非空，将给定值与查找树的根结点关键码比较； (3)若相等，则查找成功；否则 ①若给定值小于根结点关键码，则继续在左子树上进行查找； ②若给定值大于根结点关键码，则继续在右子树上进行查找。 50 30 80 20 90 85 40 35 88 32 例如: 二叉排序树 查找关键码 == 50 , 50 50 35 , 50 30 40 35 50 90 , 50 80 90 95 , 在二叉排序树上进行插入的原则是： (1)必须保证插入一个结点之后仍为一棵二叉排序树。 (2)仅当二叉排序树上不存在键值等于 K 的结点时才插入一个这样的结点。 因此，插入算法必须包含查找过程；并且当查找不成功时实施插入新结点的操作。 ●在动态查找表的定义中没有生成运算，只有初始化运算。这是因为动态查找表是从空表开始经反复的插入(及删除)而动态生成的。另一方面，假如需要的话，可以通过调用初始化算法和插入算法而实现生成运算。 63 55 90 42 98 10 67 58 45 83 从空树开始建立二叉排序树的过程 70 【例】已知关键码序列为: 63,90,70,55,67,42,98,83,10,45,58 建立一棵二叉排序树的过程 与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 可分三种情况讨论： (1)被删除的结点是叶子； (2)被删除的结点只有左子树或只有右子树； (3)被删除的结点既有左子树，也有右子树。 50 30 80 20 90 85 40 35 88 32 (1)被删除的结点是叶子结点 例如: 被删关键码 = 20 88 其双亲结点中相应指针域的值改为“空” 50 30 80 20 90 85 40 35 88 32 (2)被删除的结点只有左子树 或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 被删关键码 = 40 80 50 30 80 20 90 85 40 35 88 32 (3)被删除的结点既有左子树，也有右子树 40 40 以其前驱替代之，然后再删除该前驱结点 被删结点 前驱结点 被删关键码 = 50 可以证明，在随机情况下，含有n个结点的二叉排序树的平均查找长度为 1+4log2n 其时间效率很高。同时，其它运算如插入和删除亦易于实现。相对而言，有序表上的二分查找效率也很高；但若在有序表上进行插入和删除显然十分不便且低率。 33 32 6 23 21 23 21 6 32 33 图6-8?单支二叉排序树示例 二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵深度为n的单支树时，查找算法退化为顺序查找，平均查找长度上升为(n+1)/2。为了避免出现这种情况，需要在二叉排序树的动态变化过程中随时调整其形态，使之保持“平衡”。当二叉排序树的形态比较匀称时，它的平均查找长度接近于log2n。 ●一棵平衡二叉排序树(简称AVL树)或者是一棵空树，或者是一棵任一结点的左子树与右子树的高度至多差1的二叉排序树。 ●对于二叉排序树上的任何结点，其平衡因子定义为该结点左子树的高度减去