什么是平衡二叉樹(shù)AVL-創(chuàng)新互聯(lián)

什么是平衡二叉樹(shù)AVL，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比鄯善網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式鄯善網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋鄯善地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。

前言

Wiki:在計(jì)算機(jī)科學(xué)中，AVL樹(shù)是最早被發(fā)明的自平衡二叉查找樹(shù)。在AVL樹(shù)中，任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹(shù)的大高度差為1，因此它也被稱為高度平衡樹(shù)。查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是 O(logn）。增加和刪除元素的操作則可能需要借由一次或多次樹(shù)旋轉(zhuǎn)，以實(shí)現(xiàn)樹(shù)的重新平衡。AVL 樹(shù)得名于它的發(fā)明者 G. M. Adelson-Velsky 和 Evgenii Landis，他們?cè)?962年的論文《An algorithm for the organization of information》中公開(kāi)了這一數(shù)據(jù)結(jié)構(gòu)。

1 為什么要有平衡二叉樹(shù)

二叉搜索樹(shù)一定程度上可以提高搜索效率，但是當(dāng)原序列有序時(shí)，例如序列 A = {1，2，3，4，5，6}，構(gòu)造二叉搜索樹(shù)如圖 1.1。依據(jù)此序列構(gòu)造的二叉搜索樹(shù)為右斜樹(shù)，同時(shí)二叉樹(shù)退化成單鏈表，搜索效率降低為 O(n)。

什么是平衡二叉樹(shù)AVL

在此二叉搜索樹(shù)中查找元素 6 需要查找 6 次。

二叉搜索樹(shù)的查找效率取決于樹(shù)的高度，因此保持樹(shù)的高度最小，即可保證樹(shù)的查找效率。同樣的序列 A，將其改為圖 1.2 的方式存儲(chǔ)，查找元素 6 時(shí)只需比較 3 次，查找效率提升一倍。

什么是平衡二叉樹(shù)AVL

可以看出當(dāng)節(jié)點(diǎn)數(shù)目一定，保持樹(shù)的左右兩端保持平衡，樹(shù)的查找效率最高。

這種左右子樹(shù)的高度相差不超過(guò) 1 的樹(shù)為平衡二叉樹(shù)。

2. 定義

平衡二叉查找樹(shù)：簡(jiǎn)稱平衡二叉樹(shù)。由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹(shù)，根據(jù)科學(xué)家的英文名也稱為 AVL 樹(shù)。它具有如下幾個(gè)性質(zhì)：

  1. 可以是空樹(shù)。

  2. 假如不是空樹(shù)，任何一個(gè)節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，并且高度之差的絕對(duì)值不超過(guò) 1。

平衡之意，如天平，即兩邊的分量大約相同。

例如圖 2.1 不是平衡二叉樹(shù)，因?yàn)楣?jié)點(diǎn) 60 的左子樹(shù)不是平衡二叉樹(shù)。

什么是平衡二叉樹(shù)AVL

圖 2.2 也不是平衡二叉樹(shù)，因?yàn)殡m然任何一個(gè)節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，但高度之差已經(jīng)超過(guò) 1 。

什么是平衡二叉樹(shù)AVL

圖 2.3 是平衡二叉樹(shù)。

什么是平衡二叉樹(shù)AVL

3. 平衡因子

定義：某節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)的高度(深度)差即為該節(jié)點(diǎn)的平衡因子（BF,Balance Factor），平衡二叉樹(shù)中不存在平衡因子大于 1 的節(jié)點(diǎn)。在一棵平衡二叉樹(shù)中，節(jié)點(diǎn)的平衡因子只能取 0 、1 或者 -1 ，分別對(duì)應(yīng)著左右子樹(shù)等高，左子樹(shù)比較高，右子樹(shù)比較高。

什么是平衡二叉樹(shù)AVL
什么是平衡二叉樹(shù)AVL
什么是平衡二叉樹(shù)AVL

4. 節(jié)點(diǎn)結(jié)構(gòu)

定義平衡二叉樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，這里計(jì)算每個(gè)節(jié)點(diǎn)的深度，通過(guò)深度的比較可得出是否平衡

    Tree parent; //該節(jié)點(diǎn)的父節(jié)點(diǎn)

    ElementType val; //節(jié)點(diǎn)值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {
        parent = NULL;
        depth = 0;
        lchild = rchild = NULL;
        this->val=val;
    }
};

