30分钟让你掌握AVL树（平衡二叉树）

前言：本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也请大牛不要打击小菜)。

本文适合，对avl还不了解，还没有亲自实现avl的插入和删除操作的同学。

ps，你在嘲笑楼主的题目时，你已证明了自己正在嘲笑自己的智商。我们要善于征服陌生的事物。你如果有半个小时时间就心无杂念的开始吧，建议那些读10分钟文章就心燥还是关闭浏览器吧。

文章结构：

什么是二叉排序树(bst)二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树： (1)若左子树不空，则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空，则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;

好了二叉排序树定义很好理解(如果还不理解,为了不浪费时间，先暂停一下，去google or baidu 下，理解了再继续)，再此就不举别的例子了，下面我实现下BST的一些基本操作算法。BST的基本操作

typedef struct _BitNode{ int data; struct _BitNode *lchild,*rchild;}BitNode,*BiTree;

1.1 ,BST的搜索:为什么先实现搜索呢?一般BST里面没有重复的元素，你增添或者删除元素，都必须要先查找一下，看有没有呀，所以BST搜索要先实现，这个搜索是很简单的，慢慢看我讲解吧,我们先看这张图

假如你想找到数值为3的节点并给你这个树的根节点，且规定你只能看到这个根节点左右孩子(其他你们权限看到，也看不到)。那不就是很容易啦，先用3和根节点(此为6)比，显然比6小。那我就去找他的左孩子比，注意，此时4就是6的左子树的根了，那我们就和4这个新的树根比吧，显然又比4小。那我们就继续找这个新根的左孩子比，而此时3就是4的左子树的根了，那我们就和这个根比，哇塞，我们顺藤摸瓜，终于找到了哦!!，那我们就提炼一下这个过程吧，注意哦，我们每次都是和树根相比较的哦!规则：1.先和这棵树的根比2.如果比这个树根小就和这个树根的左子树的根比，否则就和这个树根的右子树比。3.重复2过程，直到根为空为止。 根据3个步骤很容易实现递归代码。//搜索元素，参数依次为0: 根节点,1: 查找的元素,2: 找到目标元素的前一个节点指针，初始值为NULL

// 3:如果返回真把目标到元素的指针指向n，返回假，就把pre复制给n)(参数如果不明白，先不要细究，往下看吧)

bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n);

