AVL樹之旋轉

1、AVL樹

  AVL樹首先是一顆二叉搜尋樹，滿足其所有性質，AVL樹又叫做高度平衡的二叉搜尋樹;

  AVL: 動态搜尋樹;

  平衡因子bf: 右樹高度 — 左樹高度; bf的取值隻能是1, 0, -1;

  左右子樹都得符合平衡因子, 若不符, 的通過旋轉來調整平衡因子;

2、四種旋轉

  (1)、單旋轉---->直線型

  (2)、雙旋轉----->折線型

  要進行兩次旋轉的調整，判斷折線，看哪邊突出(就是三個結點中有一個突出的方向)，就先向哪邊旋轉；

  四種旋轉，每次就隻針對兩個結點(要進行旋轉的2個結點)；然後将上面的分支挂到旋轉後的L/R上即可。

3、畫平衡樹

  根據一組數字，畫出其AVL樹：16 3 7 11 9 26 18 14 15

  畫AVL樹，首先其實是一顆搜尋二叉樹; 按照其比左孩子大，比右孩子小畫就行; 有了平衡因子，不滿足時在旋轉調整即可。

  畫法如下：

4、四種旋轉的實作

  永遠隻考慮三層以内結點的旋轉；

  C++實作其所有代碼：

  (1)、右單旋

  代碼如下(代碼中ptr代表的是要bf不為平衡處，指向要進行旋轉的結點)：

void RotateR(AVLNode<Type> *&ptr){
        AVLNode<Type> *subR = ptr;
        ptr = ptr->leftChild;  //通過引用直接修改指向1的指針(可能是上一個的左孩子/右孩子)
        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;  //同樣是經過引用修改
    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    subL->bf = ptr->bf = 0;
}      

  在進行單旋轉時，因為是在插入，其自身的bf不用調整，初始化為0;修改的是根和另一個結點的bf;

  (3)、先左後右單旋

  在進行雙旋轉時，首先明确左/右孩子，根結點的最終情況, 在進行調整;并且在雙旋轉時每個結點的bf都得改變；

  平衡因子在這不好考慮，有點複雜，具體分析如下：

  平衡因子的考慮關鍵在：ptr有左樹/右樹，對應上去則subL/sunR原先必有一個分支結點; ptr沒有孩子結點，對應subR/subL原先也沒有分支結點；

  代碼如下：

void RotateLR(AVLNode<Type> *&ptr){
    AVLNode<Type> *subR = ptr;    //最終右孩子
    AVLNode<Type> *subL = ptr->leftChild; //最終左孩子
    ptr = subL->rightChild;  //最終根節點,因為引用,最終這個修改了指向根結點，完成了連接配接;

    subL->rightChild = ptr->leftChild;
    ptr->leftChild = subL;
    if(ptr->bf <= 0){
        subL->bf = 0;  //此時的情況就是,自己ptr原先沒有挂結點或者是左樹挂上結點，而滿足這種情況下，sunL原先必有左樹，此時在挂上右樹，是以為0;
    }else{
        subL->bf = -1;  //此時的情況是ptr有右孩子，而sunL有左孩子，滿足這種情況，是以bf隻能是-1;
    }

    subR->leftChild = ptr->rightChild;
    ptr->rightChild = subR;
    if(ptr->bf == -1){  //當結點ptr其隻有左孩子時，
        subR->bf = 1;  //sunR必定有右孩子,是以此時為1
    }else{
        subR->bf = 0; //當ptr沒有孩子結點或有一個右孩子時(此時subR必有右樹)，是以此時為0;
    }

    ptr->bf = 0;   //調整後根的bf永遠是0;
}      

  (4)、先右後左單旋

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;
}