5. AVL樹(shù)插入時(shí)的失衡與調(diào)整

圖 5.1 是一顆平衡二叉樹(shù)

什么是平衡二叉樹(shù)AVL

在此平衡二叉樹(shù)插入節(jié)點(diǎn) 99 ，樹(shù)結(jié)構(gòu)變?yōu)椋?/p>

什么是平衡二叉樹(shù)AVL

在動(dòng)圖 5.2 中，節(jié)點(diǎn) 66 的左子樹(shù)高度為 1，右子樹(shù)高度為 3，此時(shí)平衡因子為 -2，樹(shù)失去平衡。

在動(dòng)圖 5.2 中，以節(jié)點(diǎn) 66 為父節(jié)點(diǎn)的那顆樹(shù)就稱為 最小失衡子樹(shù)。

最小失衡子樹(shù)：在新插入的節(jié)點(diǎn)向上查找，以第一個(gè)平衡因子的絕對(duì)值超過(guò) 1 的節(jié)點(diǎn)為根的子樹(shù)稱為最小不平衡子樹(shù)。也就是說(shuō)，一棵失衡的樹(shù)，是有可能有多棵子樹(shù)同時(shí)失衡的。而這個(gè)時(shí)候，我們只要調(diào)整最小的不平衡子樹(shù)，就能夠?qū)⒉黄胶獾臉?shù)調(diào)整為平衡的樹(shù)。

平衡二叉樹(shù)的失衡調(diào)整主要是通過(guò)旋轉(zhuǎn)最小失衡子樹(shù)來(lái)實(shí)現(xiàn)的。根據(jù)旋轉(zhuǎn)的方向有兩種處理方式，左旋 與 右旋 。

旋轉(zhuǎn)的目的就是減少高度，通過(guò)降低整棵樹(shù)的高度來(lái)平衡。哪邊的樹(shù)高，就把那邊的樹(shù)向上旋轉(zhuǎn)。

5.1 左旋
什么是平衡二叉樹(shù)AVL

以圖 5.1.1 為例，加入新節(jié)點(diǎn) 99 后， 節(jié)點(diǎn) 66 的左子樹(shù)高度為 1，右子樹(shù)高度為 3，此時(shí)平衡因子為 -2。為保證樹(shù)的平衡，此時(shí)需要對(duì)節(jié)點(diǎn) 66 做出旋轉(zhuǎn)，因?yàn)橛易訕?shù)高度高于左子樹(shù)，對(duì)節(jié)點(diǎn)進(jìn)行左旋操作，流程如下：

（1）節(jié)點(diǎn)的右孩子替代此節(jié)點(diǎn)位置
（2）右孩子的左子樹(shù)變?yōu)樵摴?jié)點(diǎn)的右子樹(shù)
（3）節(jié)點(diǎn)本身變?yōu)橛液⒆拥淖笞訕?shù)

整個(gè)操作流程如動(dòng)圖 5.1.2 所示。

什么是平衡二叉樹(shù)AVL

  • 節(jié)點(diǎn)的右孩子替代此節(jié)點(diǎn)位置 —— 節(jié)點(diǎn) 66 的右孩子是節(jié)點(diǎn) 77 ，將節(jié)點(diǎn) 77 代替節(jié)點(diǎn) 66 的位置

  • 右孩子的左子樹(shù)變?yōu)樵摴?jié)點(diǎn)的右子樹(shù) —— 節(jié)點(diǎn) 77 的左子樹(shù)為節(jié)點(diǎn) 75，將節(jié)點(diǎn) 75 挪到節(jié)點(diǎn) 66 的右子樹(shù)位置

  • 節(jié)點(diǎn)本身變?yōu)橛液⒆拥淖笞訕?shù) —— 節(jié)點(diǎn) 66 變?yōu)榱斯?jié)點(diǎn) 77 的左子樹(shù)

5.2 右旋

右旋操作與左旋類似，操作流程為：

