原文連結
前言
首先介紹下 二分搜尋樹 ，它又名有序二叉查找樹，它的特點是左子樹的節點值要小于父節點值，右子樹的節點值要大于父節點值。基于這樣的特點，我們在查找某個節點的時候，可以采取二分查找的思想快速找到這個節點，時間複雜度期望值是為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由開始的不平衡已變成平衡。
删除節點
AVL樹的删除操作和二分搜尋樹一樣，也分待删除結點的右子樹為空、左子樹為空和左右子樹都不為空的情況。
那如何更新高度和平衡因子，不平衡的節點又如何調整為平衡的呢？和插入節點一樣。
插入節點是插入一個節點後從葉子節點計算高度，然後再到父節點根據左右子樹的高度計算平衡因子，接着更新高度，再到上一個父節點，直到整個二叉樹的頂點。
删除節點可以看作是包含插入節點的，因為删除一個節點後會從左右子樹中拉上來一個節點，不會再從葉子節點從新計算高度了，而是從左右子樹開始接着更新高度和計算平衡因子。
來源 | 算法無遺策
作者 | 我脫下短袖