第九章_查找 课1.ppt

* 9.2 动态查找树表 （2）被删除的结点只有左子树或者只有右子树 由左子树或右子树取代被删结点。 * 9.2 动态查找树表 删除数据值为 99 的结点。 * 9.2 动态查找树表 删除数据值为 200 的结点。 * 9.2 动态查找树表 （3）被删除的结点既有左子树，也有右子树，则 通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针值为空) 或右子树中最小的结点(被删结点的右子树中的最左的结点，其左儿子指针值为空) 要点：维持二叉分类树的特性不变。在中序遍历中紧靠着被删结点的结点才有资格作为“替身” * 9.2 动态查找树表 （3）被删除的结点既有左子树，也有右子树 * 9.2 动态查找树表 （3）被删除的结点既有左子树，也有右子树 200 250 300 110 99 105 230 216 400 450 500 200 250 300 110 99 105 230 216 400 450 500 * 9.2 动态查找树表 结论： 先将替身的数据值复制到被删结点 将原替身的另一儿子作为它的父亲结点的儿子，究竟是作为左儿子还是右儿子依原替身结点和其父亲结点的关系而定。 释放原替身结点的空间。 * 9.2 动态查找树表 结论： PL、PR皆空，直接删除 PL或PR为空 PL为空，删除后的情况 * 9.2 动态查找树表 结论：PL、PR皆不空 * F C CL S SL QL P PR Q PR F C CL S SL QL P PR Q 法2: F C CL S SL QL P PR Q 法1: 例：请从下面的二叉排序树中删除结点P。 S SL * 10 3 6 2 4 18 12 15 6 3 4 2 18 12 15 删除10 * 1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 ?log2 n?+1 2) 一棵二叉排序树的平均查找长度为： 三、二叉排序树的查找分析 其中： ni 是每层结点个数； Ci 是结点所在层次数； m 为树深。 最坏情况：即插入的n个元素从一开始就有序， ——变成单支树的形态！ 此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。 * 最好情况：即：与折半查找中的判定树相同（形态比较均衡） 树的深度为：?log 2n ? +1 ； ASL=log 2(n+1) –1 ；与折半查找相同。 * 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。 2. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。 3. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。 作 业 * 作 业 二．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？ （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 * 作 业 三. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 作业请在第九章全部讲完后一起交。 * 9.1 静态查找表 例：查找 key = 5 的结点所在的数组元素的下标地址 * 9.1 静态查找表 * 9.1 静态查找表 * 9.1 静态查找表 * 9.1 静态查找表 int Search_bin ( SStable ST, KeyType key ) // 在有序表中查找关键字之值为 key 的结点，找到返回该结点在表中的下标地址，否则返回 0 { low = 1 ; high = ST.length ; while ( low = high ) { mid = ( low + ligh ) / 2 ; if ( EQ(S