算法与数据结构查找.ppt

BUPTSCSTBUPT[2.插入]首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。[3.生成][算法步骤]反复执行以下操作a.读入一个记录，设其关键字为K；b.调用查找算法，确定插入位置；c.调用插入算法，实施插入结点的操作；第23页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT例：将序列122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099第24页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT[4.删除]依据被删除结点p的不同情况分析：1.p是叶子结点：修改其双亲指针即可2.p只有左孩子：用p的左子树代替以p为根的子树p只有右孩子：用p的右子树代替以p为根的子树3.p有两个孩子：找到p的中序后继(或前趋)结点q，q的数据复制给p，删除只有右子(或左子)/无孩子的q第25页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT例：(1)(2)(2)(3)5320901050869541241528891304539878992第26页，共70页，星期日，2025年，2月5日BUPTSCSTBUPTvoidDelete(BSTreeT,keytypeX)//在二叉排序树T上，删除为X的结点。{BSTreef,p=T;while(pp-key!=X)//查找值为X的结点if(p-keyX){f=p;p=p-lc;}//f为p的双亲else{f=p;p=p-rc;}if(p==NULL){printf(“无关键字为X的结点\n”);exit(0);}if(p-lc==NULL)//被删结点无左子树if(f-lc==p)f-lc=p-rc;//将被删结点的右子树接到其双亲上elsef-rc=p-rc;else{//被删结点有左子树q=p;s=p-lc;while(s-rc!=NULL){//查左子树中最右下的结点（中序最后结点）q=s;s=s-rc;}p-key=s-key;//结点值用其左子树最右下的结点的值代替if(q==p)p-lc=s-lc;//被删结点左子树的根结点无右子女elseq-rc=s-lc;//s是被删结点左子树中序序列最后一个结点free(s);}}第27页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT[4.性能分析]给定树的形态，等概率查找成功时的ASL=?ci/n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：?1+4log2n关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树第28页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT8.7平衡二叉树(AVL树)[1.定义]平衡二叉树或者是空树，或者是满足如下性质的二叉排序树：1)它的左、右子树的高度之差的绝对值不超过1；2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子：该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二叉树：每个结点的平衡因子都为＋1、－1、0的二叉排序树。第29页，共70页，星期日，2025年，2月5日BUPTSCSTBUPT[2.结点的存储结构]lc