第8章B--数据结构课件(吴伟民-严蔚敏编著).ppt

《第8章B--数据结构课件(吴伟民-严蔚敏编著).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、周四之前请完成作业：第八章查找自测卷全部内容课外活动：对AOE网的讨论第七章图自测卷全部内容18.1基本概念8.2静态查找表8.3动态查找表8.4哈希查找表第8章查找教材第8、11和12章省略，因《操作系统》课程会涉及。2特点：一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树8.3动态查找表表结构在查找过程中动态生成。要求：对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。典型的动态表———二叉排序树3三、二叉排序树

2、的查找分析最坏情况：即插入的n个元素从一开始就有序。（单支树）此时树深为n;ASL=(n+1)/2;与顺序查找情况相同。最好情况：即：与折半查找中的判定树相同（形态均衡）此时树深为：log2n+1；ASL=log2(n+1)–1；与折半查找情况相同。一般情况：（与logn同阶）问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡平衡二叉树4四、平衡二叉树平衡二叉树又称AVL树，它是具有如下性质的二叉树：为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平

3、衡因子balance。这样，可以得到AVL树的其它性质：即

4、左子树深度-右子树深度

5、≤1左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤15(a)平衡树(b)不平衡树例：判断下列二叉树是否AVL树？任一结点的平衡因子只能取：-1、0或1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。00011-1-120001-16如果在一棵AVL树中插入一个新结点

6、，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转7若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：8若在A的右子树的左子树上插入结点，使A的平衡因子

7、从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：这种调整规则可以保证二叉排序树的次序不变9013037024例：请将下面序列构成一棵平衡二叉排序树：（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-13

8、7053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053108.4哈希查找表一、哈希表的概念二、哈希函数的构造方法三、冲突处理方法四、哈希表的查找及分析11一、哈希表的概念哈希表：即散列存储结构。散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！例1：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V[01]单元；将200101181

9、0202的所有信息存入V[02]单元；……将2001011810231的所有信息存入V[31]单元。欲查找学号为2001011810216的信息，便可直接访问V[16]！12例2：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。（注：H（k）＝k称为散列函数）解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：讨论：如何进行散列查找？根据存储时用到的散列函数

10、H(k)表达式，迅即可查到结果！例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。地址…9…11…14…232425…39…内容14119232539缺点：空间效率低！13选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。通常关键码的集合比哈希地址集合大得多，因而经过哈