第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平衡旋转