（1）節(jié)點(diǎn)的左孩子代表此節(jié)點(diǎn)
（2）節(jié)點(diǎn)的左孩子的右子樹(shù)變?yōu)楣?jié)點(diǎn)的左子樹(shù)
（3）將此節(jié)點(diǎn)作為左孩子節(jié)點(diǎn)的右子樹(shù)。

什么是平衡二叉樹(shù)AVL

6. AVL樹(shù)的四種插入節(jié)點(diǎn)方式

假設(shè)一顆 AVL 樹(shù)的某個(gè)節(jié)點(diǎn)為 A，有四種操作會(huì)使 A 的左右子樹(shù)高度差大于 1，從而破壞了原有 AVL 樹(shù)的平衡性。平衡二叉樹(shù)插入節(jié)點(diǎn)的情況分為以下四種：

什么是平衡二叉樹(shù)AVL

具體分析如下：

6.1 A的左孩子的左子樹(shù)插入節(jié)點(diǎn)(LL)

只需要執(zhí)行一次右旋即可。

什么是平衡二叉樹(shù)AVL

實(shí)現(xiàn)代碼如下：

//LL型調(diào)整函數(shù)
//返回:新父節(jié)點(diǎn)
Tree LL_rotate(Tree node){
    //node為離操作節(jié)點(diǎn)最近的失衡的節(jié)點(diǎn)
    Tree parent=NULL,son;
    //獲取失衡節(jié)點(diǎn)的父節(jié)點(diǎn)
    parent=node->parent;
    //獲取失衡節(jié)點(diǎn)的左孩子
    son=node->lchild;
    //設(shè)置son節(jié)點(diǎn)右孩子的父指針
    if (son->rchild!=NULL)  son->rchild->parent=node;
    //失衡節(jié)點(diǎn)的左孩子變更為son的右孩子
    node->lchild=son->rchild;
    //更新失衡節(jié)點(diǎn)的高度信息
    update_depth(node);
    //失衡節(jié)點(diǎn)變成son的右孩子
    son->rchild=node;
    //設(shè)置son的父節(jié)點(diǎn)為原失衡節(jié)點(diǎn)的父節(jié)點(diǎn)
    son->parent=parent;
    //如果失衡節(jié)點(diǎn)不是根節(jié)點(diǎn)，則開(kāi)始更新父節(jié)點(diǎn)
    if (parent!=NULL){
        //如果父節(jié)點(diǎn)的左孩子是失衡節(jié)點(diǎn)，指向現(xiàn)在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
             //父節(jié)點(diǎn)的右孩子是失衡節(jié)點(diǎn)
              parent->rchild=son;
        }
     }
    //設(shè)置失衡節(jié)點(diǎn)的父親
    node->parent=son;
    //更新son節(jié)點(diǎn)的高度信息
    update_depth(son);
    return son;
}
6.2 A的右孩子的右子樹(shù)插入節(jié)點(diǎn)(RR)

只需要執(zhí)行一次左旋即可。

什么是平衡二叉樹(shù)AVL

實(shí)現(xiàn)代碼如下：

//RR型調(diào)整函數(shù)
//返回新父節(jié)點(diǎn)
Tree RR_rotate(Tree node){
    //node為離操作節(jié)點(diǎn)最近的失衡的節(jié)點(diǎn)
    Tree parent=NULL,son;
    //獲取失衡節(jié)點(diǎn)的父節(jié)點(diǎn)
    parent=node->parent;
    //獲取失衡節(jié)點(diǎn)的右孩子
    son=node->rchild;
    //設(shè)置son節(jié)點(diǎn)左孩子的父指針
    if (son->lchild!=NULL){
          son->lchild->parent=node;
    }
    //失衡節(jié)點(diǎn)的右孩子變更為son的左孩子
    node->rchild=son->lchild;
    //更新失衡節(jié)點(diǎn)的高度信息
    update_depth(node);
    //失衡節(jié)點(diǎn)變成son的左孩子
    son->lchild=node;
    //設(shè)置son的父節(jié)點(diǎn)為原失衡節(jié)點(diǎn)的父節(jié)點(diǎn)
    son->parent=parent;
    //如果失衡節(jié)點(diǎn)不是根節(jié)點(diǎn)，則開(kāi)始更新父節(jié)點(diǎn)
    if (parent!=NULL){
        //如果父節(jié)點(diǎn)的左孩子是失衡節(jié)點(diǎn)，指向現(xiàn)在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
            //父節(jié)點(diǎn)的右孩子是失衡節(jié)點(diǎn)
            parent->rchild=son;
        } 
    }
    //設(shè)置失衡節(jié)點(diǎn)的父親
    node->parent=son;
    //更新son節(jié)點(diǎn)的高度信息
    update_depth(son);
    return son;
}
6.3 A的左孩子的右子樹(shù)插入節(jié)點(diǎn)(LR)