bool SearchBST(BiTree T,int key,BiTree pre,BiTree&n) { if(!T) { n=pre; //如果此数为空树，那我们就把前一个元素指针pre(此时为NULL)复制给n，注意树为空时，n才为NULL。 return false; //返回假没有找到 } else if(key==T->data) { n=T; //找到了就把目标元素指针给n return true; } if(keydata) SearchBST(T->lchild,key,T,n) ;//去找他的左子树根比 else { SearchBST(T->rchild,key,T,n);//去找他的右子树根比。 } }

1.2 BST的增添元素算法实现有了搜索这个功能，那我们的增添元素的功能就很容易实现了，算法描述：1.先搜所以下所增添的key，在不在此树里面。2.如果没有找到，则申请空间，把key加入里面返回true，否则返回false。

bool InsetBST(BiTree &T,int k) { BitNode* p; if(!SearchBST(T,k,NULL,p)) { BitNode * temp=new BitNode; temp->data=k; temp->lchild=temp->rchild=NULL; if(!p) //只有树为空时，此时的p才为NULL。看到这里应该明白SearchBST(T,k,pre,p)这些参数的意义了吧 { T=temp; } else { if(kdata) //如果不为空树，加入的key值就和p相比较，小于就是他的左孩子，否子为右孩子 p->lchild=temp; else { p->rchild=temp; } } return 0; } else { return false; } }

1.3BST删除元素的算法实现

既然看到这里了，证明你的好奇心很强，这一节看完，我们就离成功不远了，那我们继续吧!

删除总共有3种情况，1只有左子树;2，只有右子树;3，左右子树都有。 先看第一种

如上图所示 我们要删除4这个节点，我们就把他双亲节点的左孩子指向4的左子树。简单吧!。那我么看第二种吧

如上图所示我们所要删除的7节点只有右子树，想必一定想到了，那我们就把他双亲节点的右孩子指向7节点的右孩子，那不就ok啦，太棒了!!。现在看第三种情况吧。

大家看出这三幅图的变化了吗?我们所要删除节点4，为了要保持树的顺序我们就要找比4大的且要离4最近的，那就是他的后继，当然你找前继也是可以的。此图是找他的后继。我们找到后就用4的后继替换4，最后删除后继这个节点。ok，大家看完并理解了这3种情况，那代码实现就很easy啦。

bool DeleElement(BiTree&T,int key) { if(!T) { return 0; //树是空树的话就返回假 } if(T->data==key) { BitNode*s,*p; if(T->rchild==NULL) //只有右子树，情况2 { s=T; T=T->lchild; free(s); } else if(T->lchild==NULL) { s=T; //只有左子树，情况1 T=T->rchild; free(s); } else { //情况3，左右子树都有 p=T; s=T->rchild; while (s->lchild) { p=s; //找到所要删除节点的后继，那就是他的右孩子的 s=s->lchild; } T->data=s->data; //用删除节点的后继替换所删除的节点 if(p!=T) { p->lchild=NULL; //所删除的节点的右孩子不是叶结点 } else p->rchild=NULL; //所删除的节点的右孩子是叶节点 free(s); } return 1; } else if(keydata) DeleElement(T->lchild,key); //去和他的左子树根去比较 else DeleElement(T->rchild,key); //去和他的右子树根去比较 }

//中序遍历并输出元素 void InorderReverse(BiTree T) { if(T) { InorderReverse(T->lchild); cout<data<rchild); p="" }

终于搞完啦，咱也立马上机去测试吧，如果理解了，就自己测试吧，看能不能自己写出来哦!下面是我自己的测试

int main(){ BiTree tree=NULL; int a[]={60,86,50,40,35,74,51,100,37,90}; for(int i=0;i<10;i++) InsetBST(tree,a[i]); InorderReverse(tree); cout<<" "<<endl<<endl; p="" 0;}

到这为止二叉排序树已经搞定了，如果你自己也实现了上述功能，那证明你有很强的好奇心并且很有天赋(因为楼主搞了好几天才明白，你十几分就搞定了，那不是最好的证明吗?ps：楼主是那种很迟钝但很有毅力)，有了前面的基础，AVL就是手到擒来，不要灰心哦，鼓足劲就继续征程吧。如果没有理解，先暂停会，避免浪费不必要的时间，就不要往下看了，建议反复认真看几遍，如果还不理解，可能这篇文章不适合你，建议参考其它文章。

什么是AVL定义：

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1,这里我们定义:

#define EH 0,#define LH 1,#define RH -1.依次为等高，左高，右高。

typedef struct _BitNode

{

int data;

int bf;//平衡因子

struct _BitNode *lchild,*rchild;

}BitNode,*BiTree;

我们都知道，平衡二叉树是在二叉排序树(BST)上引入的(这一点很重要哦，下图为例)，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡，那么怎么保持平衡呢?如果还不理解看看下面的图吧。

看看AVL的魅力吧。有它就有它存在的价值，看下图便知。

图一和图二都是BST，但图二不是AVL，图一是AVL Tree，如果我们要找到10，图一比较次数为3，而图二比较次数为7次，很显然，在规模比较大的话AVL优势就很突出了。既然AVL这么强大，牛叉。那我们就把它拿下吧。2.1 AVL增添元素 这里搜索和BST搜索一样，我就不浪费时间介绍了，我们先实现增加元素的，实现然后删除元素的。可是每次的插入和删除都要确保二叉树的平衡，那么怎么保持平衡呢?我们就引入平衡因子。注意这里再看下平衡因子的定义我先演示下给一组数据，怎么组成一棵AVl Tree。。int a[]={4,3,2,7,9,11,10};1， 插入4，如图：

，平衡因子为0.2， 插入3，如图：

，4的平衡因子因为4的左子树增长了，1-0=1，3， 插入2，如图

，显然4的平衡因子大于1了，为了保持平衡那我们就这样做：让4节点的左孩子指向3的右子树(此时为NULL)，让3的右孩子指向4，让树根指向3，如图

，这种操作我们规定为右旋操作，此图是以4为根进行旋转。 代码如下

void R_Rotate(BiTree&T){ BiTree p; // p=T->lchild; //假如此时T指向4，则p指向3; T->lchild=p->rchild; //把3的右子树挂接到4的左子树上(此例子3右子树为空) p->rchild=T; //让3的右孩子指向4. T=p; //根指向节点3}

4，插入7，如图：

5，插入9，如图：

显然节点4不平衡了。那我们就把4的右孩子7的左子树(此时为NULL)，让7的左孩子指向4，让3的右孩子指向7，如图：

，我们规定此操作为左旋操作，此图是以4为根进行旋转，代码如下：

void L_Rotate(BiTree&T){ BiTree p; p=T->rchild; //假如此时T指向4，则p指向7. T->rchild=p->lchild; //让7的左子树挂接到4的右子树上 p->lchild=T; //让7的左孩子指向4 T=p; //树根指向7}

6.我们插入11，如图：

显然3节点，不平衡了，大家都应该知道以3为根进行左旋。让3的右孩子指向7的左子树(此时为4)。7的左孩子指向3，根指向7，如下图所示：

7.我们插入10，如图：

显然节点9不平衡，且是右边高，那我们左旋吧，左旋后的效果是上图右图所示。显然这是不对的，10比11小，但在11的右孩子上。(根本原因是9和11的平衡因子符号不同)那我们在怎么办呢,看下图吧：

成功离我们不远了，我们很容易的把这组数据拼出了AVl 树，是不是很有成就感呀。好啦，我们总结下插入元素的有哪些规律吧 1，如上所述的第3步，当插入元素后导致左边高，右边低，并且为4和3的平衡因子符号相同，则右旋。 

2, 如上所诉的第5步，当插入节点9后，导致以4为根的树右边高，左边低，4和7的平衡因子符号相同，则左旋 3，如上所述的第7步，当插入节点10后，导致以9为根的树右边高，左边低，由于9和11的平衡因子符号不同(也就是根和他的右孩子的平衡因子符号不同)不能进行左旋，正确操作：需要先右旋在左旋，要让根和根的右孩子平衡因子符号相同。 4，第4种旋转和3相反，当左边高于右边的话，且根和他的左孩子，平衡因子符号不同，需要先左旋再右旋恩，就是这么简单。在实现插入函数之前，我们先封装2个函数。RightBalance():当右高时需要右平衡时调用;

LeftBalance()功能:当左高时需要左平衡时调用;右平衡函数代码:

void RightBalance(BiTree&T){ BiTree R,rl; //调用此函数时，以T为根的树，右边高于左边，则T->bf=RH。 R=T->rchild; //R是T的右孩子 switch (R->bf) { case RH: //如果 T的右孩子和T他们的平衡因子符号相同时，则直接左旋，这是总结中的第2项 T->bf=R->bf=EH; L_Rotate(T); break;

case EH: T->bf=RH; R->bf=LH; L_Rotate(T); break; case LH: //如果T的右孩子和T他们的平衡因子符合不同时，需要先以T的右孩子为根进行右旋，再以T为根左旋。 //rl为T的右孩子的左孩子 rl=R->lchild; //2次旋转后，T的右孩子的左孩子为新的根 。注意：rl的右子树挂接到R的左子树上，rl的左子树挂接到T的右子树上 switch (rl->bf) //这个switch 是操作T和T的右孩子进行旋转后的平衡因子。 { case EH: T->bf=R->bf=EH; //这些平衡因子操作，大家可以自己画图操作理解 下面的注解 break; ////2次旋转后，T的右孩子的左孩子为新的根 。 //并且rl的右子树挂接到R的左子树上，rl的左子树挂接到T的右子树上，rl为新根 case RH: R->bf=EH; T->bf=LH; break; case LH: R->bf=RH; T->bf=EH; break; default: break; } rl->bf=EH; R_Rotate(T->rchild); //先左旋，以T->rchild为根左旋。 L_Rotate(T); //右旋，以T为根, 左旋后 T是和rl想等，rl是新根 break; }}void LeftBalance(BiTree&T){ BiTree L,lr; L=T->lchild; switch (L->bf) {

case EH: L->bf=RH; T->bf=LH; R_Rotate(T); break; case LH: L->bf=T->bf=EH; R_Rotate(T); break; case RH: lr=L->rchild; switch (lr->bf) { case EH: L->bf=L->bf=EH; case RH: T->bf=EH; L->bf=LH; break; case LH: L->bf=EH; T->bf=RH; break; default: break; } lr->bf=EH; L_Rotate(T->lchild); R_Rotate(T); break; default: break; }}

//哈哈，两元猛将我们已经找到了，但是你看到这有点累了，但不要灰心，成功就在我们脚下，现在放弃，岂不是很可惜啦。那我们就实现插入元素的功能

bool InsertAVLtree(BiTree&T,int key,bool&taller){ if(!T) //此树为空 { T=new BitNode; //直接作为整棵树的根。 T->bf=EH; T->lchild=T->rchild=NULL; T->data=key; taller=true; return true; } else { if(key==T->data) //已有元素，不用插入了，返回false; { taller=false; return false; } if(keydata) //所插元素小于此根的值，就找他的左孩子去比 { if(!InsertAVLtree(T->lchild,key,taller)) //所插元素小于此根的值，就找他的左孩子去比 return false; if(taller) //taller为根，则树长高了，并且插入到了此根的左子树上。 { switch (T->bf) //此根的平衡因子 { case EH: //原先是左右平衡，等高 T->bf=LH; //由于插入到左子树上，导致左高=》》LH taller=true; //继续往上递归 break; case LH: LeftBalance(T); //原先LH，由于插入到了左边，这T这个树，不平衡需要左平衡 taller=false; //以平衡，设taller为false，往上递归就不用进入此语句了， break; case RH: T->bf=EH; //原先RH，由于插入到左边，导致此T平衡 taller=false; break; default: break; } } } else { if(!InsertAVLtree(T->rchild,key,taller)) return false; if(taller) { switch (T->bf) { case EH: T->bf=RH; taller=true; break; case LH: T->bf=EH; taller=false; break; case RH: RightBalance(T); taller=false; break; default: break; } } } }

//中序遍历输出void InOrderReverse(BiTree&T){ if(T) { InOrderReverse(T->lchild); cout<data<rchild); p="" }}

看到这了，自己出一组数据或按照我刚才用一组数据拼成avl的过程，看代码走一遍，你会有不一样的收货的哦(这其实非常重要)，并插入了成功了，你已经成功99%了，没有想到自己这么厉害吧，我们接下来完成它的删除操作，我们就完美了。如果你有追求完美的目标，那就跟我走吧

2.2AVL的删除操作

下面我会贴出代码，根据代码把上图的元素删除掉吧，你会成功的

为了更好的理解，建议先把插入代码先实现。

删除代码和BST的删除相似，AVL删除元素后还要照顾好平衡。

bool DeletElement(BiTree&T,int key,bool&lower)//参数(0)树根，(1)删除的元素，(3)此树是否降低标志位

{

bool L,R;//删除的是左子树还是右子树，作为标志。

L=R=false;

if(T==NULL) // 判断树根是否为空

return false;

if(key==T->data)//找到了所要删除的节点

{

BitNode* p,*s;

p=T->rchild;

s=p;

lower=true; //找到了必定删除，lower为真

if(T->rchild==NULL) // 如果所要删除的节点的右孩子为空

{

p=T;

T=T->lchild; //直接删除比如删除上图的 4,9,10，

free(p);

lower=true;

return true;

}

else

{

while (s)//如果所要删除的T节点右子树不为空，就找T的后继，也就是T的右孩子左子树的最左叶节点

{

p=s;

s=s->lchild;

}

T->data=p->data;//替换T

DeletElement(T->rchild,p->data,lower);//删除掉T的后继

R=true;

}

}

else if(key

好吧，请原谅我骗了你，你看到这时，已不止半小时了。但为你使你相信你是有能力看完的，我不得不做这个下贱的谎言。 我不期望你能全部都能按照我的思路写下去，因为我写的还不够好，哪怕你有一点收获，楼主也是值得的。