软件技术基础课件

15-13.4

二叉排序树及其查找1.二叉排序树（二叉查找树）的定义

二叉排序树或者是一棵空树，或者是满足下述要求的二叉树： (递归定义)(1)若它的左子树非空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树非空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左右子树本身也是二叉排序树。4553100619078123372415-2二叉排序树的构造按二叉排序树的定义规则依次将待排数据插入二叉树二叉排序树的形态与初始序列有关，最坏情况为一单支树15-3二叉排序树的插入template<classT>voidBS_Tree<T>::insert_BS_Tree(Tx){BSnode<T>*p,*q;p=newBSnode<T>;p->d=x;p->lchild=NULL;p->rchild=NULL;q=BT;if(q==NULL)BT=p;else{while((q->lchild!=p)&&(q->rchild!=p)){if(x<q->d){if(q->lchild!=NULL)q=q->lchild;elseq->lchild=p;}else{if(q->rchild!=NULL)q=q->rchild;elseq->rchild=p;}}}return;}15-4二叉排序树的删除要求：删除任意结点后，仍然保持二叉排序树的特征。叶结点可直接删除只有右子树18302326121413qp183023261413q15-5二叉排序树的删除只有左子树18

302326121413qp182326121413q15-6二叉排序树的删除左右子树均有，方案一18302327121413qp28251430232713122825Pr直接链接到qr上深度增加15-7二叉排序树的删除左右子树均有，方案二

18302327121413qp282514302327122825P的直接中序（q所指）前趋代替P1315-8二叉排序树的删除左右子树均有，方案三

18302327121413qp2825233027122825P的直接中序（q所指）后继代替P141315-9基本思想类似于对分查找，从根结点开始走一条到待查结点的一条查找路径，直至查找成功或不成功。

将key与根结点的关键字比较：二叉排序树的查找45531006190781233724若key=

根结点的关键字,查找成功，返回该结点的指针；若key

根结点的关键字，在左子树中查找，递归调用；

若key

根结点的关键字，在右子树中查找，递归调用；Key=24查找成功！24

45：继续在左子树中查找24

12：继续在右子树中查找24

37：继续在左子树中查找15-10Template<classT>Bsnode<T>*BS_Tree<T>::search_BS_Tree(Tx){Bsnode<T>*p=NULL;

intflag;p=BT;flag=0;while((p!=NULL)&&(flag==0)){if(p->d==x)flag=1;elseif(x<p->d)p=p->lchild;elsep=p->rchild;}if(p==NULL){cout<<“找不到！”<<endl;return(p);}return(p);}算法实现15-11算法分析在一般情况下，此算法的时间复杂度为ASL=(1*1+2*2+3*4+4*3)/12=2.9

但是ASL与树的形状有关：对于一组数据组成的树：

{40,17,57,09,53,22,89,28,15,45}15-12对于同样一组数据，由于排列顺序不同：{15,57,09,53,89,45,40,28,22,17}ASL=(1*1+2*2+3*2+4*1+5*1+6*1+7*1+8*1)/10=4.1由此可见，为了得到较好的平均查找长度，需要对二叉排序树进行进一步的处理。这就是二叉排序树的平衡化的处理15-13二叉排序树的平衡化处理HL-HRHL-HR||||||---15-14平衡化处理15-15LL型平衡旋转(1)A的左子树

B的右子树,改A的平衡因子为0(2)B的右子树

A,改B的平衡因子为03.3.3-13.3.3-23.3.3-13.3.3-13.3.3-2+1+215-16RR型平衡旋转-1-2(1)A的右子树

B的左子树,改A的平衡因子为0(2)B的左子树

A,改B的平衡因子为0015-17LR型平衡旋转图3.3.3-33.3.3-33.3.3-4图3.3.3-4123+1+23.3.3-33.3.3-415-18算法描述：(1)B的右子树C上升为根节点;(2)A的左子树

C的右子树;B的右子树C的左子树;(逆旋)(3)C的右子树A;C的左子树B;(顺旋)处理平衡因子:(4)如果C的平衡因子=1;则A的平衡因子-1;B的平衡因子0;(5)否则:

如果C的平衡因子=-1;则A的平衡因子0;B的平衡因子1;(6)C的平衡因子0;输出新树根节点C;结束。123+1+2

15-19RL型平衡旋转-1-23.3.3-4图3.3.3-4132

3.3.3-4-1→-215-20算法描述：(1)A的右子树B上升为根节点;(2)A的右子树

B的左子树;C的左子树B的右子树;(顺旋)(3)B的左子树A;B的右子树C;(逆旋)