平衡二叉樹

二叉查找樹的查找、插入、删除的時間複雜度均線性正比于二叉查找樹的高度，高度越小，效率越高。
最好的情況下，每次都一分為二，左右子樹的節點數均為n/2，左右子樹的高度也一樣。

原理 AVL樹

平衡二叉查找樹，簡稱平衡二叉樹（AVL）
平衡二叉樹或為空樹，或為具有以下性質的平衡二叉樹：①左右子樹高度差的絕對值不超過1；②左右子樹也是平衡二叉樹
平衡二叉樹除了具有适度平衡性，還具有局部性：①在單次插入、删除後，至多有O(1)處出現不平衡；②總可以在O(logn)時間内，使這O(1)處不平衡重新調整為平衡。
對平衡二叉樹在動态修改後出現的不平衡，隻需局部（最小不平衡子樹）調整平衡即可，不需要對整顆樹進行調整。

調整平衡的方法

調整平衡可以分為4種情況： LL型、RR型、LR型、RL型。

LL型

插入新節點x後，從該節點向上找到最近的不平衡節點A，如果最近不平衡節點到新節點的路徑前兩個都是左子樹L，就是LL型。
即将節點x插入A的左子樹的左子樹中，A的左子樹因插入新節點而高度增加，造成A的平衡因子由1增加為2，失去平衡。需要進行LL旋轉（順時針）調整平衡。
LL旋轉：A順時針旋轉到B的右子樹，B原來的右子樹T_{3}被抛棄，A旋轉後正好左子樹空閑，将這個被抛棄的子樹 T 3 T_{3} T3放到A的左子樹中即可。
旋轉之後，A、B兩個節點的左右子樹高度之差均為0，滿足平衡條件，C的左右子樹未變，仍然平衡。

