Posted on 2007-02-20 12:57
dennis 閱讀(1202)
評論(0) 編輯 收藏 所屬分類:
數據結構與算法
樹的平衡，我們已經知道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