為什么需要AVL樹？
在二叉搜索樹專題講過二叉搜索樹一定程度上可以提高搜索效率，但是當(dāng)原序列有序時(shí)，依據(jù)此序列構(gòu)造的二叉搜索樹為右斜樹或者左斜樹，同時(shí)二叉樹退化成單鏈表，搜索效率降低為 O(n)。
例如假設(shè)有一組數(shù)[1, 2, 3, 4, 5, 6]如果我們以順序添加到二叉搜索樹中, 那么這顆二叉搜索樹就會(huì)退化成一個(gè)鏈表。
二叉搜索樹的查找效率取決于樹的高度，因此保持樹的高度最小，即可保證樹的查找效率。因此就有了AVL樹。
AVL樹也算是一種特殊的兒二叉搜索樹，這里不講AVL樹的搜索與查找，因?yàn)槎急容^簡單，主要講的是AVL樹的插入與刪除，因?yàn)樾薷目赡軙?huì)導(dǎo)致重新平衡。
定義
它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1。AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點(diǎn)對應(yīng)的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。
4的左子樹高度是0，右子樹高度是0，高度差0
5的左子樹高度1，右子樹高度0，高度差1
8的左子樹高度2，右子樹高度1，高度差1
12的左子樹高度3，右子樹高度2，高度差1
18的左子樹高度1，右子樹高度0，高度差1
平衡因子
某節(jié)點(diǎn)的左子樹與右子樹的高度(深度)差即為該節(jié)點(diǎn)的平衡因子（BF,Balance Factor），平衡二叉樹中不存在平衡因子大于 1 的節(jié)點(diǎn)。在一棵平衡二叉樹中，節(jié)點(diǎn)的平衡因子只能取 0 、1 或者 -1 ，分別對應(yīng)著左右子樹等高，左子樹比較高，右子樹比較高。當(dāng)平衡因子的絕對值大于 1 時(shí)，就會(huì)觸發(fā)樹的重新平衡。
插入與刪除
刪除操作與二叉搜索樹一樣，只不過刪除一個(gè)節(jié)點(diǎn)需要檢查樹是否平衡，如果平衡因子絕對值大于 1 時(shí)，就需要重新平衡，若平衡二叉樹種某個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度相差大于1，該樹就是失衡了，該結(jié)點(diǎn)稱為失衡點(diǎn)，先找到失衡點(diǎn)，接下來的操作就和插入時(shí)需要平衡一樣了，所以這里只需要講失衡點(diǎn)是怎么平衡的就可以。
會(huì)有四種情況導(dǎo)致失衡：
-
LL型
當(dāng)新插入的結(jié)點(diǎn)為左子樹的左子結(jié)點(diǎn)時(shí)，我們需要進(jìn)行右旋操作來保證此部分子樹繼續(xù)處于平衡狀態(tài)。
下面看一個(gè)比較復(fù)雜的情況:插入一個(gè)節(jié)點(diǎn)20
-
RR型
當(dāng)新插入的結(jié)點(diǎn)為右子樹的右子結(jié)點(diǎn)時(shí)，我們需要進(jìn)行左旋操作來保證此部分子樹繼續(xù)處于平衡狀態(tài)。
-
LR型
對于LR型的情況，要使用先對失衡點(diǎn)的左孩子進(jìn)行左旋，然后再對失衡點(diǎn)進(jìn)行右旋來解決。
復(fù)雜情況：
-
RL型
對于RL型的情況，要使用先對失衡點(diǎn)的右孩子進(jìn)行右旋，然后再對失衡點(diǎn)進(jìn)行左旋來解決。
復(fù)雜情況：
總結(jié)：
AVL是歷史上出現(xiàn)的第一種平衡二叉樹，它現(xiàn)在的很多應(yīng)用都已經(jīng)被紅黑樹代替。主要原因是它的平衡限制比較紅黑樹嚴(yán)格，在插入或者刪除節(jié)點(diǎn)的時(shí)候很容易違反平衡限制條件，造成頻繁的樹結(jié)構(gòu)調(diào)整和重新平衡。AVL限制對每個(gè)節(jié)點(diǎn)左子樹和右子樹的高度相差不超過一，所以它是高度平衡的二叉樹，因而在進(jìn)行查找的時(shí)候效率很高。而紅黑樹的平衡限制比AVL要弱，甚至左右子樹的高度差等于2倍，所以紅黑樹的查找效率比AVL要低。但是，紅黑樹不需要頻繁重平衡(得益于其寬松的限制條件)，所以在插入刪除較頻繁的環(huán)境中紅黑樹勝出。
