数据结构__查找叉树和平衡叉树.pptVIP

第9章 查找 9.2 动态查找表 一、二叉排序树的定义 二、二叉排序树的插入与删除 讨论1：二叉排序树的插入和查找操作 二叉排序树的查找插入算法如何实现？ 二叉排序树的静态查找思想 若二叉排序树为空，则查找失败. 否则，先拿根结点值与待查值进行比较，若相等，则查找成功. 若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤. 二叉排序树的动态查找算法 查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。（P228算法9.5（b）） 插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。（P228算法9.6） 二叉排序树的删除 要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针。 p只有左子树或右子树，只需用p的孩子代替p。 p左、右子树均非空。沿p左子树的根C的右子树分支找到S，S的右子树为空。 法1：令*p的左子树为 *f的左子树，*p的右子树为*s的右子树； 法2：令*s代替*p 将S的左子树成为S的双亲Q的右子树，用S取代p 。 若C无右子树，用C取代p。 例：请从下面的二叉排序树中删除结点P。 三、二叉排序树的查找分析 最好情况：即：与折半查找中的判定树相同（形态比较均衡） 四、平衡二叉树 1）LL平衡旋转： 3）LR平衡旋转： 例：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53） 作业 已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 (2) 若已经对表中元素进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 (3) 按表中元素顺序构造一棵平衡二叉排序树，画出每插入一个元素的示意图并标明类型(LL,RR,LR,RL)，并求其在等概率的情况下查找成功的平均查找长度。 * * 数据结构讲义 - 二叉树和平衡二叉树 特点： 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树 五、B-树和B+树 表结构在查找过程中动态生成。 要求： 对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回； 否则插入关键字等于key 的记录。 典型的动态表———二叉排序树 （a） （b） 练：下列2种图形中，哪个不是二叉排序树 ？ ----或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 讨论：对(a)中序遍历后的结果是什么？ 将数据元素构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高； ② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； ③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！ ——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90）， 24 53 45 12 90 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 则生成的二叉排序树形态不同： 查找成功，返回 查找成功，返回 查找算法 静态查找算法 动态查找算法（插入） 二叉排序树查找的算法实现 1)递归函数? NODE *search(t,x) NODE *t; char x; {if(t==NULL) return(NULL); ? else ? {if(t-data==x) return(t); if(x(t-data) return(search(t-lchild,x)); ?