若 A 的左孩子節(jié)點(diǎn) B 的右子樹(shù) E 插入節(jié)點(diǎn) F ，導(dǎo)致節(jié)點(diǎn) A 失衡，如圖：

什么是平衡二叉樹(shù)AVL

A 的平衡因子為 2 ，若仍按照右旋調(diào)整，則變化后的圖形為這樣：

什么是平衡二叉樹(shù)AVL

經(jīng)過(guò)右旋調(diào)整發(fā)現(xiàn)，調(diào)整后樹(shù)仍然失衡，說(shuō)明這種情況單純的進(jìn)行右旋操作不能使樹(shù)重新平衡。那么這種插入方式需要執(zhí)行兩步操作，使得旋轉(zhuǎn)之后為 原來(lái)根節(jié)點(diǎn)的左孩子的右孩子作為新的根節(jié)點(diǎn)。

（1）對(duì)失衡節(jié)點(diǎn) A 的左孩子 B 進(jìn)行左旋操作，即上述 RR 情形操作。
（2）對(duì)失衡節(jié)點(diǎn) A 做右旋操作，即上述 LL 情形操作。

調(diào)整過(guò)程如下：

什么是平衡二叉樹(shù)AVL
什么是平衡二叉樹(shù)AVL

也就是說(shuō)，經(jīng)過(guò)這兩步操作，使得 原來(lái)根節(jié)點(diǎn)的左孩子的右孩子 E 節(jié)點(diǎn)成為了新的根節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

//LR型，先左旋轉(zhuǎn)，再右旋轉(zhuǎn)
//返回：新父節(jié)點(diǎn)
Tree LR_rotate(Tree node){
    RR_rotate(node->lchild);
    return LL_rotate(node);
}
6.4 A的右孩子的左子樹(shù)插入節(jié)點(diǎn)(RL)

右孩子插入左節(jié)點(diǎn)的過(guò)程與左孩子插入右節(jié)點(diǎn)過(guò)程類似，也是需要執(zhí)行兩步操作，使得旋轉(zhuǎn)之后為 原來(lái)根節(jié)點(diǎn)的右孩子的左孩子作為新的根節(jié)點(diǎn)。

（1）對(duì)失衡節(jié)點(diǎn) A 的右孩子 C 進(jìn)行右旋操作，即上述 LL 情形操作。
（2）對(duì)失衡節(jié)點(diǎn) A 做左旋操作，即上述 RR 情形操作。

什么是平衡二叉樹(shù)AVL
什么是平衡二叉樹(shù)AVL
什么是平衡二叉樹(shù)AVL

也就是說(shuō)，經(jīng)過(guò)這兩步操作，使得 原來(lái)根節(jié)點(diǎn)的右孩子的左孩子 D 節(jié)點(diǎn)成為了新的根節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

//RL型，先右旋轉(zhuǎn)，再左旋轉(zhuǎn)
//返回:新父節(jié)點(diǎn)
Tree RL_rotate(Tree node){
    LL_rotate(node->rchild);
    return RR_rotate(node);
}

補(bǔ)充：

上述四種插入方式的代碼實(shí)現(xiàn)的輔助代碼如下：

//更新當(dāng)前深度
void update_depth(Tree node){
    if (node==NULL){
        return;
    }else{
        int depth_Lchild=get_balance(node->lchild); //左孩子深度
        int depth_Rchild=get_balance(node->rchild); //右孩子深度
        node->depth=max(depth_Lchild,depth_Rchild)+1;
    }
}

//獲取當(dāng)前節(jié)點(diǎn)的深度
int get_balance(Tree node){
    if (node==NULL){
         return 0;
    }
    return node->depth;
}

