低调整率的广义AVL树及其统一重平衡方法

Generalized AVL tree with low adjusting ratio and its unified rebalancing method

针对传统AVL(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念。统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋转操作。广义AVL树放松了AVL树的平衡约束,允许左右子树树高相差不超过N(N≥1),当更新操作(插入/删除)执行后,广义AVL树只在平衡约束条件不满足时采用统一重平衡算法进行调整。理论分析与实验结果表明,广义AVL树的调整率随着N的增大而显著降低:N为5时,调整率低于4%;N为13时调整率低于千分之一。广义AVL树的调整率远低于红黑树等经典数据结构,适合并发应用。

The traditional AVL （ Adelson-Velskii and Landis） tree programming has been faced with the problem of too much code, complex process and high adjusting ratio. To solve these problems, a unified reb＇alancing method was developed and a generalized AVL （AVL-N） tree was defined. The unified rebalancing method automatically classifies the type of the unbalanced node in AVL tree and uses a new way to adjust the tree shape without using standard rotations. AVL-N tree with relaxed balance allows the height difference between the right sub-tree and left sub-tree doesn＇t exceed N（ N ≥ 1 ）. When insertions and deletions have been performed in AVL-N tree, the height difference between the right sub-tree and left sub-tree of some nodes may be higher than N. At that time the unified rebalancing would be applied to rearrange the unbalanced node＇s descendants. The simulation results indicate that the adjusting ratio of AVL-N tree reduced significantly with N increasing, it is less than 4% for N =5 and less than 0.1% for N = 13. The adjusting ratio of AVL-N tree is far below other classic data structures, such as red-black tree, and allows for a greater degree of concurrency than the original proposal.