AVLTree LL_Rotation(AVLTree &T)//LL旋轉
{
    AVLTree temp=T->lchild;
    T->lchild=temp->rchild;
    temp->rchild=T;
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

RR型

插入新節點x後，從該節點向上找到最近不平衡節點A，如果最近不平衡節點到新節點的路徑前兩個都是右子樹R，就是RR型。需要進行RR旋轉（逆時針）調整平衡。
RR旋轉：A逆時針旋轉到B的左子樹，B原來的左子樹T_{2}被抛棄，A旋轉後正好右子樹空閑，将這個被抛棄的子樹 T 2 T_{2} T2放到A右子樹中即可。
旋轉之後，A、B兩個節點的左右子樹高度之差均為0，滿足平衡條件，C的左右子樹未變，仍然平衡。

AVLTree RR_Rotation(AVLTree &T)//RR旋轉
{
    AVLTree temp=T->rchild;
    T->rchild=temp->lchild;
    temp->lchild=T;
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

LR型

插入新節點x後，從該節點向上找到最近不平衡節點A，如果最近不平衡節點到新節點的路徑前兩個依次是左子樹L、右子樹R，就是LR型。
LR旋轉：分兩次旋轉。C逆時針旋轉到A、B之間，C原來的左子樹 T 2 T_{2} T2被抛棄，B正好右子樹空閑，将這個被抛棄的子樹 T 2 T_{2} T2放到B右子樹中；這時已經轉變為LL型，進行LL旋轉即可，實際上也可以看作C固定不動，B進行RR旋轉，然後進行LL旋轉。
旋轉之後，A、B兩個節點的左右子樹高度之差均為0，滿足平衡條件，C的左右子樹未變，仍然平衡。

AVLTree LR_Rotation(AVLTree &T)//LR旋轉
{
     T->lchild=RR_Rotation(T->lchild);
     return LL_Rotation(T);
}

RL型

插入新節點x後，從該節點向上找到最近不平衡節點A，如果最近不平衡節點到新節點的路徑前兩個依次是右子樹R、左子樹L，就是RL型。
RL旋轉：分兩次旋轉。C順時針旋轉到A、B之間，C原來的右子樹 T 3 T_{3} T3被抛棄，B正好左子樹空閑，這個被抛棄的子樹 T 3 T_{3} T3放到B左子樹；這時已經轉變為RR型，做RR旋轉即可，實際上，也可以看作C固定不動，B進行LL旋轉，然後進行RR旋轉。
旋轉之後，A、B兩個節點的左右子樹高度之差均為0，滿足平衡條件，C的左右子樹未變，仍然平衡。

AVLTree RL_Rotation(AVLTree &T)//RL旋轉
{
    T->rchild=LL_Rotation(T->rchild);
    return RR_Rotation(T);
}

平衡二叉樹的插入

在平衡二叉樹中插入新的資料元素 x x x，首先要查找其插入的位置，在查找過程中，用 p p p指針記錄目前節點，用 f f f指針記錄 p p p的雙親。

在平衡二叉樹中查找 x x x，如果查找成功，則什麼也不做，傳回 p p p；如果查找失敗，則執行插入操作。
建立一個新節點 p p p存儲 x x x，該節點的雙親為 f f f，高度為1。
從新節點子父 f f f出發，向上查找最近的不平衡節點。逐層檢查各代祖先節點，如果平衡，則更新其高度，繼續向上查找；如果不平衡，則判斷失衡類型（沿着高度最大的子樹判斷，剛插入新節點的子樹必然高度大），并作出相應的調整，傳回p。

AVLTree Insert(AVLTree &T,int x)
{
    if(T==NULL) //如果為空，建立新結點
    {
        T=new AVLNode;
        T->lchild=T->rchild=NULL;
        T->data=x;
        T->height=1;
        return T;
     }
    if(T->data==x) return T;//查找成功，什麼也不做，查找失敗時才插入
    if(x<T->data)//插入到左子樹
    {
        T->lchild=Insert(T->lchild,x);//注意插入後飯後結果挂接到T->lchild
        if(Height(T->lchild)-Height(T->rchild)==2)//插入後看是否平衡，如果不平衡顯然是插入的那一邊高度大
        {                                         //沿着高度大的那條路徑判斷
            if(x<T->lchild->data)//判斷是LL還是LR,即插入的是lchild節點的lchild 還是rchild
                T=LL_Rotation(T);
            else
                T=LR_Rotation(T);
        }
    }
    else//插入到右子樹
    {
        T->rchild=Insert(T->rchild,x);
        if(Height(T->rchild)-Height(T->lchild)==2)
        {
            if(x>T->rchild->data)
                T=RR_Rotation(T);
            else
                T=RL_Rotation(T);
        }
    }
    updateHeight(T);
    return T;
}

平衡二叉樹的建立

平衡二叉樹的建立和二叉查找樹的建立類似，隻是插入操作多了調整平衡而已。可以從空樹開始，按照輸入關鍵字的順序依次進行插入操作，最終得到一顆平衡二叉樹。

初始化平衡二叉樹為空樹，T = NULL。
輸入一個關鍵字x，将x插入平衡二叉樹T中。
重複步驟2，直到關鍵字輸入完畢。

AVLTree CreateAVL(AVLTree &T)
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        T=Insert(T,x);
    }
    return T;
}

平衡二叉樹的删除

進行删除操作時需要一直從删除節點之父向上檢查，發現不平衡便立即調整，然後繼續向上檢查，直到樹根。

在平衡二叉樹中查找x，如果查找失敗，則傳回；如果查找成功，則執行删除操作（同二叉查找樹的删除操作）。
從實際被删除節點之父g出發（當被删除節點有左右子樹時，令其直接前驅（或直接後繼）代替其位置，删除其之間前驅，實際被删除節點為其之間前驅（或直接後繼）），向上尋找最近的不平衡節點。逐層檢查各代祖先節點，如果平衡，則更新其高度，繼續向上尋找；如果不平衡，則判斷失衡類型（沿着高度大的子樹判斷），并做相應的調整。
繼續向上檢查，一直到樹根。

