数据结构（C语言版）最全课件完整版ppt全书电子教案全套教学教程PPT课件.ppt

Hash(key)=key mod p (p是一个整数) 关键：如何选取合适的p？ 技巧：设表长为m，取p≤m且为质数 除留余数法 （最常用重点掌握） ① 执行速度（即计算哈希函数所需时间）； ② 关键字的长度； ③ 哈希表的大小； ④ 关键字的分布情况； ⑤ 查找频率。 构造哈希函数考虑的因素 1.开放定址法 处理冲突的方法 2.链地址法 基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 1.开放定址法（开地址法） 线性探测法 二次探测法 伪随机探测法 Hi=(Hash(key)+di) mod m ( 1≤i m ) 其中：m为哈希表长度 di 为增量序列 1，2，…m-1，且di=i 一旦冲突，就找下一个空地址存入 线性探测法 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10 47 7 △ ▲ △ △ 29 11 16 92 22 8 3 ① 47、7、11、16、92没有冲突 ② Hash(29)=7，有冲突，由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入 ③ 3 连续移动了两次 线性探测法 线性探测法的特点 优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。 缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率。 解决方案：二次探测法 二次探测法 关键码集为 {47，7，29，11，16，92，22，8，3}， 设： 哈希函数为Hash(key)=key mod 11 Hi=(Hash(key)±di) mod m 其中：m为哈希表长度，m要求是某个4k+3的质数； di为增量序列 12，-12，22，-22，…，q2 0 1 2 3 4 5 6 7 8 9 10 8 29 7 16 92 47 3 22 11 △ ▲ △ △ Hash(3)=3，哈希地址冲突，由 H1=(Hash(3)+12) mod 11=4，仍然冲突； H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。 伪随机探测法 Hi=(Hash(key)+di) mod m ( 1≤i m ) 其中：m为哈希表长度 di 为随机数 step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找 到能用的存储地址为止。 开放地址法建立哈希表步骤 平均查找长度和二叉树的形态有关，即， 最好：log2n（形态匀称，与二分查找的判定树相似） 最坏: （n+1)/2（单支树） 查找的性能分析 40 24 55 12 37 12 24 37 40 55 问题：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值≤ 1 平衡二叉树 平衡因子:该结点左子树与右子树的高度差 1989奥斯卡是最佳短片奖--《Balance》 世界需要平衡，破坏平衡的一方，也许会一时很强势的称霸，最终的结局逃不过孤立和落空 任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树； 对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。 (a) 平衡树 (b) 不平衡树 练习：判断下列二叉树是否AVL树？ 0 0 0 1 1 -1 -1 2 0 0 0 1 -1 如果在一棵AVL树中插入一个新结点，就有