在按照二叉查找樹（二叉查找樹（BST：Binary Search Tree） ）的方式插入元素構建一個平衡二叉樹（平衡二叉樹 ）時，可能會出現不平衡的現象。可以根據新插入節點與最低不平衡節點之間的位置關系進行相應的調整。

我們先把需要調整的類型分為四種情況：LL型、RR型、LR型、RL型。使用圖形示例與實際代碼結合的方式對不平衡二叉樹進行旋轉。

定義一個樹節點：

平衡二叉樹節點定義

LL型調整

由于在y_6的左孩子(L)的左子樹(L)上插入新結點2，使原來平衡二叉樹變得不平衡，此時y_6的平衡因子由1增至2。顯然，按照大小關系，結點x_3應作為新的根結點，1和y_6兩個節點分别作為左右孩子節點才能平衡，y_6結點就好像是繞結點x_3順時針旋轉一樣。

LL型調整

總結一下LL型調整的一般步驟：

1. 将y_6（新的不平衡節點）的左孩子x_3提升為新的根節點；
2. 将原來的根節點y_6降為x_3的右孩子
3. 各子樹按照大小關系連接（y_6的右孩子，x_3的左孩子不變，x_3的右孩子調整為y_6的左孩子）

LL型旋轉代碼實現

RR型調整

由于在y_2的右孩子(R)的右子樹(L)上插入新結點5，使原來平衡二叉樹變得不平衡，此時y_2的平衡因子由1增至2。顯然，按照大小關系，結點x_4應作為新的根結點，y_2和6兩個節點分别作為左右孩子節點才能平衡，y_2結點就好像是繞結點x_4逆時針旋轉一樣。

RR型調整

總結一下RR型調整的一般步驟：

1. 将y_2（新的不平衡節點）的右孩子x_4提升為新的根節點；
2. 将原來的根節點y_2降為x_4的左孩子
3. 各子樹按照大小關系連接（y_6的左孩子，x_4的右孩子不變，x_4的左孩子調整為y_2的右孩子）

RR型旋轉代碼實現

LR型調整

由于在6的左孩子(L)的右子樹(R)上插入新結點3，使原來平衡二叉樹變得不平衡，此時6的平衡因子由1增至2。顯然，按照大小關系，結點x_4應作為新的根結點，y_2和6兩個節點分别作為左右孩子節點才能平衡。

LR型調整

總結一下LR型調整的一般步驟：

1. 将y_2假設為新的根節點；
2. 将以y_2為根的二叉樹進行RR型旋轉；
3. 再對以y_6為根的二叉樹進行LL型旋轉；

LR型旋轉代碼實現

RL型調整

由于在2的右孩子(R)的左子樹(L)上插入新結點4，使原來平衡二叉樹變得不平衡，此時2的平衡因子由1增至2。顯然，按照大小關系，結點3應作為新的根結點，2和5兩個節點分别作為左右孩子節點才能平衡。

RL型調整

總結一下RL型調整的一般步驟：

1. 将x_5假設為新的根節點；
2. 将以x_5為根的二叉樹進行LL型旋轉；
3. 再對以y_2為根的二叉樹進行RR型旋轉；

RL型旋轉代碼實現

理解好平衡二叉樹的旋轉，對後邊學習紅黑樹有非常大的幫助。下一篇文章學習，如何在構建和删除平衡二叉樹的過程中維持二叉樹一直平衡。

平衡二叉樹

如何優雅地畫好二叉樹

二叉樹遍曆的思維導圖

二叉樹的層序遍曆及應用

二叉查找樹（BST：Binary Search Tree）

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!