第九章查找§9.1静态查找表顺序查找顺序查找无序表上的顺序查找平均查找长度无序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找有序表上的顺序查找：失败静态查找表有序顺序表上的折半查找有序顺序表上的折半查找有序顺序表上的折半查找有序顺序表上的折半查找：成功有序顺序表上的折半查找有序顺序表上的折半查找有序顺序表上的折半查找有序顺序表上的折半查找有序顺序表上的折半查找：失败有序顺序表上的折半查找折半查找算法折半查找法折半查找判定树折半查找判定树查找失败查找失败折半查找判定树折半查找算法折半查找判定树折半查找判定树n=11折半查找判定树n=11折半查找的效率分析折半查找的效率分析折半查找的效率分析索引顺序表的查找索引顺序表的查找：分块查找索引顺序表的查找：分块查找索引顺序表的查找：分块查找完全二叉树n=119.2动态查找表二叉排序树和平衡二叉树二叉排序树图示二叉排序树的查找运算二叉排序树的查找算法二叉排序树的插入运算二叉排序树的插入算法二叉排序树的特点二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算二叉排序树的删除运算删除两个子树均不空的*p结点删除两个子树均不空的*p结点typedefintdatatype;typedefstructnode/*二叉排序树结点定义*/{datatypekey;/*结点值*/structnode*lchild,*rchild;/*左、右孩子指针*/}bsnode;typedefbsnode*bstree;bstreedelbstree(bstreet,datatypex){/*在二叉排序树t中删除结点值为x的结点*/bstreep,q,child;bssearch1(t,x,&p,&q);/*查找被删结点*/if(q)/*找到了待删除结点*/{if(q->lchild==NULL&&q->rchild==NULL)/*情况1，待删结点为叶结点*/{if(p)/*待删除结点有双亲*/{if(p->lchild==q)p->lchild=NULL;elsep->rchild=NULL;}elset=NULL;/*待删结点为树根*/free(q);}else/*情况2，待删结点的左子树为空，用待删结点的右子树替代该结点*/if(q->lchild==NULL){if(p)/*待删结点的双亲结点不为空*/{if(p->lchild==q)p->lchild=q->rchild;/*q是其双亲结点的左儿子*/elsep->rchild=q->rchild;/*q是其双亲结点的右儿子*/}elset=q->rchild;free(q);}else/*情况3，待删结点的右子树为空，用待删结点的左子树替代该结点*/if(q->rchild==NULL){if(p)/*待删结点的双亲结点不为空*/{if(p->lchild==q)p->lchild=q->lchild;/*q是其双亲结点的左儿子*/elsep->lchild=q->lchild;/*q是其双亲结点的右儿子*/}elset=q->lchild;free(q);}else/*情况4，待删结点的左右子树均不为空，用右子树代替待删结点，同时将待删结点的左子树收为右子树中序首点的左儿子*/{child=q->rchild;while(child->lchild)/*找待删结点右子树中的中序首点*/child=child->lchild;child->lchild=q->lchild;/*将待删结点的左子树收为child的左孩子*/if(p)/*待删结点不是树根*/{if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elset=q->rchild;/*待删结点为树根*/free(q);}}returnt;}算法9.7基于二叉排序树的结点删除二叉排序树的查找性能二叉排序树的查找性能(续)二叉排序树的查找性能(续)二叉排序树的形态二叉排序树的形态(续)平衡二叉树概念G.M.Adelson-Velskii和E.M.Landis在1962年提出了动态保持二叉排序树平衡的一个有效办法，后称为Adelson方法。下面介绍Adelson方法如何将一个新结点k插入到一棵平衡二叉排序树T中去。（3）改组：改组以kj为根的子树除了满足新子树高度要和原来以kj为根子树的高度相同外，还需使改造后的子树是一棵