《算法导论AVL树.doc》由会员分享，可在线阅读，更多相关《算法导论AVL树.doc（15页珍藏版）》请在三一文库上搜索。
1、算法导论思考题P177：13-3:AVL树主要思路：实现AVL树的关键在于维持树的平衡性。为了保证平衡，AVL树中的每个结点都有一个平衡因子，它表示这个结点的左、右子树的高度差，也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的平衡因子bal值只能是-1、0、1。反之，只要二叉树上一个结点的bal的绝对值大于1，则该二叉树就不是平衡二叉树。每当插入一个节点或删除都有可能破坏了树的平衡性。因此首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二叉查找树的平衡，则找出离插入点最近的不平衡结点，然后将该不平衡结点为根的子树进行旋转操作，称该不平衡结点为旋转根，以该旋转根为根的子树称为
2、最小不平衡子树。要对树进行翻转，以满足平衡性。翻转使用的方法是红黑树中提到的左旋和右旋。根据出现的不同情况对树进行旋转。归纳为4种旋转类型：LL型旋转、RR型旋转、LR型旋转、RL型旋转。1、LL型旋转：2、LR型旋转：推荐精选3、RR型旋转：4、RL型旋转：上图（a）（b）（c）（d）为四种类型的旋转图示。证明：推荐精选 假设 是一颗高度为h的AVL树中最小的节点数：可以看到的定义与斐波那契数列的定义非常相似利用归纳法证明：当时，而（其中），则。反之，含有n个结点的平衡树的最大深度为。 在平衡的的平衡二叉查找树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：(1)若BB
3、ST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1； (2)若e的关键字和BBST的根结点的关键字相等，则不进行； (3)若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：a、BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变；b、BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；c、BBST的根结点的平衡因
4、子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；推荐精选（4） 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。算法实现： #include<stdio.h>#include<malloc.h>#define LH +1 /左高#define EH 0 /等高#define RH -1 /右高t
5、ypedef int ElemType;typedef struct BSTNodeElemType data;int bf; struct BSTNode *LChild,*RChild; BSTNode,*BSTree;推荐精选/ LL型平衡化旋转void L_Rotate(BSTree &p) /对以*p为根的二叉查找树作左旋处理，处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点BSTNode *rc;rc=p->RChild; p->RChild=rc->LChild; rc->LChild=p; p->bf=rc->bf=EH;
6、/平衡因子修改p=rc; /p指向新的根结点/ RR型平衡化旋转void R_Rotate(BSTree &p) /对以*p为根的二叉查找树作右旋处理，处理之后H指向新的树根结点，即旋转处理之前的左子树的根结点BSTNode *lc;lc=p->LChild; p->LChild=lc->RChild; lc->RChild=p; p->bf=lc->bf=EH; p=lc; 推荐精选void LeftBalance(BSTree &T) /对以指针T所指结点为根的二叉树作左平衡旋转处理，函数结束时，指针T指向新的根结点BSTree lc,r
7、d;lc=T->LChild; /lc指向*T的左子树根结点switch(lc->bf) /检查*T的左子树平衡度，并作相应平衡处理case LH: /新结点插入在*T的左孩子的左子树上，需要作单右旋处理T->bf=lc->bf=EH;R_Rotate(T);break;case RH: /新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc->RChild; /rd指向*T的左孩子的右子树的根switch(rd->bf) /修改*T及其左孩子的平衡因子case LH:T->bf=RH;lc->bf=EH;break;case EH:T-&
8、gt;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(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:
9、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=EH;R_Rotate(T->RChild);L_Rotate(T);break;推荐精选int Insert_AVL(BSTree &T,ElemType e,bool &taller) /若在平衡的二叉树T中不存在和e有相同关键字的结点，则插入一个数据
10、元素为e的新结点，并返回1，否则返回0.若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否if(!T) /插入新结点，树“长高”，置taller为trueT=(BSTree)malloc(sizeof(BSTNode);T->data=e;T->LChild=T->RChild=NULL;T->bf=EH;taller=true;else if(e=T->data) /树中已存在和e有相同关键字的结点 taller=false; /不再插入return 0; if(e<T->data) /应继续在T的左子树中进行搜索
11、推荐精选if(!Insert_AVL(T->LChild,e,taller) /未插入 return 0;if(taller) /已插入到T的左子树中且左子树“长高”switch(T->bf) /检查T的平衡度case LH: LeftBalance(T);taller=false;break;case EH: T->bf=LH;taller=true;break;case RH: T->bf=EH;taller=false;break;else /应继续在T的右子树中进行搜索if(!Insert_AVL(T->RChild,e,taller) /未插入推荐精选r
12、eturn 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: /原本右子树比左子树高，需要作右平衡处理RightBalance(T); taller=false;break; return 1;推荐精选void InOrderTraverse(BSTree &T)if(T) InOrderTraverse(T->LChild);printf("%
13、dt%d",T->data,T->bf);printf("n");InOrderTraverse(T->RChild);void PreOrderTrave(BSTree &T,BSTree &HT,ElemType e)bool flag;if(T)if(T->data!=e)Insert_AVL(HT,T->data,flag);PreOrderTrave(T->LChild,HT,e);PreOrderTrave(T->RChild,HT,e);推荐精选void main()int i;bool fl
14、ag;ElemType e;BSTree HT;HT=NULL;printf("请输入数值（0为空树）：");scanf("%d",&e);for(i=1;e!=0;i+)Insert_AVL(HT,e,flag);printf("请输入数值（0为空树）：");scanf("%d",&e);printf("n= 中序遍历平衡二叉树 =n");InOrderTraverse(HT);printf("n");printf("n= 指定查找平衡二叉树 =n");printf("请输入要查找的数值： ");推荐精选scanf("%d",&e);flag=true;if(flag=true)Insert_AVL(HT,e,flag);printf("n* 插入 %d *n",e);InOrderTraverse(HT);printf("n");运行结果： （注：可编辑下载，若有不当之处，请指正，谢谢!） 推荐精选