AVL樹統一重平衡方法
大小：0.74 MB 人氣：0 2018-01-14 需要積分：1
標簽：AVL(10009)
針對傳統AVL（ Adelson-Velskii and Landis）樹重平衡算法代碼量大、流程復雜、調整率過高的問題，提出一種統一重平衡算法，并提出廣義AVL樹的概念。統一重平衡算法能對AVL樹的失衡節點進行自動分類、調整，取消了傳統重平衡方法中的四種旋轉操作。廣義AVL樹放松了AVL樹的平衡約束，允許左右子樹樹高相差不超過Ⅳ（Ⅳ≥1），當更新操作（插入／刪除）執行后，廣義AVL樹只在平衡約束條件不滿足時采用統一重平衡算法進行調整。理論分析與實驗結果表明，廣義AVL樹的調整率隨著Ⅳ的增大而顯著降低：Ⅳ為5時，調整率低于4%；Ⅳ為13時調整率低于千分之一。廣義AVL樹的調整率遠低于紅黑樹等經典數據結構，適合并發應用。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%
