【原】有关AVL树的总结与感悟

C/C++实现AVL树（二叉平衡搜索树）

一开始以为很复杂很可怕，后来自己想了一下其实也没那么可怕，无非就是左右子树的顺序调换而已。

有关AVL的旋转的原理就不再说明，不懂自行百度查书了解旋转原理。
以下是部分代码实现AVL树

首先是树的结构的构建

 struct tree
 {
    struct tree* ls;   //左儿子
    struct tree* rs;   //右儿子
    int siz,con,data,height;  //大小，内容，数据，高度
 };
 typedef struct tree stu;
 typedef struct tree* ptr;

下面是旋转的代码实现

1.左单旋与右单旋

什么时候单旋不再说明了，自行百度查书了解各种情况。

 void left(ptr* now){             //左旋
    ptr tmp=(*now)->rs;          //其实本质就是左右儿子的替换
    (*now)->rs=tmp->ls;
    tmp->ls=*now;
    tmp->siz=(*now)->siz;
    pushup(*now),pushup(tmp);
    *now=tmp;
    return;
 }

void right(ptr* now){             //右旋 
    ptr tmp=(*now)->ls;
    (*now)->ls=*now;
    tmp->siz=(*now)->siz;
    pushup(*now),pushup(tmp);
    *now=tmp;
    return;
}

2.插入、平衡、刷新过程

平衡这一部分的代码是AVL的核心
其实也就是比普通二叉搜索树多了一个平衡的操作而已
写出二叉搜索树，再加上平衡操作就行了

总的来说就是插入->平衡->刷新

void ins(ptr* now,int num)   //其实仔细分辨的话，也只是比二叉搜索树多了一些判断和平衡而已
{
if (*now==NULL)
{
*now=(ptr)malloc(sizeof(stu));
(*now)->siz=(*now)->con=1;
(*now)->data=num,(*now)->height=0;
(*now)->ls=(*now)->rs=NULL; return;
}
if ((*now)->data==num)
{
(*now)->con++;
pushup(*now); return;
}
if ((*now)->data>num) ins(&(*now)->ls,num);
else ins(&(*now)->rs,num);
pushup(*now); balance(now); return;
}

void balance(ptr *now)    //进行平衡的操作  对于不同情况的调用
{
if (*now==NULL) return;
if (h((*now)->ls)-h((*now)->rs)==2)
{
if (h((*now)->ls->ls)>h((*now)->ls->rs)) right(now);
else left(&(*now)->ls),right(now); return;  
}
if (h((*now)->rs)-h((*now)->ls)==2)
{
if (h((*now)->rs->rs)>h((*now)->rs->ls)) left(now);
else right(&(*now)->rs),left(now); return;
}
return;
}

 void pushup(ptr now){            //进行重新刷新 相当于树的重建过程
     if(now==NULL) return;        //刷新当前树的高度，数据内容等
     now->height=1;
     now->siz=now->con;
     now->siz+=size(now->ls);
     now->siz+=size(now->rs);
     if(h(now->ls)>h(now->ls))
        now->height+=h(now->ls); 
     else now->height+=h(now->rs);
     return;
 }

3.删除节点后的平衡

void del(ptr* now,int num)
{
if (*now==NULL) return;
if ((*now)->data==num)
{
if ((*now)->con>1) (*now)->con--;
else
{
ptr cng=*now;
if ((*now)->ls==NULL) *now=(*now)->rs,free(cng);
else if ((*now)->rs==NULL) *now=(*now)->ls,free(cng);
else
{
cng=(*now)->rs;
while (cng->ls) cng=cng->ls;
(*now)->data=cng->data;
(*now)->con=cng->con,cng->con=1;
del(&(*now)->rs,cng->data);
}
}
}
else
{
if ((*now)->data>num) del(&(*now)->ls,num);
else del(&(*now)->rs,num);
}
pushup(*now); balance(now); return;
}

4.打印AVL树的结点

1.前序遍历

void print(ptr p)
{
printf("data:%d,con:%d,",p->data,p->con);
printf("siz:%d,h:%d   ",p->siz,p->height);
return;
}

void printfst(ptr now)
{
if (now)
{
print(now);
if (now->ls) printfst(now->ls);
if (now->rs) printfst(now->rs);
}
else printf("NULL");
return;
}

2.中序遍历

void printmid(ptr now)
{
if (now)
{
if (now->ls) printmid(now->ls);
print(now);
if (now->rs) printmid(now->rs);
}
else printf("NULL");
return;
}

3.后序遍历

void printlst(ptr now)
{
if (now)
{
if (now->ls) printlst(now->ls);
if (now->rs) printlst(now->rs);
print(now);
}
else printf("NULL");
return;
}

5.总结

这个是链表实现的AVL树，后期会补充上数组实现AVL树，
总的来说，并不算太难，比起复杂的图的递归，这个确实比较明确，就是旋转->平衡->刷新的过程。
往后也会补充上双旋的过程。
也欢迎大家一起学习交流。