算法导论AVL树

1、算法导论思考题 P177: 13-3:AVL 树主要思路：实现AVL树的关键在于维持树的平衡性。为了保证平衡， AVL树中的每个结 点都有一个平衡因子，它表示这个结点的左、右子树的高度差，也就是左子树的 高度减去右子树的高度的结果值。AVL树上所有结点的平衡因子bal值只能是-1、 0、1。反之，只要二叉树上一个结点的 bal的绝对值大于1，则该二叉树就不是 平衡二叉树。每当插入一个节点或删除都有可能破坏了树的平衡性 。因此首先检查是否破 坏了树的平衡性，如果因插入结点而破坏了二叉查找树的平衡， 则找出离插入点 最近的不平衡结点，然后将该不平衡结点为根的子树进行旋转操作，称该不平衡 结点为旋转

2、根，以该旋转根为根的子树称为最小不平衡子树。要对树进行翻转， 以满足平衡性。翻转使用的方法是红黑树中提到的左旋和右旋。 根据出现的不同 情况对树进行旋转。归纳为4种旋转类型：LL型旋转、RR型旋转、LR型旋转、 RL型旋转。1、LL型旋转:樹入結点2、LR型旋转:Bl Cl Cr Am3、RR型旋转:插入结点Al Bl &4、RL型旋转:醫入结点(d)上图(a) (b) (c) (d)为四种类型的旋转图示证明:假设Nh是一颗高度为h的AVL树中最小的节点数:Nh Nh i Nh 21, No 0,Ni 1可以看到Nh的定义与斐波那契数列的定义非常相似FhFh i Fh 2, Fo 0,

