《数据结构》课程PPT教学课件（2012）第9章 查找 9.3 动态查找表 9.4 哈希查找表

第9章查找 9.1基本概念 9.2静态查找表 9.3动态查找表 9.4哈希查找表 教材第8、11和12章省略，因《操作系统》课程会涉及

1 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希查找表 第9章 查找 教材第8、11和12章省略，因《操作系统》课程会涉及

9.3 动态查找表 特点：表结构在查找过程中动态生成。 要求：对于给定值key, 若表中存在其关键字等于ky的记录，则查找成功返回； 否则插入关键字等于key的记录。 典型的动态表 二叉排序树 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树 区

2 特点： 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树 9.3 动态查找表 表结构在查找过程中动态生成。 要求： 对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回； 否则插入关键字等于key 的记录。 典型的动态表———二叉排序树

三、二叉排序树的查找分析 最坏情况：即插入的个元素从一开始就有序。（单支树） 此时树深为n；ASL=(n+1)/2；与顺序查找情况相同。 最好情况：即：与折半查找中的判定树相同 (形态均衡) 此时树深为：log2n」+1； ASL=log(n+1)-1；与折半查找情况相同。 一般情况： 寸2N<5I+T)Ww (与logn同阶) 思考：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 平衡二叉树

3 三、二叉排序树的查找分析 最坏情况：即插入的n个元素从一开始就有序。（单支树） 此时树深为n ; ASL= (n+1)/2 ; 与顺序查找情况相同。 最好情况：即：与折半查找中的判定树相同 （形态均衡） 此时树深为：log 2n  +1 ； ASL=log 2 (n+1) –1 ；与折半查找情况相同。 一般情况： n n ASL )ln 1  2(1+ （与 log n 同阶） 思考：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 平衡二叉树

平衡二叉树的特点： 任一结点的平衡因子只能取：-1、0或1。 例：判断下列二叉树是否AVL树？ 0 (a)平衡树 (b)不平衡树 对于一棵有n个结点的AL树，其高度保持在 0Iog2n)数量级，ASL也保持在0log2n)量级

4 (a) 平衡树 (b) 不平衡树 平衡二叉树的特点： 任一结点的平衡因子只能取：-1、0 或 1。 ❖ 对于一棵有n个结点的AVL树，其高度保持在 O(log2n)数量级，ASL也保持在O(log2n)量级。 例：判断下列二叉树是否AVL树？ 0 0 0 1 1 -1 -1 2 0 0 0 1 -1

如果在一棵AVL树中插入一个新结点，就有可能 造成失衡，此时必须重新调整树的结构，使之恢 复平衡。我们称调整平衡过程为平衡旋转。 平衡旋转可以归纳为四类： ÷LL平衡旋转 RR平衡旋转 LR平衡旋转 。RL平衡旋转 现分别介绍这四种平衡旋转

5 如果在一棵AVL树中插入一个新结点，就有可能 造成失衡，此时必须重新调整树的结构，使之恢 复平衡。我们称调整平衡过程为平衡旋转。 现分别介绍这四种平衡旋转。 平衡旋转可以归纳为四类： ❖ LL平衡旋转 ❖ RR平衡旋转 ❖ LR平衡旋转 ❖ RL平衡旋转

1)LL平衡旋转： 若在A的左子树的左子树上插入 结点，使A的平衡因子从1增加至 2,需要进行一次顺时针旋转。 以B为旋转轴 2)RR平衡旋转： 若在A的右子树的右子树上插入结 点，使A的平衡因子从-1增加至-2， B 需要进行一次逆时针旋转。 以B为旋转轴

6 若在A的左子树的左子树上插入 结点，使A的平衡因子从1增加至 2，需要进行一次顺时针旋转。 A B C A 若在A的右子树的右子树上插入结 点，使A的平衡因子从-1增加至-2， 需要进行一次逆时针旋转。 2）RR平衡旋转： A B A C 1）LL平衡旋转： 以B为旋转轴 以B为旋转轴

3)LR平衡旋转： 若在A的左子树的右子树上插入 结点，使A的平衡因子从1增加至 2,需要先进行逆时针旋转，再 顺时针旋转。 以插入的结点C为旋转轴 4)RL平衡旋转： 若在A的右子树的左子树上插入结 点，使A的平衡因子从-1增加至-2， 需要先进行顺时针旋转，再逆时 针旋转。 以插入的结点C为旋转轴 这种调整规则可以保证二叉排序树的次序不变

7 A B C 若在A的右子树的左子树上插入结 点，使A的平衡因子从-1增加至-2， 需要先进行顺时针旋转，再逆时 针旋转。 4）RL平衡旋转： A B C A B C A 若在A的左子树的右子树上插入 结点，使A的平衡因子从1增加至 2，需要先进行逆时针旋转，再 顺时针旋转。 3）LR平衡旋转： A B C 这种调整规则可以保证二叉排序树的次序不变 以插入的结点C为旋转轴 以插入的结点C为旋转轴 B A C

例：请将下面序列构成一棵平衡二叉排序树： (13,24,37,90,53) ↓↓↓↓°↓ 需要RL平衡旋转 2 (绕C先顺后逆) 13 24 1 0 0 需要RR平衡旋转 24 13 53 绕B逆转，B为根) 0 0 0 37 37 90 0 53 0 0 37 90

8 0 13 0 37 0 24 例：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53） 0 13 0 37 -1 0 24 -1 -2 13 需要RR平衡旋转 (绕B逆转,B为根） 0 90 -1 24 -1 37 0 53 1 90 -2 37 需要RL平衡旋转 (绕C先顺后逆） 0 37 0 90 0 53 0 37 0 90 0 53

9.4哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析 D

9 9.4 哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析

一、哈希表的概念 哈希表：即散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应 关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)),查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元： 将2001011810202的所有信息存入V[02]单元； 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]」

10 一、哈希表的概念 哈希表：即散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应 关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元； 将2001011810202的所有信息存入V[02]单元； . 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]！