1、AVL樹(shù)

成都創(chuàng)新互聯(lián)主要從事成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)漢南,十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專(zhuān)業(yè),歡迎來(lái)電咨詢(xún)建站服務(wù):18980820575

 AVL樹(shù)首先是一顆二叉搜索樹(shù)，滿(mǎn)足其所有性質(zhì)，AVL樹(shù)又叫做高度平衡的二叉搜索樹(shù);

 AVL: 動(dòng)態(tài)搜索樹(shù);

 平衡因子bf: 右樹(shù)高度 — 左樹(shù)高度; bf的取值只能是1, 0, -1;

 左右子樹(shù)都得符合平衡因子, 若不符, 的通過(guò)旋轉(zhuǎn)來(lái)調(diào)整平衡因子;

2、四種旋轉(zhuǎn)

 (1)、單旋轉(zhuǎn)---->直線(xiàn)型

 (2)、雙旋轉(zhuǎn)----->折線(xiàn)型

 要進(jìn)行兩次旋轉(zhuǎn)的調(diào)整，判斷折線(xiàn)，看哪邊突出(就是三個(gè)結(jié)點(diǎn)中有一個(gè)突出的方向)，就先向哪邊旋轉(zhuǎn)；

 四種旋轉(zhuǎn)，每次就只針對(duì)兩個(gè)結(jié)點(diǎn)(要進(jìn)行旋轉(zhuǎn)的2個(gè)結(jié)點(diǎn))；然后將上面的分支掛到旋轉(zhuǎn)后的L/R上即可。

3、畫(huà)平衡樹(shù)

 根據(jù)一組數(shù)字，畫(huà)出其AVL樹(shù)：16 3 7 11 9 26 18 14 15

 畫(huà)AVL樹(shù)，首先其實(shí)是一顆搜索二叉樹(shù); 按照其比左孩子大，比右孩子小畫(huà)就行; 有了平衡因子，不滿(mǎn)足時(shí)在旋轉(zhuǎn)調(diào)整即可。

 畫(huà)法如下：

4、四種旋轉(zhuǎn)的實(shí)現(xiàn)

 永遠(yuǎn)只考慮三層以?xún)?nèi)結(jié)點(diǎn)的旋轉(zhuǎn)；

 C++實(shí)現(xiàn)其所有代碼：

 (1)、右單旋

 代碼如下(代碼中ptr代表的是要bf不為平衡處，指向要進(jìn)行旋轉(zhuǎn)的結(jié)點(diǎn))：

void RotateR(AVLNode<Type> *&ptr){
        AVLNode<Type> *subR = ptr;
        ptr = ptr->leftChild;  //通過(guò)引用直接修改指向1的指針(可能是上一個(gè)的左孩子/右孩子)
        subR->leftChild = ptr->rightChild;
        ptr->rightChild = subR;
        ptr->bf = subR->bf = 0;
    }

 (2)、左單旋

 左單旋與右單旋的代碼是鏡像的，并且想法是一致的; 所以代碼如下：

void RotateL(AVLNode<Type> *&ptr){
    AVLNode<Type> *subL = ptr;
    ptr = subL->rightChild;  //同樣是經(jīng)過(guò)引用修改
    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    subL->bf = ptr->bf = 0;
}

 在進(jìn)行單旋轉(zhuǎn)時(shí)，因?yàn)槭窃诓迦?，其自身的bf不用調(diào)整，初始化為0;修改的是根和另一個(gè)結(jié)點(diǎn)的bf;

 (3)、先左后右單旋

 在進(jìn)行雙旋轉(zhuǎn)時(shí)，首先明確左/右孩子，根結(jié)點(diǎn)的最終情況, 在進(jìn)行調(diào)整;并且在雙旋轉(zhuǎn)時(shí)每個(gè)結(jié)點(diǎn)的bf都得改變；

 平衡因子在這不好考慮，有點(diǎn)復(fù)雜，具體分析如下：

 平衡因子的考慮關(guān)鍵在：ptr有左樹(shù)/右樹(shù)，對(duì)應(yīng)上去則subL/sunR原先必有一個(gè)分支結(jié)點(diǎn); ptr沒(méi)有孩子結(jié)點(diǎn)，對(duì)應(yīng)subR/subL原先也沒(méi)有分支結(jié)點(diǎn)；

 代碼如下：

void RotateLR(AVLNode<Type> *&ptr){
    AVLNode<Type> *subR = ptr;    //最終右孩子
    AVLNode<Type> *subL = ptr->leftChild; //最終左孩子
    ptr = subL->rightChild;  //最終根節(jié)點(diǎn),因?yàn)橐?最終這個(gè)修改了指向根結(jié)點(diǎn)，完成了連接;

    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    if(ptr->bf <= 0){
        subL->bf = 0;  //此時(shí)的情況就是,自己ptr原先沒(méi)有掛結(jié)點(diǎn)或者是左樹(shù)掛上結(jié)點(diǎn)，而滿(mǎn)足這種情況下，sunL原先必有左樹(shù)，此時(shí)在掛上右樹(shù)，所以為0;
    }else{
        subL->bf = -1;  //此時(shí)的情況是ptr有右孩子，而sunL有左孩子，滿(mǎn)足這種情況，所以bf只能是-1;
    }

    subR->leftChild = ptr->rightChild;
    ptr->rightChild = subR;
    if(ptr->bf == -1){  //當(dāng)結(jié)點(diǎn)ptr其只有左孩子時(shí)，
        subR->bf = 1;  //sunR必定有右孩子,所以此時(shí)為1
    }else{
        subR->bf = 0; //當(dāng)ptr沒(méi)有孩子結(jié)點(diǎn)或有一個(gè)右孩子時(shí)(此時(shí)subR必有右樹(shù))，所以此時(shí)為0;
    }

    ptr->bf = 0;   //調(diào)整后根的bf永遠(yuǎn)是0;
}

 (4)、先右后左單旋

 與上一個(gè)雙旋的代碼是鏡像的, 并且想法是一致的; 平衡因子的修改有點(diǎn)不一樣，注意一下就行， 所以代碼如下:

void RotateRL(AVLNode<Type> *&ptr){
    AVLNode<Type> *subL = ptr;
    AVLNode<Type> *subR = ptr->rightChild;
    ptr = subR->leftChild;

    subR->leftChild = ptr->rightChild;
    ptr->rightChild = subR;
    if(ptr->bf >=0){
        subR->bf = 0;
    }else{
        subR->bf = 1;
    }

    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    if(ptr->bf == 1){
        subL->bf = -1;
    }else{
        subL->bf = 0;
    }

    ptr->bf = 0;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前題目：AVL樹(shù)之旋轉(zhuǎn)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)地址：http://www.rwnh.cn/article18/posgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站營(yíng)銷(xiāo)、動(dòng)態(tài)網(wǎng)站、網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、用戶(hù)體驗(yàn)

廣告

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