算法导论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型旋转：3、RR型旋转：4、RL型旋转：上图（a）（b）（c）（d）为四种类型的旋转图示。证明： 假设 是一颗高度为h的AVL树中最小的节点数：可以看到的定义与斐波那契数列的定义非常相似利用归纳法证明：当时，而（其中），则。反之，含有n个结点的平衡树的最大深度为。 在平衡的的平衡二叉查找树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：(1)若BBST为空树，则插

3、入一个数据元素为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的根结点的平衡因子为1（左子树的

4、深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；（4） 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。算法实现： #include#include#define LH +1 /左高#define EH 0 /等高#define RH -1 /右高typedef int ElemType;typedef struct BSTNodeE

5、lemType 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; /平衡因子修改p=rc; /p指向新的根结点/ RR型平衡化旋转void R_Rotate(BSTree &p) /对以*p为根的二叉查找树作右旋处理

6、，处理之后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,rd;lc=T-LChild; /lc指向*T的左子树根结点switch(lc-bf) /检查*T的左子树平衡度，并作相应平衡处理case LH: /新结点插入在*T的左孩子的左子树上，需要作单右旋处理T-bf=lc-bf=

7、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-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

8、 &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=EH;R_Rotate(T-RChild);L_Rotate(T);break;int Insert_AVL(BSTree &T,ElemT

9、ype e,bool &taller) /若在平衡的二叉树T中不存在和e有相同关键字的结点，则插入一个数据元素为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(

10、edata) /应继续在T的左子树中进行搜索 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) /未插入return

11、 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(%dt%d,T-data,T-bf);printf(n);InOrder

12、Traverse(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 flag;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= 中序遍历平衡二叉树 =