南邮数据结构上课-dsb第7章-新二叉平衡树

7.2二叉平衡树

集合可以用二叉平衡树表示。是一种特殊的二叉搜索树，它能有效地控制树的高度，避免产生普通搜索树的“退化”树形。注：只介绍二叉平衡树的插入，不介绍二叉平衡树的删除。第七章与搜索树7.2二叉平衡树7.2.1二叉平衡树的定义1.二叉平衡树的定义二叉平衡树又称AVL树（G.M.Adel’son-Vel’skii和E.M.Landis）。它或者是一棵空二叉树，或者是具有下列性质的二叉树：（1)它的左、右子树高度之差的绝对值不超过1；（2)它的左、右子树都是二叉平衡树。2.结点的平衡因子二叉树上结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。3.二叉平衡树的例子4.AVL搜索树

既是二叉搜索树又是AVL树。(具有平衡性和排序性)。在下面的讨论中，二叉平衡树（AVL树）是指AVL搜索树。AVL树可以采用普通二叉树的二叉链表存储，为了简化插入和删除操作，为每个结点增加一个平衡因子。程序7.6AVLNode类（二叉平衡树结点类）template<classT>structAVLNode{AVLNode(constT&x){element=x; lChild=rChild=NULL; bF=0;}Telement;intbF;bf:结点的平衡因子AVLNode*lChild,*rChild;};7.2.2二叉平衡树类程序7.7二叉平衡树类二叉平衡树可用于实现动态集。template<classT>classAVLTree:publicDynamicSet<T>定义动态集的派生类{public:AVLTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);

private:AVLNode<T>*root;ResultCodeInsert(AVLNode<T>*&p,T&x,bool&unBalanced);voidLRotation(AVLNode<T>*&s,bool&unBalanced);voidRRotation(AVLNode<T>*&s,bool&unBalanced);};//二叉平衡树的搜索和一般二叉树的搜索一样。下面介绍插入7.2.3二叉平衡树的平衡旋转1.二叉平衡树的插入

二叉平衡树的插入可先按普通二叉搜索树的插入方法插入结点。新结点设为q，但插入新结点后的新树可能不再是AVL树，这时需要重新平衡，使之仍具平衡性和排序性。插入后将影响从根到插入位置的路径上所有结点的平衡因子的值。如果被插入的结点在这条路径上某个结点的左子树上，那么该结点的平衡因子将加1，否则将减1。图中4个元素的插入分别代表4种不同情况：（1）插入25

树仍然是二叉平衡树，树高度加1（2）插入35树仍然是二叉平衡树（3）插入14树不再是二叉平衡树（4）插入44树不再是二叉平衡树一般情况，插入新结点后会影响从根结点到新结点的路径上所有结点的平衡因子。插入在某结点的左子树上，该结点的平衡因子+1，插入在某结点的右子树上，该结点的平衡因子-1，2.重新平衡

如果从根结点到插入位置的路径上所有结点的平衡因子均为0，那么插入后这棵树仍然是二叉平衡树，而高度加1。如果在这条路径上，某个结点的平衡因子不为0，但自它以下直至插入位置的所有结点的平衡因子都为0，则以该结点为根的子树将是有可能不平衡的最小子树s。重新平衡的范围局限于该子树。为讨论插入算法，作以下假定：（1）结点s是新插入结点q的具有非零平衡因子值(插入前的值)的最近的祖先。（2）新结点q已插在结点s的左子树上。（3）从结点s到新结点q的路径上所有结点（不含s）的平衡因子值均已修正。

我们只涉及新结点q插在结点s的左子树上的情况，其对偶（右子树上）的情况一样。下面分三种情况加以分析。（1）情况1

若插入前，从根结点到新结点q的插入位置的路径上所有结点的平衡因子值均为0，插入q后只需将根结点的平衡因子改为1，并且AVL树的高度加1。（2）情况2（s->bF=-1)

若新结点q插在结点s较矮的（左）子树上(这时有s->bf为-1)，则只需令s->bf为0即可。(3)情况3（s->bF=1)

新结点q插在s的较高的子树上。这时又可分为两种不同情况：

a）情况3a:LL-旋转(r->bF=1)新结点插在结点s的左子树的左子树上新结点插在结点s的左子树的左子树上，这时有s->bf为1且r->bf为1。重新平衡的操作及对平衡因子的修正如下。

