数据结构与算法_第九章讲解.ppt

第9章 查找;查找的基本概念 ;平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：;9.1 静态查找表 ;静态查找表的顺序存储结构： typedef struct{ ElemType *elem; //数据元素存储空间基址，0号单元留空 int length /* 表长度 */ } SSTable;;9.1.1 顺序表;算法分析(顺序表) 查找成功时的平均查找长度ASL成功为： ASL= ? PiCi = 1/n* (n-i+1) = (n+1)/2 (约表长的一半) 查找失败时的平均查找长度ASL失败显然为 n+1 ;9.1.2有序表的查找;查找21;查找71;二分查找算法如下： int Search_Bin ( SSTable ST, KeyType key ) { // 算法9.2 // 在有序表ST中折半查找其关键字等于key的数据元素。 // 若找到，则函数值为该元素在表中的位置，否则为0。 int low, high, mid; low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if (EQ(key , ST.elem[mid].key)) return mid; // 找到待查元素 else if (LT(key, ST.elem[mid].key)) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin; 算法分析 查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示： ◆ 根结点就是第一次进行比较的中间位置的记录； ◆ 排在中间位置前面的作为左子树的结点； ◆ 排在中间位置后面的作为右子树的结点； 对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。 ② 将二叉判定树的第?㏒2n?+1层上的结点补齐就成为一棵满二叉树，深度不变。;折半查找的性能分析;9.1.4索引顺序表的查找 ;算法示例;9.2 动态查找表;381;二、二叉排序树的查找算法;三、二叉排序树的插入算法 ;下图是调用上述插入函数依次插入数据元素 4,5,7,2,1,9,8,11,3的过程。;删除二叉排序树的结点;删除二叉排序树结点的算法;二叉排序树删除算法(方案2);2.平衡二叉树的定义;平衡化旋转;一、 LL型平衡化旋转; 用b取代a的位置，a成为b的右子树的根结点，b原来的右子树作为a的左子树。 ⑶ 插入后各结点的平衡因子分析 ① 旋转前的平衡因子 设插入后b的左子树的深度为HbL，则其右子树的深度为HbL-1； a的左子树的深度为HbL+1。;② 旋转后的平衡因子 a的右子树没有变，而左子树是b的右子树，则平衡因子是：HaL- HaR=(HbL-1)-(HbL-1)=0 即a是平衡的，以a为根的子树的深度是HbL。 b的左子树没有变化，右子树是以a为根的子树，则平衡因子是： HbL-HbL=0 即b也是平衡的，以b为根的子树的深度是HbL+1，与插入前a的子树的深度相同，则该子树的上层各结点的平衡因子没有变化，即整棵树旋转后是平衡的。;二、 LR型平衡化旋转;（2） 平衡化旋转方法 先以b进行一次逆时针旋转(将以b为根的子树旋转为以c为根)，再以a进行一次顺时针旋转，如图9-8所示。将整棵子树旋转为以c为根，b是c的左子树，a是c的右子树；c的右子树移到a的左子树位置， c的左子树移到b的右子树位置。;(3) 插入后结点c的平衡因子的变化分析 ① 插入后c的平衡因子是1：即在c的左子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL-1；b插入后的平衡因子是-1，则b的左子树的深度为HcL，以b为根的子树的深度是HcL+2。 因插入后a的平衡因子是2 ，则a的右子树的深度是HcL。; ② 插入后c的平衡因子是0：c本身是插入结点。设c的左子树的深度为HcL，则右子树的深度也是HcL；因b插入后的平衡因子是-1，则b的左子树的深度