AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何結點的兩個子樹的高度最大差别為1，是以它也被稱為高度平衡樹。增加和删除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹得名于它的發明者
G. M. Adelson-Velsky和E. M. Landis
，他們在1962年的論文
《An algorithm for the organization of information》
中發表了它。
AVL 樹是一種平衡二叉樹，得名于其發明者的名字（ Adelson-Velskii 以及 Landis）
在這個網站可以看到AVL樹的可視化：AVL Tree Visualization
【1】概念介紹
二叉查找樹隻限制了結點值大小：
- 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
那麼在極端情況下，可能出現如下情況，此時查找的時間複雜度從O(logN)退化為O(N)
我們理想的情況是如下所示，隻需要O(logN)就可以查找到結點(N是總結點個數)。
這就是為什麼引入AVL樹。相對于二叉查找樹，其維護了平衡：
每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1
。
總結其特點如下：
- 本身首先是一棵二叉搜尋樹(二叉查找樹)。
- 左右子樹也是AVL樹
- 帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1
- 如果它有n個結點，其高度可保持在logn ，搜尋時間複雜度O(logn)
AVL樹好的解決了二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和删除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多。
樹高的證明
設 fn為高度為 n 的 AVL 樹所包含的最少結點數，則有:
顯然 fn 是一個斐波那契數列。衆所周知，斐波那契數列是以指數的速度增長的，是以 AVL 樹的高度為O(logn)
【2】插入時四種旋轉操作
為了位置平衡，那麼AVL樹在插入和删除時需要重新調整結構，這裡可能會發生旋轉動作。
這裡先引入一個概念：平衡因子。
平衡因子：将二叉樹上結點的左子樹高度減去右子樹高度的值稱為該結點的平衡因子BF(Balance Factor)。
對于平衡二叉樹，BF的取值範圍為
[-1,1]
。如果發現某個結點的BF值不在此範圍，則需要對樹進行調整。
如下圖所示，平衡因子我們這裡取了絕對值。
如果這時插入結點5，那麼就會觸發左旋，根結點平衡因子并未發生變化。
插入一個結點，隻會影響根結點到插入結點的父結點上這條路徑上所有結點的平衡因子。
二叉樹的平衡化有兩大基礎操作： 左旋和右旋。左旋，即是逆時針旋轉；右旋，即是順時針旋轉。這種旋轉在整個平衡化過程中可能進行一次或多次，這兩種操作都是從失去平衡的最小子樹根結點開始的(即離插入結點最近且平衡因子超過1的祖結點)。
下面我們總結四種場景的旋轉。
① 左旋(RR調整)
這個如前面所示，當再次插入結點5時，就會觸發左旋操作。總結就是
插入了較高右子樹的右側結點
。
如果插入一個結點後，插入結點的父結點的平衡因子變成了0，則說明插入結點後樹的高度沒有發生變化，則隻影響了父結點的平衡因子。
如果繼續插入結點6呢？這時會導緻父結點(2)的平衡因子變成2 ，那麼就會觸發父結點的左旋，使結點4變成新的父結點。
如果插入一個結點後，該結點的父結點的平衡因子的絕對值大于等于1，在向上更新過程中如果某一個結點的平衡因子變成了0則停止更新，最壞情況下一直要更新到根結點。
② 右旋(LL調整)
與RR調整相對的是，LL調整也就是在較高左側子樹插入左側結點。
如下所示，插入結點2，那麼會導緻父結點4的平衡因子變為2，這時需要進行右旋。右旋之後根結點5的平衡因子變為了1(無需調整)，調整結束。
如果繼續插入結點1呢？按照平衡二叉樹的規則，這時會插入到結點2的左側。這時會打破根結點的平衡因子，發生根結點的變化。
- 調整原先根結點(5)的左側結點(3)為新的根結點(3)
- 舊的根結點作為新的根結點的右子結點
- 原先左側結點(3)的右側結點(4)作為舊的根結點(5)的左側結點(4)
總結來看，根結點進行變化的前提條件是左子樹(右子樹)沒有辦法經過調整維持原先的樹高度。比如左子樹(右子樹)已經是一棵滿二叉樹(或者是不存在沒有兄弟結點的葉子結點)，那麼此時再在左子樹(右子樹)插入新的結點，隻能通過修改根結點來調整平衡。
③ 先左旋後右旋(LR調整)
也就是插入較高左側子樹的右孩子結點。
如下圖所示，這裡首先對34進行左旋調整4為3的父結點，然後對整體進行右旋，提升4為新的根結點，原先的根結點5降為4的右結點。
④ 先右旋再左旋(RL調整)
也就是插入較高右側子樹的左側結點。
如下圖所示，這裡首先對67進行右旋調整6為7的父結點，然後對整體進行左旋，提升6為新的根結點，原先的根結點5降為6的左結點。
關于插入的總結
AVL樹也是一顆二叉搜尋樹，是以它在插入資料時也需要先找到要插入的位置然後再将結點插入。不同的是，AVL樹插入結點後需要對結點的平衡因子進行調整(自底向上折回調整)，如果插入結點後平衡因子的絕對值大于1,則還需要對該樹進行旋轉，旋轉成為一顆高度平衡的二叉搜尋樹。
【3】删除操作
首先這裡我們回顧一下二叉查找樹的前驅和後繼結點。
① 前驅結點
某結點的前驅結點就是小于該結點中的最大結點。
主要有③個場景：
- ① 如果某個結點存在左子結點，那麼左子結點（子樹）下中的最大 key 值結點即是前驅。
比如結點4的前驅是2
- ② 如果某個結點沒有左子結點，而且如果該結點為其父結點的右子結點，那麼該結點的父結點即為該結點的前驅。
比如結點3的前驅是2
- ③ 如果某個結點沒有左子結點，而且如果該結點為其父結點的左子結點，那麼就往頂端尋找，直到找到第一個結點A并且A是其父結點的右子結點，結點A的父結點就是要找的前驅。
比如結點7的前驅是6
② 後繼結點
某結點的後繼就是大于該結點的所有結點中最小的那個結點。
仍舊以下圖為例：
同樣有3種場景
- ① 如果某個結點存在右子結點，那麼右子結點（子樹）下中的最小 key 值結點即是後繼。
比如結點6的後繼是7
- ② 如果某個結點沒有右子結點，而且如果該結點為其父結點的左子結點，那麼該結點的父結點即為該結點的後繼。
比如結點7的後繼是8
- ③ 如果某個結點沒有右子結點，而且如果該結點為其父結點的右子結點，那麼就往頂端尋找，直到找到第一個結點A且A是其父結點的左子結點，A的父結點就是要找的後繼。
比如3的後繼是4，結點A是2.
③ AVL的結點删除
AVL的結點删除和 BST 類似，将結點與後繼交換後再删除。删除會導緻樹高以及平衡因子變化，這時需要沿着被删除結點到根的路徑來調整這種變化。如何調整變化？其實就是類似插入時的“旋轉操作”。
如下所示，我們删除結點4：
那麼第一步則是将結點4與後繼(結點5)交換，然後删除結點4：
這時可以看到左側結點5的平衡因子是2，打破了AVL樹的性質，典型的LR結構，那麼我們進行先左旋再右旋的調整。