数据结构课件09讲述.ppt

在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。 平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？ n = 0 空树 最大深度为 0 n = 1 最大深度为 1 n = 2 最大深度为 2 n = 4 最大深度为 3 n = 7 最大深度为 4 先看几个具体情况: 反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？ h = 0 N0 = 0 h = 1 h = 2 h = 3 一般情况下 N1 = 1 N2 = 2 N3 = 4 Nh = Nh-1 + Nh-2 + 1 利用归纳法可证得 Nh = Fh+2 - 1 因此，在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。 总之，含有 n 个结点的二叉平衡树能达到的最大深度 hn = log?(?5 (n+1)) - 2。 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 9.3 哈 希 表 前述查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 一、哈希表是什么？ 查找的效率取决于和给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零。 对于频繁使用的查找表，希望 ASL = 0。 只有一个办法：预先知道所查关键字在表中的位置 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。 若以下标为000 ~ 999 的顺序表表示之。 例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份)。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 分块查找过程需要分两步进行 （1）先确定待查记录所在的块(子表) 假设给定值K=38，则先将K依次和索引表中最大关键字进行比较，因为22﹤K﹤48，则关键字为38的记录若存在，必定在第二个子表中 （2）在块中顺序查找。 由于同一索引项中的指针指示第二个子表中的第一个记录是表中第七个记录，则自第七个记录起进行顺序查找，直到找到某个关键字的值等于K为止。假若此子表中没有关键字等于K的记录(例如：K=29时，自第六个记录起至第11个记录的关键字和K比较都不等)，则查找不成功。 9.2 动态查找表（树表）的查找 表结构在查找过程中动态生成 对于给定值key 若表中存在，则成功返回； 否则插入关键字等于key 的记录 二叉排序树 平衡二叉树 一、二叉排序树 （二叉查找树） 1．定义 2．查找算法 3．插入算法 4．删除算法 5．查找性能的分析 （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； 1．定义： 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树： （3）它的左、右子树也都分别是二叉 排序树。 （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； 50 30 80 20 90 10 85 40 35 25 23 88 例如: 是二叉排序树。 66 不 66 练习 45 12 53 3 37 24 100 61 90 78 3，12，24，37，45，53，61，78，90，100 递增 得到一个关键字的递增有序序列 练习 中序遍历二叉排序树后的结果有什么规律？ 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 通常，取二叉链表作为 二叉排序树的存储结构 typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; TElemType data; （1）若二叉排序树为空，则查找失败，返回空指针。 （2）若二叉排序树非空，将给定值key与根结点的关键