AVL樹統(tǒng)一重平衡方法

　　針對傳統(tǒng)AVL（ Adelson-Velskii and Landis）樹重平衡算法代碼量大、流程復雜、調(diào)整率過高的問題，提出一種統(tǒng)一重平衡算法，并提出廣義AVL樹的概念。統(tǒng)一重平衡算法能對AVL樹的失衡節(jié)點進行自動分類、調(diào)整，取消了傳統(tǒng)重平衡方法中的四種旋轉(zhuǎn)操作。廣義AVL樹放松了AVL樹的平衡約束，允許左右子樹樹高相差不超過Ⅳ（Ⅳ≥1），當更新操作（插入／刪除）執(zhí)行后，廣義AVL樹只在平衡約束條件不滿足時采用統(tǒng)一重平衡算法進行調(diào)整。理論分析與實驗結(jié)果表明，廣義AVL樹的調(diào)整率隨著Ⅳ的增大而顯著降低：Ⅳ為5時，調(diào)整率低于4%；Ⅳ為13時調(diào)整率低于千分之一。廣義AVL樹的調(diào)整率遠低于紅黑樹等經(jīng)典數(shù)據(jù)結(jié)構(gòu)，適合并發(fā)應用。