知識星球（點選上方公眾號，可快速關註）
來源：帥地（本文來自作者的投稿，其簡介見末尾）
1、若它的左子樹不為空，則左子樹上所有的節點值都小於它的根節點值。
2、若它的右子樹不為空，則右子樹上所有的節點值均大於它的根節點值。
3、它的左右子樹也分別可以充當為二叉查詢樹。
例如：
例如，我現在想要查詢數值為14的節點。由於二叉查詢樹的特性，我們可以很快著找到它，其過程如下：
1、和根節點9比較
2、由於 14 > 9，所以14只可能存在於9的右子樹中，因此檢視右孩子13
3、由於 14 > 13，所以繼續檢視13的右孩子15
4、由於 14 < 15，所以14只可能存在於15的左孩子中，因此查詢15的左孩子14
5、這時候發現14正是自己查詢的值，於是查詢結束。
這種查詢二叉樹的查詢正是二分查詢的思想，可以很快著找到目的節點，查詢所需的最大次數等同於二叉查詢樹的高度。
在插入的時候也是一樣，透過一層一層的比較，最後找到適合自己的位置。
初始的二叉查詢樹只有三個節點：
然後我們按照順序陸續插入節點 4，3，2，1，0。插入之後的結構如下：
這是一種比查詢二叉樹還特別的樹哦，這種樹就可以幫助我們解決二叉查詢樹剛才的那種所有節點都傾向一邊的缺點的。具有如下特性：
-
具有二叉查詢樹的全部特性。
-
每個節點的左子樹和右子樹的高度差至多等於1。
例如：圖一就是一顆AVL樹了，而圖二則不是(節點右邊標的是這個節點的高度)。
對於圖二，因為節點9的左孩子高度為2，而右孩子高度為0。他們之間的差值超過1了。
這種樹就可以保證不會出現大量節點偏向於一邊的情況了。
聽起來這種樹還不錯，可以對於圖1，如果我們要插入一個節點3，按照查詢二叉樹的特性，我們只能把3作為節點4的左子樹插進去，可是插進去之後，又會破壞了AVL樹的特性，那我們那該怎麼弄？
右旋
我們在進行節點插入的時候，可能會出現節點都傾向於左邊的情況，例如：
我們把這種傾向於左邊的情況稱之為 左-左型。這個時候，我們就可以對節點9進行右旋操作，使它恢復平衡。
即：順時針旋轉兩個節點，使得父節點被自己的左孩子取代，而自己成為自己的右孩子
再舉個例子：
節點4和9高度相差大於1。由於是左孩子的高度較高，此時是左-左型，進行右旋。
這裡要註意，節點4的右孩子成為了節點6的左孩子了
我找了個動圖，儘量這個動圖和上面例子的節點不一樣。
左旋
左旋和右旋一樣，就是用來解決當大部分節點都偏向右邊的時候，透過左旋來還原。例如：
我們把這種傾向於右邊的情況稱之為 右-右型。
我也找了一張動圖。
例子講解
初始狀態如下：
然後我們主鍵插入如下數值：1,4,5,6,7,10,9,8
插入 1
左-左型，需要右旋調整。
插入4
繼續插入 5
右-右型，需要左旋轉調整。
繼續插入6
右-右型，需要進行左旋
繼續插入7
右-右型，需要進行左旋
繼續插入10
繼續插入9
出現了這種情況怎麼辦呢?對於這種 右-左型 的情況，單單一次左旋或右旋是不行的，下麵我們先說說如何處理這種情況。
這種我們就把它稱之為 右-左 型吧。處理的方法是先對節點10進行右旋把它變成右-右型。
然後在進行左旋。
所以對於這種 右-左型的，我們需要進行一次右旋再左旋。
同理，也存在 左-右型的，例如：
對於左-右型的情況和剛才的 右-左型相反，我們需要對它進行一次左旋，再右旋。
回到剛才那道題
對它進行右旋再左旋。
到此，我們的插入就結束了。
總結一下
在插入的過程中，會出現一下四種情況破壞AVL樹的特性，我們可以採取如下相應的旋轉。
1、左-左型：做右旋。
2、右-右型：做左旋轉。
3、左-右型：先做左旋，後做右旋。
4、右-左型：先做右旋，再做左旋。
不知道大家發現規律沒，這個規則還是挺好記。
程式碼實現
//定義節點
class AvlNode {
int data;
AvlNode lchild;//左孩子
AvlNode rchild;//右孩子
int height;//記錄節點的高度
}
//在這裡定義各種操作
public class AVLTree{
//計算節點的高度
static int height(AvlNode T) {
if (T == null) {
return -1;
}else{
return T.height;
}
}
//左左型，右旋操作
static AvlNode R_Rotate(AvlNode K2) {
AvlNode K1;
//進行旋轉
K1 = K2.lchild;
K2.lchild = K1.rchild;
K1.rchild = K2;
//重新計算節點的高度
K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;
return K1;
}
//進行左旋
static AvlNode L_Rotate(AvlNode K2) {
AvlNode K1;
K1 = K2.rchild;
K2.rchild = K1.lchild;
K1.lchild = K2;
//重新計算高度
K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;
return K1;
}
//左-右型，進行右旋，再左旋
static AvlNode R_L_Rotate(AvlNode K3) {
//先對其孩子進行左旋
K3.lchild = R_Rotate(K3.lchild);
//再進行右旋
return L_Rotate(K3);
}
//右-左型，先進行左旋，再右旋
static AvlNode L_R_Rotate(AvlNode K3) {
//先對孩子進行左旋
K3.rchild = L_Rotate(K3.rchild);
//在右旋
return R_Rotate(K3);
}
//插入數值操作
static AvlNode insert(int data, AvlNode T) {
if (T == null) {
T = new AvlNode();
T.data = data;
T.lchild = T.rchild = null;
} else if(data < T.data) {
//向左孩子遞迴插入
T.lchild = insert(data, T.lchild);
//進行調整操作
//如果左孩子的高度比右孩子大2
if (height(T.lchild) - height(T.rchild) == 2) {
//左-左型
if (data < T.lchild.data) {
T = R_Rotate(T);
} else {
//左-右型
T = R_L_Rotate(T);
}
}
} else if (data > T.data) {
T.rchild = insert(data, T.rchild);
//進行調整
//右孩子比左孩子高度大2
if(height(T.rchild) - height(T.lchild) == 2)
//右-右型
if (data > T.rchild.data) {
T = L_Rotate(T);
} else {
T = L_R_Rotate(T);
}
}
//否則，這個節點已經在書上存在了，我們什麼也不做
//重新計算T的高度
T.height = Math.max(height(T.lchild), height(T.rchild)) + 1;
return T;
}
}提示：可以左右拉動
希望透過這種漫畫的形式，能夠讓你們更加容易讀懂一些演演算法或資料結構。
【關於作者】
帥地：一個熱愛程式設計的在校生，我的世界不只有coding，還有writing
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：
http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
