資料結構之AVL樹

樹的平衡，我們已經知道dwl算法，不過dwl算法需要從整體上平衡樹，但是樹的平衡也可以局部的進行，由adel'son-vel'skii-landis提出了一種經典方法，稱為avl樹。

1。概念：avl樹，或者說可适應樹，是指樹中每個節點的的平衡因子的絕對值不大于1，即隻能為-1，0，1

平衡因子：節點的右子樹的高度減去左子樹的高度

2。avl樹的插入：從新插入節點到根的路徑上，修改遇到的節點的平衡因子即可，對其他部分沒影響

1）向右子女的右子樹插入一個節點，單旋轉就可以

2）向右子女的左子樹插入一個節點，雙旋轉，先圍繞父節點，再圍繞祖父節點

3。avl樹的删除：從删除節點到根的路徑上，任何不平衡因子的節點都需要修改，與插入不同，需要o(lgn)次旋轉。

4。一個java實作：

http://www.koders.com/java/fid3b5247d34968077a6efd4216589026d343559ff9.aspx?s=avl%2btree

文章轉自莊周夢蝶  ，原文釋出時間5.17