二叉查找樹已經能夠很好的應用到應用程序中，但它們在最壞的情況下性能還是很糟糕。考慮到如圖所示這種情況： 查找操作的性能完全等同於線性。而AVL樹的查找操作，能夠保證無論怎麼構造它，運行時間一直對數級別的。一起來學習一下AVL樹吧。
AVL(Adelson-Velsky 和 Landis)樹,是帶有平衡條件的二叉查找樹，這個平衡條件必須要容易保持，並且它保證樹的深度是O(LogN).
一顆AVL樹是其每個節點的左右子樹節點高度最多差1的二叉查找樹。
我門上面說，一顆AVL樹是其每個節點的左右子樹節點高度最多差1的二叉查找樹。 左右子樹的高度最多差1便是AVL樹的平衡條件。
當進行插入操作時，我們需要更新通往根節點的所有節點的平衡信息。而插入操作隱含困難的原因在於，可能會破壞AVL樹的特性（例如，考慮將6插入到圖1的AVL樹中將會破壞節點為8的平衡條件）。如果發生這種情形，那麼就要考慮在插入完成之後重新回復節點的平衡信息。事實上，總可以通過對樹進行簡單的修正得到，我們稱其為旋轉(ratation).
在插入以後，只有那些從插入點到根節點的平衡條件可能變化，因為只有這些節點的字數可能發生變化。當我們沿著這條路路徑行進到根節點，可以發現一個節點它的新平衡破壞了AVL樹的特性。我們需要在這個節點重新平衡這棵樹。
我們把必須重新平衡的節點叫做α。因為平衡條件是高度最多相差1，那麼出現不平衡就是α點的高度相差為2。容易看出這種不平衡可能出現在下面這四種情況下：
1和4，2和3 是關於α點的鏡像對稱。因此理論上講只有兩種情況，當然編程上還是四種情況。
第一種情況是插入發生在外邊的情況(即左-左的情況或者右-右的情況)，該情況是通過對樹的一次單旋轉來完成操作。
第二種情況是插入發生在內部的情形(即左-右的情況或者右-左的情況)，該情況通過稍微復雜點的雙旋轉操作來處理。
下圖顯示了單旋轉如何調整情形1。旋轉前的圖在左邊，旋轉後的圖在右邊。
讓我們來分析具體的做法。節點K2不滿足平衡條件， 因為它的左子樹比右子樹深兩層（圖中的虛線表示樹的各層）.
為使樹恢復平衡，我們把節點X向上移一層，並把Z像下移一層，為此我們重新安排節點以形成一顆等價的樹。如上圖的右邊部分。抽象的形容就是，把把樹想象成一棵柔軟靈活的樹，抓住子節點K1，閉上眼睛使勁的搖動它，這樣由於重力的作用，K1就變成了新的根。二叉樹的性質告訴我們，在原樹中K2>K1，這樣在新樹中，K2變成了K1的右兒子，Y變成了K2的左子樹，而X、Z依然是K1的左子樹和K2的右子樹。
讓我們演示一個更長的例子，假設從初始的空的AVL樹開始依次插入3、2、1,然後再依次插入4-7.
在插入關鍵字1的時候第一個問題就出現了，AVL性質在根處被破壞，我們在根和其左兒子之間施加單旋轉操作來修正問題。下圖是旋轉之前和之後的兩棵樹。
圖中虛線連接的兩個節點，它們是旋轉的主體。下面我們插入關鍵字4這沒有問題，在我們插入關鍵字5的時候，問題又出現了，平衡條件在關鍵字3處被破壞，而通過單旋轉再次將問題修復。
接下來插入6，平衡條件在根節點處被打破，因此我們在根處，在2、4之間施加一次單旋轉操作。
我們插入最後的關鍵字7，它導致另外的旋轉。
單旋轉對情形2、3無效願因在於子樹Y太深。單旋轉沒有降低它的深度。
對於子樹Y我們可以假設他有一個根和兩棵子樹（對應上圖的K2、B、C）。
為了平衡期間，我們不能再把K3當成根了，而如上圖所示K3和K1之間旋轉又解決不了問題，唯一的選擇是把K2當成根，這迫K1成為K2的左子樹，K3成為K1的右子樹，而K2的左子樹成為K1的右子樹，K2的右子樹成為K3的左子樹。容易看出最後得到的樹滿足AVL樹的特征。
我們繼續在前面例子的基礎上以倒序插入10-16，接著插入8，再插入9.插入16很容易這並不破壞樹的平衡,插入15會引起節點7處的高度不平衡，這屬於情形3，需要通過右-左雙旋轉來解決。如圖：
下面我們來插入14，它也需要一個雙旋轉。此時修復樹的旋轉還是右-左雙旋轉
如果現在插入13那麼在根處就會出現不平衡，由於13不在4-7之間，我們知道只要一次單旋轉就行.
插入12也需要一次雙旋轉
插入11、10都需要進行單旋轉，接著我們插入8不需要進行旋轉，這樣就建成了一顆近乎理想的平衡樹
最後我們插入9，在節點10發生不平衡，這裡滿足情形2，對左兒子的右子樹進行一次，需要一次雙旋轉。
現在讓我們對上面的討論做出總結，除幾種情形外，編程的細節是相當簡單的。為將節點X插入AVL樹T中，我們遞歸的將X插入到T的子樹中。如果子樹的高度不變，那麼插入完成；如果出現高度不平衡，那麼找到不平衡點，做適當的單旋轉或者雙旋轉，更新這些高度，從而完成插入。
sealed traitAVLTree[+A] extends Serializable {
defbalance: Int
defdepth: Int
defcontains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean
definsert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B]
defrebalance[B >: A]: AVLTree[B]
}
/**
* 葉子節點
*/
case objectLeafextendsAVLTree[Nothing] {
override valbalance: Int = -1
override valdepth: Int = 0
override defcontains[B >: Nothing](x: B)(implicit ordering: Ordering[B]): Boolean = false
override definsert[B >: Nothing](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
Node(x, Leaf, Leaf)
}
override defrebalance[B >: Nothing]: AVLTree[B] = this
}
case classNode[A](value: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] {
override defbalance: Int = right.depth - left.depth
override defdepth: Int = math.max(left.depth, right.depth)
override defcontains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean = ???
override definsert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
valcmp = ordering.compare(x,value)
if (cmp < 0){
Node(value, left.insert(x),right).rebalance
} else if (cmp > 0){
Node(value, left, right.insert(x)).rebalance
} else {
this
}
}
override defrebalance[B >: A] = {
if (-2 == balance){
if (1 == left.balance){
doubleRightRotation
} else {
rightRotation
}
} else if(2 == balance) {
if (-1 == right.balance){
doubleLeftRotation
}else {
leftRotation
}
} else {
this
}
}
/*
* 5
* \ 6
* 6 ---- 左單旋轉 ---> / \
* \ 5 7
* 7
*
* 在節點5 發生不平衡 5的右節點成為新的根節點
*/
private defleftRotation[B >: A] = {
if (Leaf != right) {
valr = right.asInstanceOf[Node[A]]
Node(r.value, Node(value, left, r.left), r.right)
} else {
sys.error("should not happen.")
}
}
/*
* 7
* / 6
* 6 ---- 右單旋轉 ---> / \
* / 5 7
* 5
*
* 在節點7 發生不平衡 7的左節點成為新的根節點
*/
private defrightRotation[B >: A] = {
if (Leaf != left) {
vall = left.asInstanceOf[Node[A]]
Node(l.value, l.left, Node(value, l.right, right))
} else {
sys.error("should not happen.")
}
}
/*
* 左雙旋轉
*
* 5 5
* \ \ 6
* 7 ----step1 ---> 6 ---step2---> / \
* / \ 5 7
* 6 7
*
* 在節點5處不平衡
* step1 : 節點5的右節點 做一次 右旋轉
* step2 : 左旋轉
*
*/
private defdoubleLeftRotation[B >: A] = {
if (Leaf != right) {
valr = right.asInstanceOf[Node[A]]
valrightRotated = r.rightRotation
Node(rightRotated.value, Node(value, left, rightRotated.left), rightRotated.right)
} else {
sys.error("should not happen.")
}
}
/*
* 右雙旋轉
*
* 7 7
* / / 6
* 5 ----step1 ---> 6 ---step2---> / \
* \ / 5 7
* 6 5
*
* 在節點7處不平衡
* step1 : 節點7的左節點 做一次 左旋轉
* step2 : 右旋轉
*
*/
private defdoubleRightRotation[B >: A] = {
if (Leaf != left) {
vall: Node[A] = left.asInstanceOf[Node[A]]
valleftRotated = l.leftRotation
Node(leftRotated.value, leftRotated.left, Node(value, leftRotated.right, right))
} else sys.error("Should not happen.")
}
《數據結構與算法分析java語言描述》 http://www.linuxidc.com/Linux/2014-04/99735.htm
