前面所講的二叉搜尋樹有個比較嚴重緻命的問題就是極端情況下當資料以排序好的順序建立搜尋樹此時二叉搜尋樹将退化為連結清單結構是以性能也大幅度下降，是以為了解決此問題我們下面要介紹的與二叉搜尋樹非常類似的結構就誕生了；
AVL（Adelson-Velskii and Landis）樹，名字取自其發明者 G.M. Adelson-Velsky 和 E.M. Landis的首字母，AVL樹是一棵特殊的二叉搜尋樹它與普通二叉搜尋樹最主要的差別就是其能夠使二叉搜尋樹維持其左右節點的平衡；
AVL樹：其任意一個節點左子樹與右子樹高度差不超過1，由于此特征是以需要在AVL增删節點時維護其左右節點使該樹滿足該特性（左右節點平衡）；
此AVL樹中節點2節點高度都為2，節點1與3節點高度都為1；節點高度為左右子樹中最大的節點高度+1；
AVL樹實作關鍵
1、标注其節點高度
2、計算節點平衡因子
3、維護其節點滿足左右節點高度不超過1
AVL樹的實作
1、AVL樹定義
根據AVL樹的特性先定義該資料類型的結構；
type AVL struct {
root *AVLNode
size int
compare Comparable
}
type AVLNode struct {
e interface{}
left *AVLNode
right *AVLNode
height int
}
AVL：為定義的AVL樹自定義對象
AVLNode：為樹中每個節點的節點自定義對象
compare：為定義的用于樹中節點元素進行資料對比的對象
size：AVL樹的元素個數
root：樹的根節點
e：節點元素值
left：左子樹
right：右子樹
height：節點高度
AVL樹與二叉搜尋樹一樣所有很多操作都可用遞歸來實作，比如元素的添加、删除、查找等；
可以說AVL樹為二叉搜尋樹的更新版本是以并不會像出現二叉搜尋樹一樣出現退化為O(n)時間複雜度的情況，與二叉搜尋樹一樣通過中序周遊可得到排序好的資料，二叉搜尋樹的搜尋、插入、删除時間複雜度為O(log(n))，n為樹的深度，這裡隻是簡單的介紹了AVL樹，後面會有AVL樹實作的相關介紹；
文章首發位址：Solinx
http://www.solinx.co/archives/1323