详解平衡二叉树.doc

一、平衡二叉树的概念 平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。定义：平衡二叉树或为空树,或为如下性质的二叉排序树: （1）左右子树深度之差的绝对值不超过1; （2）左右子树仍然为平衡二叉树. 平衡因子BF=左子树深度右子树深度.平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。如图所示为平衡树和非平衡树示意图：二、平衡二叉树算法思想若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。1）LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。（2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。（3）LR型平衡旋转法 由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。 如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。（4）RL型平衡旋转法 由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p-right一定不为空，右旋的时候p-left一定不为空，这是显而易见的。如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf = 2或者 bf = -2的节点。 三、二叉排序数的操作及C语言描述插入删除是互为镜像的操作。我们可以采用前面对二叉排序树的删除操作来进行。然后，在删除掉结点后，再对平衡树进行平衡化处理。删除操作需要的平衡化可能比插入时次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度。有可能使树增高的插入操作中，一次平衡化能抵消掉增高；有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。四、二叉排序数的C语言实现#include stdio.h#include stdlib.h#include string.h#define LH +1 /左高#define EH 0 /等高 #define RH -1 /右高#define TRUE 1#define FALSE 1#define EQ(a,b) (a)=(b)#define LT(a,b) (a) (b)#define LQ(a,b) (a) (b)typedef int KeyType;typedef int info;typedef int Boolean;typedef struct ElemTypeKeyType key;/info otherinfo;typedef struct BSTNode ElemType data; int bf; BSTNode *lchild,*rchild; / 左右孩子指针 BSTNode,*BSTree; void R_Rotate(BSTree &p) /右旋 BSTree lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc; /p指向新的根结点 /R_Rotate void L_Rotate(BSTree &p) /左旋 BSTree rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc; /p指向新的根结点 /L_Rotate void LeftBalance(BSTree &T)/作平衡旋转处理BSTree lc,rd;lc=T-lchild;switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T); break; case RH: rd=lc-rchild; switch(rd-bf) case LH:T-bf=RH;lc-bf=EH;break; case EH:T-bf=lc-bf=EH; break; case RH:T-bf=EH;lc-bf=LH;break; /switch rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch/LeftBalancevoid RightBalance(BSTree &T)/作平衡旋转处理BSTree rc,ld;rc=T-rchild;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=LH;rc-bf=EH;break; case EH:T-bf=rc-bf=EH; break; case RH:T-bf=EH;rc-bf=RH;break; /switch ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); /switch/RightBalanceint InsertAVL(BSTree &T,ElemType e,int &taller) / 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 / 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 / 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否 if(!T) / 插入新结点，树“长高”，置taller为TRUE T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=TRUE; else if EQ(e.key,T-data.key) / 树中已存在和e有相同关键字的结点则不再插入 taller=FALSE; return FALSE; if LT(e.key,T-data.key) / 应继续在*T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) / 未插入 return FALSE; 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; else / 应继续在*T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) / 未插入 return FALSE; 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; return TRUE; BSTree SearchBST(BSTree T,KeyType key) / 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， / 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。 if(!T)|EQ(key,T-data.key) return T; / 查找结束 else if LT(key,T-data.key) / 在左子树中继续查找 return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key); / 在右子树中继续查找 /SearchBSTvoid DestroyDSTable(BSTree &DT) / 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT if(DT) / 非空树 if(DT-lchild) / 有左孩子 DestroyDSTable(DT-lchild); / 销毁左孩子子树 if(DT-rchild) / 有右孩子 DestroyDSTable(DT-rchild); / 销毁右孩子子树 free(DT); / 释放根结点 DT=NULL; / 空指针赋0 /if /DestroyDSTableint InitDSTable(BSTree &DT) / 操作结果: 构造一个空的动态查找表DT DT=NULL; return 1; /InitDSTablevoid Visit(BSTree DT)/printf(DT-data.key:-%dnT-bf:%dn,DT-data.key,DT-bf);printf(DT-data.key:-%dn,DT-data.key);/Visit void TraverseDSTable(BSTree &DT,void(*Visit)(BSTree) / 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数 / 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 if(DT) TraverseDSTable(DT-lchild,Visit); / 先中序遍历左子树 Visit(DT); / 再访问根结点 TraverseDSTable(DT-rchild,Visit); / 最后中序遍历右子树 int InsertAVLD(BSTree &T)ElemType e;Boolean taller;printf(input the data until -1n);scanf(%d,&e.key);while(e.key!=-1) InsertAVL(T,e,taller); printf(input the data until -1n); scanf(%d,&e.key); return 1;/InsertAVLDvoid LeftBalanceD(BSTree T,int &shorter)BSTree lc=T-lchild,rd;switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T);break; case EH: T-bf=LH; lc-bf=RH; R_Rotate(T);break; case RH: rd=lc-rchild; switch(rd-bf) case RH: T-bf=EH;lc-bf=LH;shorter=0;break; case EH: T-bf=EH;lc-bf=EH;shorter=1;break; case LH: T-bf=RH;lc-bf=EH;shorter=1;break; /switch rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch/LeftBalanceDvoid RightBalanceD(BSTree T,int &shorter)BSTree rc=T-rchild,ld;switch(rc-bf) case RH: T-bf=rc-bf=EH; R_Rotate(T);break; case EH: T-bf=RH; rc-bf=RH; L_Rotate(T);shorter=0;break; case LH: ld=rc-lchild; switch(ld-bf) case RH: T-bf=EH;rc-bf=RH;break; case EH: T-bf=EH;rc-bf=EH;break; case LH: T-bf=LH;rc-bf=EH;break; /switch ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); /switch/RightBalanceDint SearchBSTD(BSTree &T)ElemType e;printf(nplease input the number you want to search:n);scanf(%d,&e.key);if(SearchBST(T,e.key)!=NULL) printf(%d,e.key);else printf(failed!);return 1;/SearchBSTDint Delete(BSTree &T,KeyType key,int &shorter)int success=0;/标志成功删除与否if(T) if(EQ(key,T-data.key) /相等，即当前结点就是要删除的结点 if(T-lchild!=NULL&T-rchild!=NULL) /要删除结点的左右子树都不空 BSTree q,r; /接下来，找到要删除数据的前驱结点，并且将数据与直接前驱/交换。这样我们将其前驱删除掉后，再调整平衡树就好了。 q=T-lchild; r=q;/用r来指向其前驱接点。 while(q) r=q; q=q-rchild; /while(q) KeyType temp=T-data.key; T-data.key=r-data.key; r-data.key=temp; /接下来，在左子树上删除其前驱接点 success=Delete(T-lchild,key,shorter); if(shorter) /由于删除操作导致了树变小了 switch(T-bf) case LH:T-bf=EH;break; case EH:T-bf=RH;break; case RH:RightBalanceD(T,shorter);break; /switch /if /if-要删除结点左右子树都不空 else /要删除接点有一个子树不为空 BSTree p=T; T=(T-lchild!=NULL)?T-lchild:T-rchild; delete p; success=1;/删除成功 shorter=1;/树变短了。 /else /if= else if(LT(key,T-data.key) /在左子树上查询要删除的结点 success=Delete(T-lchild,key,shorter); if(shorter) switch(T-bf) case LH: T-bf=EH; shorter=0;break; case EH: T-bf=RH; break; case RH: RightBalanceD(T,shorter); break; /switch /if-shorter /ifdata.key) /在右子树上查询要删除的结点 success=Delete(T-rchild,key,shorter); if(shorter) switch(T-bf) case LH: LeftBalanceD(T,shorter); break; case EH: T-bf=LH; break; case RH: T-bf=EH; shorter=0;break; /switch /if-shorter /else if /if(T)return success;/Deleteint DeleteD(BSTree &T)ElemType e;int shorter;printf(ninput the data you want to delete:n);scanf(%d,&e.key);Delete(T,e.key,shorter);return 1;/Deleteint main()BSTree T;InitDSTable(T);InsertAVLD(T);TraverseDSTable(T,Visit);SearchBSTD(T);DeleteD(T);TraverseDSTable(T,Visit);DestroyDSTable(T);return 1;五、复杂度分析在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n个结点的平衡树的最大深度为： 上述讨论，都是在等概率情形下的。如果不是，则为了提高效率，需对等查记录先进行排序，然后构造次优查找树。但是次优查找树不能在查找过程中生成。二叉排序树是动态的，次优查找树是静态的。六、语法知识点1、函数名作为参数传递关于这一点，前面有过讨论。http:/blog.163.com/zhoumhan_0351/blog/static/3995422720093267341920/今天我们再做一个总结。a)一个函数在编译时，也会给它分配一个入口地址。这个入口地址就称为函数的指针。可用一个指针变量指向函数，然后通过该指针变量来调用此函数。如int max(int x,int y)int (*p)(); /定义一个函数指针变量p.p=max;/将max函数的起始地址赋给指针p.c=(*p)(a,b); /等价于c=max(a,b);注意：对于函数指针来说，*(p+1)等操作是违法的。b)指向函数指针变量的定义格式：数据类型 （*指针变量名）（）;这里的数据类型是函数返回值的数据类型。这个指针变量就是专门用来存放函数入口地址的。在一个程序中，一个指针变量可以先后指向返回类型不同的函数。在给函数指针赋值时，只需给出函数名而不必给出参数。再如double (*f)(double)=exp; or f=log10;我们在程序中的函数TraverseDSTable(BSTree &DT,void(*Visit)(ElemType)便是这样。其为返回值为空型，只有一个参数的指指变量，定调用时：TraverseDSTable(T,Visit);其中，Visit便是函数名。2、带参数的宏定义 一般形式为： #define 宏名（参数表） 字符串 在程序中，在编译前，按宏定义命令行中指定的字符串从左到右进行置换，并不分配内存单元，也没有返回值的说法。如：#define EQ(a,b) (a)=(b)则凡是程序中出现有EQ(a,b)的地方，则替换成(a)=(b)表达式。七、弦外之音 关于二叉平衡树的插入的删除的讨论，网上一位网友曾有如下论述，原网址为http:/www.yuanma.org/data/2009/0825/article_3877.htm，在这里贴出来，以作思考。插入和删除 AVL树体现了一种平衡的美感，两种旋转是互为镜像的，插入删除是互为镜像的操作，没理由会有那么大的差别。实际上，平衡化可以统一的这样来操作：1、while (current != NULL)修改current的平衡因子。（1）插入节点时current-bf += (current-data *p)?1:-1;（2）删除节点时current-bf -= (current-data *p)?1:-1;（3）current指向插入节点或者实际删除节点的父节点，这是普通二叉搜索树的插入和删除操作带来的结果。*p初始值是插入节点或者实际删除节点的data。因为删除操作可能实际删除的不是data。2、判断是否需要平衡化if (current-bf = -2) L_Balance(c_root);else if (current-bf = 2) R_Balance(c_root);3、是否要继续向上修改父节点的平衡因子（1）插入节点时if (!current-bf) break;这时，以current为根的子树的高度和插入前的高度相同。（2）删除节点时if (current-bf) break;这时，以current为根的子树的高度和删除前的高度相同4、当前节点移动到父节点，转1。p = &(current-data); current = current-parent;完整的插入删除函数如下：bool insert(const T &data) if (!BSTree:insert(data) return false; const T* p = &data; while (current) current-bf += (current-data *p)?1:-1; if (current-bf = -2) L_Balance(c_root); else if (current-bf = 2) R_Balance(c_root); if (!current-bf) break; p = &(current-data); current = current-parent; return true;bool remove(const T &data) if (!BSTree:remove(data) return false; const T* p = &r_r_data;/在class BSTree里添加proteceted: T r_r_data，在BSTree:remove(const /T &data)里修改为实际删除的节点的data while (current) current-bf -= (current-data *p)?1:-1; if (current-bf = -2) L_Balance(c_root); else if (current-bf = 2) R_Balance(c_root); if (current-bf) break; p = &(current-data); current = current-parent; return true;你可以看到，他们是多么的对称。注：关于二叉平衡树的插入、删除操作中平衡因子的更新，还有待进一步的探讨及争鸣更为简化和统一的处理方法。