動畫 | 什麼是AVL樹？ - ⎝⎛CodingNote.cc ⎞⎠

首先介紹下二分搜索樹，它又名有序二叉查找樹，它的特點是左子樹的節點值要小於父節點值，右子樹的節點值要大於父節點值。基於這樣的特點，我們在查找某個節點的時候，可以採取二分查找的思想快速找到這個節點，時間複雜度期望值是為O(log n)，但是它有最壞的的情況下。

例如，輸入數組[9，7，5，3，1]，如果要滿足二分搜索樹的規則插入一個個節點，這樣的二叉樹會退化成一條線性表，待會查找元素的時候時間複雜度已達O(N)。

所以針對這種情況，我們引申出了平衡二分搜索樹，它每個節點的左右子樹高度差不會超過1，它能在O(log n)內完成插入、查找和刪除操作。平衡二分搜索樹種類比較多，AVL樹是其中的一種，但是它是最早被發明的自平衡二分搜索樹。

AVL樹也會被稱為高度平衡樹，因為它比二分搜索樹多了一個特點：任一節點的左右子樹高度差最大為1。如果以後去參賽，可以根據數據的情況更改高度差最大值，甚至也可以制定高度差相差幾倍。

計算高度和平衡因子

計算高度是從葉子節點開始的，起始高度默認為1。然後計算葉子節點的父節點高度，比較左右子樹的高度，採取最大值再加1就是這個節點的高度了。依此類推，直到整個樹的頂點。

計算平衡因子也跟計算高度從葉子節點開始的，然後依次往父節點計算。節點的平衡因子公式是它左子樹的高度減去它右子樹的高度，有時候也會相反，可負數。

帶有平衡因子-1、0或1的節點被認為是平衡的，即期望平衡節點的平衡因子的絕對值不會大於高度差最大值的。帶有平衡因子-2或2的節點被認為是不平衡的，意味著需要重新調整這個樹。平衡因子的絕對值最大值不會超過高度差最大值+1，說明這個數的任一節點的平衡因子不會出現-3或3。

如果改定高度差最大值為2，那麼平衡因子會出現-3或3了，同時這個節點也是不平衡的，需要旋轉調整。帶有平衡因子-2、-1、0、1或2則被認為是平衡的。

動畫

Code

左旋轉和右旋轉

AVL樹調整不平衡的節點分為左旋轉和右旋轉，卻分四種情況：LL、RR、LR和RL。其中L是左旋轉，R是右旋轉。如何採取使用哪一種情況則看插入的節點在哪裡。

如果插入的節點是再T2子樹裡面，T1、T2、T3和T4都代表一個子樹。T2裡面插入一個節點，這個子樹的高度加1，再計算父節點的平衡因子。如果這個節點是平衡的，則更新這個節點的高度。然後再往上計算父節點的平衡因子，接著判斷是否平衡，如果是平衡的則更新高度，直到是不平衡的則進行旋轉操作。

看上面圖中，節點9是不平衡的，需要進行旋轉操作。那如何進行哪種情況操作呢？

看左右子樹哪一個子樹插入了一個節點，節點5的左子樹高度加1，導致節點5的平衡因子由0變成1。為了讓節點5的平衡因子可以由1變成0，則希望節點5的右子樹可以高度加1，所以就向節點5的父節點9進行右旋轉操作，重新調整平衡因子，節點5的平衡因子恢復為0。

如果是下面情況，則不能單純的進行右旋轉操作了。看下面途中，插入一個節點是在節點3右子樹發生的，節點3的平衡因子由0變成-1，應該希望是節點3左子樹的高度可以高點。所以對節點3進行左旋轉操作。

對節點3進行左旋轉操作之後，更新相應節點的高度和平衡因子。看下面圖中，發現節點5的平衡因子由-1變成1了，為了讓1變成0，則希望是節點5的右子樹高度可以高一點，所以對節點9進行右旋轉操作。

進行LR旋轉的操作如下圖，節點5的平衡因子已恢復為0，節點9由開始的不平衡已變成平衡。

動畫

Code

刪除節點

AVL樹的刪除操作和二分搜索樹一樣，也分待刪除結點的右子樹為空、左子樹為空和左右子樹都不為空的情況。

那如何更新高度和平衡因子，不平衡的節點又如何調整為平衡的呢？和插入節點一樣。

插入節點是插入一個節點後從葉子節點計算高度，然後再到父節點根據左右子樹的高度計算平衡因子，接著更新高度，再到上一個父節點，直到整個二叉樹的頂點。

刪除節點可以看作是包含插入節點的，因為刪除一個節點後會從左右子樹中拉上來一個節點，不會再從葉子節點從新計算高度了，而是從左右子樹開始接著更新高度和計算平衡因子。

動畫

Code

—–END—–