第九章 查找.pptVIP

第九章 查 找 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.3 动态查找表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 9.4 哈希表 第九章 查找小结 第九章 习 题 结束 第 * 页 * 第九章 查找 9.1 概述 9.2 静态表查找表 9.3 动态表查找表 9.4 哈希表 9.3 动态查找表? 如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供1）、2）两种查找外，还要提供动态查找功能： 3）? 查找某个“特定”元素是否在表中，若不在，则将该元素插入表中；4）??查找某个“特定”元素是否在表中，若在，从表中删除该元素； 如何组织动态查找表？ 线性表：顺序查找效率低 有序表：二分查找法须用顺序结构存储有序表，插入删除操作要移动元素； 本节介绍动态查找表的一种组织形式——二叉排序树 1? 二叉排序树的概念二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； 45 53 100 61 90 78 12 3 37 24 二叉排序树 2 二叉排序树的查找 在二叉排序树中查找关键字为key的记录 基本思想 若二叉排序树为空树，查找失败，返回null或 0； 否则，将key与根结点的关键字比较： 若key = 根结点的关键字,查找成功，返回该记录在二叉排序树 中的位置； 若key ? 根结点的关键字，继续在左子树中查找； 若key ? 根结点的关键字，继续在右子树中查找； 例 在如下二叉排序树中查找关键字为24的记录 45 53 100 61 90 78 12 3 37 24 24?45 继续在左子树中查找 24?12 继续在右子树中查找 24?37 继续在左子树中查找 Key=24 查找成功！ 45 53 100 61 90 78 12 3 37 24 例 在如下二叉排序树中查找关键字为60的记录 查找失败！ 查找路径 左子树为空 算法 BiTree SearchBST(BiTree T, KeyType key) { //二叉排序树用二叉链表存储。在根指针T所指二叉排序树中递归地查找//关键字等于key的记录，若查找成功，则返回该记录结点的指针，否则 //返回空指针 if(!T)|| EQ(key, T-data. key) return(T); // 若T为空或查找成功，返回 else if LT(key, T-data. key) return(SearchBST(T-1child, key)); //在左子树中继续查找 return(SearchBST(T-rchild, key)) //在右子树中继续查找 }//SearchBST 61 90 100 53 45 78 12 3 37 24 45 53 100 61 90 78 12 3 37 24 性能分析：二叉排序树的查找效率与树的形态有关，若树的形态为“单枝”，二叉排序树的查找就“退化”为顺序查找；若树的形态比较“平衡”，二叉排序树的查找与二分查找类似； 为获得较高的查找效率，需要构造“平衡”的二叉排序树。关于如何构造平衡二叉树，有兴趣的同学可参见课本P233-238。 3 二叉排序树的插入、删除 二叉排序树是动态查找表的组织形式,动态查找表要提供插入删除数据元素的操作。 在一般二叉树的基本操作中只有插入、删除子树操作，没有插入、删除结点操作。原因是；除了叶子结点外，在二叉树中插入、删除结点将破坏树的结构。 下面介绍如何在二叉排序树的插入、删除。二叉排序树是作为动态查找表的组织形式，目的是获得较高的查找效率并且能方便地进行插入删除操作。因此在二叉排序树中插入、删除结点的原则是：插入、删除结点后仍是二叉排序树。 1）二叉排序树的插入 新插入的结点为叶子结点，并且是查找