关键词: 平衡二叉树, 选择算法, 访问路径, 方向指示, 非递归

Abstract: 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.

Key words: AVL tree, the selection method, the aceess path, direction, non-recursion