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

轉載于:https://blog.51cto.com/wait0804/1839051

總結

以上是生活随笔為你收集整理的AVL树之旋转的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。