AVLTree adjust(AVLTree &T)//删除結點後，需要判斷是否還是平衡，如果不平衡，就要調整
{
    if(T==NULL) return NULL;
    if(Height(T->lchild)-Height(T->rchild)==2)//沿着高度大的那條路徑判斷
    {
        if(Height(T->lchild->lchild)>=Height(T->lchild->rchild))
            T=LL_Rotation(T);
        else
            T=LR_Rotation(T);
    }
    if(Height(T->rchild)-Height(T->lchild)==2)//沿着高度大的那條路徑判斷
    {
        if(Height(T->rchild->rchild)>=Height(T->rchild->lchild))
            T=RR_Rotation(T);
        else
            T=RL_Rotation(T);
    }
    updateHeight(T);
    return T;
}

AVLTree Delete(AVLTree &T,int x)
{
    if(T==NULL) return NULL;
    if(T->data==x)//如果找到删除節點
    {
        if(T->rchild==NULL)//如果該節點的右孩子為NULL,那麼直接删除
        {
            AVLTree temp=T;
            T=T->lchild;
            delete temp;
        }
        else//否則，将其右子樹的最左孩子作為這個節點，并且遞歸删除這個節點的值
        {
           AVLTree temp;
           temp=T->rchild;
           while(temp->lchild)
              temp=temp->lchild;
           T->data=temp->data;
           T->rchild=Delete(T->rchild,T->data);
           updateHeight(T);
        }
        return T;
    }

    if(T->data>x)//調節删除節點後可能涉及的節點
        T->lchild=Delete(T->lchild,x);
    if(T->data<x)
        T->rchild=Delete(T->rchild,x);
    updateHeight(T);
	T=adjust(T);
    return T;
}

整體算法實作

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef struct AVLNode{
   int data;
   int height;
   struct AVLNode *lchild;
   struct AVLNode *rchild;
}*AVLTree;

AVLTree Empty(AVLTree &T)//删除樹
{
    if(T==NULL) return NULL;
    Empty(T->lchild);
    Empty(T->rchild);
    delete T;
    return NULL;
}

inline int Height(AVLTree T)//計算高度
{
    if(T==NULL) return 0;
    return T->height;
}

void updateHeight(AVLTree &T)
{
     T->height=max(Height(T->lchild),Height(T->rchild))+1;
}