r=s->lchild;if(r->bf==1){s->lchild=r->rchild;r->rchild=s;r->bf=s->bf=0;}b）情况3b:LR-旋转(r->b=-1)新结点插在结点s的左子树的右子树上，这时有s->b=+1且r->b=-1。重新平衡的操作如下。

1）r=s->lchild;2）u=r->rchild;3）r->rchild=u->lchild;4）u->lchild=r;5）s->lchild=u->rchild;6）u->rchild=s;1s1u-1r新结点插在结点s的左子树的右子树上，这时有s->b=+1且r->b=-1。重新平衡的操作如下。

r=s->lchild;u=r->rchild;r->rchild=u->lchild;u->lchild=r;s->lchild=u->rchild;u->rchild=s;根据u的平衡因子的值分三种情况修正s,r平衡因子switch(u->bf){case+1:s->bf=-1;r->bf=0;break;case0:s->bf=0;r->bf=0;break;case-1:s->bf=0;r->bf=+1;}u->bf=0;上面的讨论我们只涉及新结点q插在结点s的左子树上的情况，其对偶的情况(RR和RL)读者可比照上面的讨论自行分析。

LL旋转和RR旋转合称为单一旋转，LR旋转和RL旋转合称为双重旋转。例子按45,28,15,12,14,23顺序建立二叉平衡树。程序7.8左旋转函数template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced){AVLNode<T>*u,*r=s->lChild;if(r->bF==1){//LL旋转

s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子树的根

}Else{//LR旋转

u=r->rChild;r->rChild=u->lChild; u->lChild=r;s->lChild=u->rChild;u->rChild=s; switch(u->bF){ case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break; case-1:s->bF=0;r->bF=1;}s=u;//s指示新子树的根

} s->bF=0;//结点s的平衡因子为0 unBalanced=false;//结束重新平衡操作}1.AVL_Insert函数在集合上定义的Insert函数调用AVL_Insert递归函数，实现在集合中插入元素e，如果是重复元素，则返回false，否则返回true。

AVL_Insert递归函数的执行过程可叙述如下：(1)搜索新元素e的插入位置，并插入之；(2)修正从新结点到结点s的平衡因子；

(3)如果是情况一和二，则算法结束，否则调用LRotation或RRotation完成重新平衡以s为根的子树，包括适当修正平衡因子。7.2.4二叉平衡树的插入二叉平衡树的插入算法template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced){ResultCoderesult=Success;if(p==NULL){//插入新结点

p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element){//新结点插入左子树

result=Insert(p->lChild,x,unBalanced); if(unBalanced) switch(p->bF){ case-1:p->bF=0;unBalanced=false;break; case0:p->bF=1;break; case1:LRotation(p,unBalanced); }} elseif(x==p->element){//有重复元素，插入失败

unBalanced=false;x=p->element;result=Duplicate; } else{//新结点插入右子树

result=Insert(p->rChild,x,unBalanced); if(unBalanced) switch(p->bF){ case1:p->bF=0;unBalanced=false;break; case0:p->bF=-1;break; case-1:RRotation(p,unBalanced); } }returnresult;}

7.4.5二叉平衡树的删除

在二叉平衡树上删除结点，有可能导致二叉平衡树失去平衡，这样就需重新平衡，方法同插入。为简化算法，规定：删除最多只有一个孩子的结点。若删除的结点有两个孩子，则转化。

转化方法：用中序遍历次序下的后继结点代替，然后删除该后继结点。对一棵子树重新平衡后，可能会使该子树变矮而影响其双亲结点的平衡性，这样就需要检查其祖先结点的平衡性。用shorter记录对其双亲平衡性的影响，若shorter为false，则表示当前子树的高度不变，不会影响其双亲结点的平衡性；否则为true,会影响。分三种情况讨论：(1)情况1:p的平衡因子为0

删除后不影响平衡性，修改p的平衡因子。以p为根的子树高度不变，shorter为false,算法终止。(2)情况2:从p的较高的子树上删除1个结点修改p的平衡因子为0，删除后不影响平衡性，但以p为根的子树的高度变矮。可能会影响p的双亲结点为根的子树的平衡性。shorter为true。(3)情况3:从p的较矮的子树上删除1个结点要破坏以p为根的子树的平衡性，必须重新平衡。设r是p的较高子树的根。根据r的平衡因子的值，有三种做法：①r的平衡因子