?

AVL樹平衡旋轉詳解

概述

? AVL樹又叫做平衡二叉樹。前言部分我也有說到，AVL樹的前提是二叉排序樹(BST或叫做二叉查找樹)。由于在生成BST樹的過程中可能會出現(xiàn)線型樹結構，比如插入的順序是：1, 2, 3, 4, 5, 6, 7..., n。在BST樹中，比較理想的狀況是每個子樹的左子樹和右子樹的高度相等，此時搜索的時間復雜度是log(N)。可是，一旦這棵樹演化成了線型樹的時候，這個理想的情況就不存在了，此時搜索的時間復雜度是O(N)，在數(shù)據(jù)量很大的情況下，我們并不愿意看到這樣的結果。

? 現(xiàn)在我們要做的事就是讓BST在創(chuàng)建的過程中不要向線型樹發(fā)展。方法就是讓其在添加新節(jié)點的時候，不斷調整樹的平衡狀態(tài)。

? 定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

?

AVL樹實現(xiàn)

1.節(jié)點失衡

? 我們對于節(jié)點平衡有這樣的定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。而這里提到的高度差，就是我們下面會引入的平衡因子：BF（balance factor）。

? 因為AVL樹說到底還是一個二叉樹，只有兩個子節(jié)點。而且節(jié)點失衡的發(fā)生，是因為有一個新節(jié)點的插入，這個新插入的節(jié)點導致了某些節(jié)點左右子節(jié)點高度的不一致。所以我們可以枚舉出以下4種情況的失衡狀態(tài)。

(1)在一個節(jié)點的左子樹的左子樹上插入一個新節(jié)點。即LL。在這種情況下，我們可以通過將節(jié)點右旋使其平衡。如圖-2所示

圖-2 LL單右旋操作

原A的左孩子B變?yōu)楦附Y點，A變?yōu)槠溆液⒆?#xff0c;而原B的右子樹變?yōu)锳的左子樹，注意旋轉之后Brh是A的左子樹。

?

(2)在一個節(jié)點的右子樹的右子樹上插入一個新節(jié)點。即RR。在這種情況下，我們可以通過將節(jié)點左旋使其平衡。如圖-3所示；

圖-3 RR單左旋操作

這時只需要把樹向左旋轉一次即可，如圖所示，原A右孩子B變?yōu)楦附Y點，A變?yōu)槠渥蠛⒆?#xff0c;而原B的左子樹Blh將變?yōu)锳的右子樹。

(3)在一個節(jié)點的左子樹的右子樹上插入一個新節(jié)點。即LR。在這種情況下，我們不能直接通過將節(jié)點左旋或右來使其平衡了。這里需要兩步來完成，先讓樹中高度較低的進行一次左旋（RR型），這個時候就變成了LL了。再進行一次單右旋操作即可。如圖-4所示；

圖-4 LR先左旋再右旋操作

?

這時需要旋轉兩次，僅一次的旋轉是不能夠使二叉樹再次平衡。如圖所示，在B節(jié)點按照RR型向左旋轉一次之后，二叉樹在A節(jié)點仍然不能保持平衡，這時還需要再向右旋轉一次。

?

(4)在一個節(jié)點的右子樹的左子樹上插入一個新節(jié)點。即RL。在這種情況下，我們不能直接通過將節(jié)點左旋或右來使其平衡了。這里需要兩步來完成，先讓樹中高度較低的進行一次右旋，這個時候就變成了RR了。再進行一次單左旋操作即可。如圖-5所示；

圖-5 RL先右旋再左旋操作

?

平衡二叉樹某一節(jié)點的右孩子的左子樹上插入一個新的節(jié)點，使得該節(jié)點不再平衡。同樣，這時需要旋轉兩次，旋轉方向剛好同LR型相反。

?

? 從上面對節(jié)點失衡的說明，以及圖解。我想你已經對旋轉的操作有了一個大概地認識了吧。從圖中我們也可以看出，LL型和RR型、LR型和RL型是兩個行為很相似地操作。其實他們互為對稱。

代碼見這里

轉載于:https://www.cnblogs.com/ldq2016/p/10505036.html

總結

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

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