AVLTree LL_Rotation(AVLTree &T)//LL旋轉
{
    AVLTree temp=T->lchild;
    T->lchild=temp->rchild;
    temp->rchild=T;
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

AVLTree RR_Rotation(AVLTree &T)//RR旋轉
{
    AVLTree temp=T->rchild;
    T->rchild=temp->lchild;
    temp->lchild=T;
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

AVLTree LR_Rotation(AVLTree &T)//LR旋轉
{
     T->lchild=RR_Rotation(T->lchild);
     return LL_Rotation(T);
}

AVLTree RL_Rotation(AVLTree &T)//RL旋轉
{
    T->rchild=LL_Rotation(T->rchild);
    return RR_Rotation(T);
}

AVLTree Insert(AVLTree &T,int x)
{
    if(T==NULL) //如果為空，建立新結點
    {
        T=new AVLNode;
        T->lchild=T->rchild=NULL;
        T->data=x;
        T->height=1;
        return T;
     }
    if(T->data==x) return T;//查找成功，什麼也不做，查找失敗時才插入
    if(x<T->data)//插入到左子樹
    {
        T->lchild=Insert(T->lchild,x);//注意插入後飯後結果挂接到T->lchild
        if(Height(T->lchild)-Height(T->rchild)==2)//插入後看是否平衡，如果不平衡顯然是插入的那一邊高度大
        {                                         //沿着高度大的那條路徑判斷
            if(x<T->lchild->data)//判斷是LL還是LR,即插入的是lchild節點的lchild 還是rchild
                T=LL_Rotation(T);
            else
                T=LR_Rotation(T);
        }
    }
    else//插入到右子樹
    {
        T->rchild=Insert(T->rchild,x);
        if(Height(T->rchild)-Height(T->lchild)==2)
        {
            if(x>T->rchild->data)
                T=RR_Rotation(T);
            else
                T=RL_Rotation(T);
        }
    }
    updateHeight(T);
    return T;
}

AVLTree adjust(AVLTree &T)//删除結點後，需要判斷是否還是平衡，如果不平衡，就要調整
{
    if(T==NULL) return NULL;
    if(Height(T->lchild)-Height(T->rchild)==2)//沿着高度大的那條路徑判斷
    {
        if(Height(T->lchild->lchild)>=Height(T->lchild->rchild))
            T=LL_Rotation(T);
        else
            T=LR_Rotation(T);
    }
    if(Height(T->rchild)-Height(T->lchild)==2)//沿着高度大的那條路徑判斷
    {
        if(Height(T->rchild->rchild)>=Height(T->rchild->lchild))
            T=RR_Rotation(T);
        else
            T=RL_Rotation(T);
    }
    updateHeight(T);
    return T;
}

AVLTree Delete(AVLTree &T,int x)
{
    if(T==NULL) return NULL;
    if(T->data==x)//如果找到删除節點
    {
        if(T->rchild==NULL)//如果該節點的右孩子為NULL,那麼直接删除
        {
            AVLTree temp=T;
            T=T->lchild;
            delete temp;
        }
        else//否則，将其右子樹的最左孩子作為這個節點，并且遞歸删除這個節點的值
        {
           AVLTree temp;
           temp=T->rchild;
           while(temp->lchild)
              temp=temp->lchild;
           T->data=temp->data;
           T->rchild=Delete(T->rchild,T->data);
           updateHeight(T);
        }
        return T;
    }

    if(T->data>x)//調節删除節點後可能涉及的節點
        T->lchild=Delete(T->lchild,x);
    if(T->data<x)
        T->rchild=Delete(T->rchild,x);
    updateHeight(T);
	T=adjust(T);
    return T;
}

void Preorder(AVLTree T)//前序周遊友善看樹的結果
{
    if(T==NULL) return ;
    cout<<T->data<<"\t"<<T->height<<endl;
    Preorder(T->lchild);
    Preorder(T->rchild);
}

 void Inorder(AVLTree T)//中序周遊友善看樹的結果
{
    if(T==NULL) return ;
    Inorder(T->lchild);
    cout<<T->data<<"\t"<<T->height<<endl;
    Inorder(T->rchild);
}

 void Posorder(AVLTree T)//後序周遊友善看樹的結果
{
    if(T==NULL) return ;
    Posorder(T->lchild);
    Posorder(T->rchild);
    cout<<T->data<<"\t"<<T->height<<endl;
}

void show(AVLTree T)
{
    Preorder(T);
    cout<<endl;
    Inorder(T);
    cout<<endl;
    Posorder(T);
}

AVLTree CreateAVL(AVLTree &T)
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        T=Insert(T,x);
    }
    return T;
}
int main()
{
    int x;
    AVLTree root=NULL;
    root=Empty(root);
    CreateAVL(root);
    show(root);
    cin>>x;
    root=Delete(root,x);
    show(root);
    return 0;
}

輸入：

6
25 18 5 10 15 17
5

輸出：

算法訓練營查找算法（平衡二叉樹）平衡二叉樹

平衡二叉樹

原理 AVL樹

調整平衡的方法

LL型

RR型

LR型

RL型

平衡二叉樹的插入

平衡二叉樹的建立

平衡二叉樹的删除

整體算法實作

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希

算法訓練營 查找算法（平衡二叉樹）平衡二叉樹

平衡二叉樹

原理 AVL樹

調整平衡的方法

LL型

RR型

LR型

RL型

平衡二叉樹的插入

平衡二叉樹的建立

平衡二叉樹的删除

整體算法實作

繼續閱讀

算法訓練營查找算法（平衡二叉樹）平衡二叉樹