有關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樹，

總的來說，并不算太難，比起複雜的圖的遞歸，這個确實比較明确，就是旋轉->平衡->重新整理的過程。

往後也會補充上雙旋的過程。

也歡迎大家一起學習交流。