平衡二叉树调整的传统算法是旋转,针对不同的失衡结构分别采用左转、右转、先左转后右转、先右转后左转四种转法。其实,利用平衡二叉树最直观的特性“中为根、小为左、大为右”做调整则更简单,并可直接确定平衡因子。为此本文提出选择调整算法,即选择大中小结点直接对应到上述平衡结构,对插入失衡和删除失衡有对称的分析和描述。算法是非递归的。实验表明当结点数量超过10万时,选择算法的构建时间比旋转算法降低20%以上,删除时间下降13%以上。
The traditional algorithm for AVL tree rebalancing is the rotation method, which uses methods of left-rotation, right-rotation, left first rotation then right and right first rotation then left to deal with the different unbalance structures respectively. In fact, it is more simple to solve imbalance using the obvious characteristic of AVL tree that "middle for the root, smaller for the left and bigger for the right", and the balance-factors can be found directly. Based on this idea we propose the selection method, which chooses the smaller, middle and bigger nodes from the unbalanced structure and reform them to that balanced state. We have a symmetry analyzation and description on both inserting and deleting. The whole algorithm is non-recursion. Our experimental result verifies that the construction time of the selection method decreases over 20% than that of the rotation method and the destruction time decreases over 13% when the number of nodes exceeds 100,000.