//返回當(dāng)前平衡因子
int is_balance(Tree node){
    if (node==NULL){
         return 0;
    }else{
         return get_balance(node->lchild)-get_balance(node->rchild); 
    }
}
6.5 小總結(jié)

  1. 在所有的不平衡情況中，都是按照先 尋找最小不平衡樹(shù)，然后 尋找所屬的不平衡類別，再 根據(jù) 4 種類別進(jìn)行固定化程序的操作。

  2. LL , LR ，RR ，RL其實(shí)已經(jīng)為我們提供了最后哪個(gè)節(jié)點(diǎn)作為新的根指明了方向。如 LR 型最后的根節(jié)點(diǎn)為原來(lái)的根的左孩子的右孩子，RL 型最后的根節(jié)點(diǎn)為原來(lái)的根的右孩子的左孩子。只要記住這四種情況，可以很快地推導(dǎo)出所有的情況。

  3. 維護(hù)平衡二叉樹(shù)，最麻煩的地方在于平衡因子的維護(hù)。建議讀者們根據(jù)小吳提供的圖片和動(dòng)圖，自己動(dòng)手畫(huà)一遍，這樣可以更加感性的理解操作。

7. AVL樹(shù)的四種刪除節(jié)點(diǎn)方式

AVL 樹(shù)和二叉查找樹(shù)的刪除操作情況一致，都分為四種情況：

（1）刪除葉子節(jié)點(diǎn)
（2）刪除的節(jié)點(diǎn)只有左子樹(shù)
（3）刪除的節(jié)點(diǎn)只有右子樹(shù)
（4）刪除的節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)

只不過(guò) AVL 樹(shù)在刪除節(jié)點(diǎn)后需要重新檢查平衡性并修正，同時(shí)，刪除操作與插入操作后的平衡修正區(qū)別在于，插入操作后只需要對(duì)插入棧中的彈出的第一個(gè)非平衡節(jié)點(diǎn)進(jìn)行修正，而刪除操作需要修正棧中的所有非平衡節(jié)點(diǎn)。

刪除操作的大致步驟如下：

  • 以前三種情況為基礎(chǔ)嘗試刪除節(jié)點(diǎn)，并將訪問(wèn)節(jié)點(diǎn)入棧。

  • 如果嘗試刪除成功，則依次檢查棧頂節(jié)點(diǎn)的平衡狀態(tài)，遇到非平衡節(jié)點(diǎn)，即進(jìn)行旋轉(zhuǎn)平衡，直到?？?。

  • 如果嘗試刪除失敗，證明是第四種情況。這時(shí)先找到被刪除節(jié)點(diǎn)的右子樹(shù)最小節(jié)點(diǎn)并刪除它，將訪問(wèn)節(jié)點(diǎn)繼續(xù)入棧。

  • 再依次檢查棧頂節(jié)點(diǎn)的平衡狀態(tài)和修正直到棧空。

對(duì)于刪除操作造成的非平衡狀態(tài)的修正，可以這樣理解：對(duì)左或者右子樹(shù)的刪除操作相當(dāng)于對(duì)右或者左子樹(shù)的插入操作，然后再對(duì)應(yīng)上插入的四種情況選擇相應(yīng)的旋轉(zhuǎn)就好了。

7.1 刪除葉子節(jié)點(diǎn)

處理步驟：

①、將該節(jié)點(diǎn)直接從樹(shù)中刪除；

②、其父節(jié)點(diǎn)的子樹(shù)高度的變化將導(dǎo)致父節(jié)點(diǎn)平衡因子的變化，通過(guò)向上檢索并推算其父節(jié)點(diǎn)是否失衡；

③、如果其父節(jié)點(diǎn)未失衡，則繼續(xù)向上檢索推算其父節(jié)點(diǎn)的父節(jié)點(diǎn)是否失衡…如此反復(fù)②的判斷，直到根節(jié)點(diǎn) ；如果向上推算過(guò)程中發(fā)現(xiàn)了失衡的現(xiàn)象，則進(jìn)行 ④ 的處理；