3、 Fi1h f-)，则利用归纳法证明：当h 0时Nh斤2 1，而Fh八5 (其中Nhh 2 / < 5 1。反之，含有n个结点的平衡树的最大深度为log (、.5(n 1) 21.44log2(n 2) O(log n)。在平衡的的平衡二叉查找树 Bala need BST上插入一个新的数据元素 e的递 归算法可描述如下：(1)若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点， 树的深度增1； 若e的关键字和BBST的根结点的关键字相等，贝U不进行；(3)若e的关键字小于BBST的根结点的关键字，而且在 BBST的左子树中不 存在和e有相同关键字的结点，则将e插入在B

4、BST的左子树上，并且当插入之 后的左子树深度增加(+1)时，分别就下列不同情况处理之：a、BBST的根结点的平衡因子为-1 (右子树的深度大于左子树的深度，则将 根结点的平衡因子更改为0，BBST的深度不变；b、BBST的根结点的平衡因子为0 (左、右子树的深度相等)：则将根结点的 平衡因子更改为1，BBST的深度增1;c、BBST的根结点的平衡因子为1 (左子树的深度大于右子树的深度)：若 BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋 处理之后，将根结点和其右子树根结点的平衡因子更改为 0，树的深度不变；(4)若e的关键字大于BBST的根结点的关键字，而且在

5、BBST的右子树中 不存在和e有相同关键字的结点，则将e插入在BBST勺右子树上，并且当插入 之后的右子树深度增加（+1）时，分别就不同情况处理之。算法实现：#i nclude<stdio.h>#i nclude<malloc.h>#defi ne LH +1 / 左高#defi ne EH 0 /等高#defi ne RH -1 /右高typedef int ElemType;typedef struct BSTNodeElemType data;int bf;struct BSTNode *LChild,*RChild;BSTNode,*BSTree;/ LL型平衡

6、化旋转void L_Rotate(BSTree &p) /对以*p为根的二叉查找树作左旋处理，处理之后旋转处理之前的右子树的根结点BSTNode *rc;rc=p->RChild;p->RChild=rc->LChild;rc->LChild=p;p->bf=rc->bf=EH; /平衡因子修改p=rc;/p指向新的根结点/ RR 型平衡化旋转void R_Rotate(BSTree &p) /对以*p为根的二叉查找树作右旋处理，处理之后 旋转处理之前的左子树的根结点BSTNode *lc;lc=p->LChild;p->LChi

7、ld=lc->RChild;lc->RChild=p;p->bf=lc->bf=EH;p=lc;p指向新的树根结点，即H指向新的树根结点，即 void LeftBala nce(BSTree &T)指向新的根结点BSTree lc,rd;lc=T->LChild; /lc指向*T的左子树根结点switch(lc->bf) / 检查*T的左子树平衡度，并作相应平衡处理case LH: / 新结点插入在*T的左孩子的左子树上，需要作单右旋处 理T->bf=lc->bf=EH;R_Rotate(T);break;case RH: / 新结点插入

8、在*T的左孩子的右子树上，要作双旋处理rd=lc->RChild; /rd指向*T的左孩子的右子树的根switch(rd->bf) / 修改*T及其左孩子的平衡因子case LH:T->bf=RH;lc->bf=EH;break;case EH:T->bf=EH;lc->bf=EH;break;case RH:T->bf=EH;lc->bf=LH;break;rd->bf=EH;L_Rotate(T->LChild); /对*T的左子树作左旋平衡处理R_Rotate(T); /对*T作右旋平衡处理 void RightBalance(

9、BSTree &T)BSTree ld,rc;rc=T->RChild;rc指向*T的左子树根结点switch(rc->bf) case RH:T->bf=rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->LChild; switch(ld->bf)case LH:T->bf=EH; rc->bf=LH; break;case EH:T->bf=EH; rc->bf=EH; break;case RH:T->bf=RH; rc->bf=EH; break;ld->bf=E

10、H;R_Rotate(T->RChild); L_Rotate(T);break;int In sert_AVL(BSTree & T,ElemType e,bool & taller) /若在平衡的二叉树T中不存在和e有相同关键字的结点，则插入一个数据元 素为e的新结点，并返回1,否则返回0.若因插入而使二叉排序树失去平衡， 则 作平衡旋转处理，布尔变量taller 反映T长高与否if(!T) /插入新结点，树“长高”，置taller为trueT=(BSTree)malloc(sizeof(BSTNode);T->data=e;T->LChild=T->

11、;RChild=NULL;T->bf=EH; taller=true;else树中已存在和e有相同关键字的结点不再插入if(e=T->data) /taller=false; /return 0;if(e<T->data) /应继续在T的左子树中进行搜索未插入if(!Insert_AVL(T->LChild,e,taller) /return 0;if(taller) /已插入到T的左子树中且左子树“长高”switch(T->bf)/ 检查T的平衡度case LH:LeftBala nce(T);taller=false;break;case EH:T-&g

12、t;bf=LH;taller=true;break;case RH:T->bf=EH;taller=false;break;else/应继续在T的右子树中进行搜索if(!I nsert_AVL(T->RChild,e,taller) /未插入return 0;if(taller) /已插入到T右子树且右子树长高switch(T->bf)/ 检查T的平衡度case LH:T->bf=EH;taller=false;break;case EH:T->bf=RH;taller=true;break;case RH: /原本右子树比左子树高，需要作右平衡处理RightBa

13、la nce(T);taller=false;break;return 1;void In OrderTraverse(BSTree &T)if(T)In OrderTraverse(T->LChild);prin tf("%dt%d",T->data,T->bf);prin tf("n");In OrderTraverse(T->RChild);void PreOrderTrave(BSTree & T,BSTree & HT,ElemType e)bool flag;if(T)if(T->data

14、!=e)In sert_AVL(HT,T->data,flag);PreOrderTrave(T->LChild,HT,e);PreOrderTrave(T->RChild,HT,e);void mai n()int i;bool flag;ElemType e;BSTree HT;HT=NULL;printf("请输入数值(0为空树):");sea nf("%d",&e);for(i=1;e!=0;i+)In sert_AVL(HT,e,flag);printf(" 请输入数值(0为空树):"); scan f("%d",&e);=n");=n");prin tf("n=中序遍历平衡二叉树In OrderTraverse(HT);prin tf("n");prin tf("n=指定查找平衡二