④、如果其父節(jié)點(diǎn)失衡，則判斷是哪種失衡類型 [LL、LR、RR、RL] ，并對(duì)其進(jìn)行相應(yīng)的平衡化處理。如果平衡化處理結(jié)束后，發(fā)現(xiàn)與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的高度發(fā)生變化，則繼續(xù)進(jìn)行 ② 的檢索推算；如果與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的高度一致時(shí)，則可說(shuō)明父節(jié)點(diǎn)的父節(jié)點(diǎn)及祖先節(jié)點(diǎn)的平衡因子將不會(huì)有變化，因此可以退出處理；

什么是平衡二叉樹(shù)AVL

具體數(shù)字演示：

什么是平衡二叉樹(shù)AVL
7.2  & 7.3 刪除的節(jié)點(diǎn)只有左子樹(shù)或右子樹(shù)

處理步驟：

①、將左子樹(shù)（右子樹(shù)）替代原有節(jié)點(diǎn) C 的位置；

②、節(jié)點(diǎn)  C 被刪除后，則以 C 的父節(jié)點(diǎn)  B 為起始推算點(diǎn)，依此向上檢索推算各節(jié)點(diǎn)（父、祖先）是否失衡；

③、如果其父節(jié)點(diǎn)未失衡，則繼續(xù)向上檢索推算其父節(jié)點(diǎn) 的父節(jié)點(diǎn) 是否失衡…如此反復(fù) ② 的判斷，直到根節(jié)點(diǎn) ；如果向上推算過(guò)程中發(fā)現(xiàn)了失衡的現(xiàn)象，則進(jìn)行 ④ 的處理；

④、如果其父節(jié)點(diǎn)失衡，則判斷是哪種失衡類型 [LL、LR、RR、RL] ，并對(duì)其進(jìn)行相應(yīng)的平衡化處理。如果平衡化處理結(jié)束后，發(fā)現(xiàn)與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的高度發(fā)生變化，則繼續(xù)進(jìn)行 ② 的檢索推算；如果與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的高度一致時(shí)，則可說(shuō)明父節(jié)點(diǎn)的父節(jié)點(diǎn)及祖先節(jié)點(diǎn)的平衡因子將不會(huì)有變化，因此可以退出處理；

什么是平衡二叉樹(shù)AVL
7.4 刪除的節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)

處理步驟：

①、找到被刪節(jié)點(diǎn) B 和替代節(jié)點(diǎn) BLR (節(jié)點(diǎn) B 的前繼節(jié)點(diǎn)或后繼節(jié)點(diǎn) —— 在此選擇 前繼)；

②、將替代節(jié)點(diǎn) BLR 的值賦給節(jié)點(diǎn) B ，再把替代節(jié)點(diǎn) BLR 的左孩子 BLRL 替換替代節(jié)點(diǎn) BLR 的位置；

③、以 BLR 的父節(jié)點(diǎn) BL 為起始推算點(diǎn)，依此向上檢索推算父節(jié)點(diǎn)或祖先節(jié)點(diǎn)是否失衡；

④、如果其父節(jié)點(diǎn)未失衡，則繼續(xù)向上檢索推算其父節(jié)點(diǎn)的父節(jié)點(diǎn)是否失衡…如此反復(fù)③的判斷，直到根節(jié)點(diǎn)；如果向上推算過(guò)程中發(fā)現(xiàn)了失衡的現(xiàn)象，則進(jìn)行⑤的處理；

⑤、如果其父節(jié)點(diǎn)失衡，則判斷是哪種失衡類型  [LL、LR、RR、RL]  ，并對(duì)其進(jìn)行相應(yīng)的平衡化處理。如果平衡化處理結(jié)束后，發(fā)現(xiàn)與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的高度發(fā)生變化，則繼續(xù)進(jìn)行 ② 的檢索推算；如果與原來(lái)以父節(jié)點(diǎn)為根節(jié)點(diǎn)的高度一致時(shí)，則可說(shuō)明父節(jié)點(diǎn)的父節(jié)點(diǎn)及祖先節(jié)點(diǎn)的平衡因子將不會(huì)有變化，因此可以退出處理；

什么是平衡二叉樹(shù)AVL

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

標(biāo)題名稱：什么是平衡二叉樹(shù)AVL-創(chuàng)新互聯(lián)
URL鏈接：http://www.muchs.cn/article14/pcege.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、網(wǎng)站設(shè)計(jì)、自適應(yīng)網(wǎng)站、企業(yè)網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

綿陽(yáng)服務(wù)器托管