基于平衡因子的AVL树设计实现  

AVL Tree Design and Implementation Based on Balancing Factor

作　　者：杜薇薇[1] 张翼燕[1] 瞿春柳 

机构地区：[1]中国科学技术信息研究所,北京100038 [2]北京掌上通网络技术有限公司,北京100083

出　　处：《计算机技术与发展》2010年第3期24-27,31,共5页Computer Technology and Development

摘　　要：平衡二叉树又称AVL树,得名于它的发明者G.M.Adelson-Velsky和E.M.Landis。作为一种常用的数据结构,许多教科书都详细描述了实现的算法,但是基本都是根据不同树形LL、RR、LR、RL给出相应逻辑,而且都是直接给出结论。而文中则以平衡因子为出发点,揭示了不同树形的一致性算法,第一次以数学公式推演,论证了AVL插入和删除操作在不同树形情况下,哪个节点开始失去平衡,怎么平衡以及哪个节点平衡结束,并给出算法的完整实现代码,使AVL的实现一致、简单、易懂。AVL tree, also known as a balanced binary tree,named after its inventors G. M. Adelson - Velsky and E. M. Landis. As a common data structure, it is described in detail the realization of the algorithm in many textbooks,but based on different tree shape LL,RR, LR, RL are given the corresponding logic, and conclusions are given directly. The balance factor for this article was the starting point, revealing the coherence of different tree algorithm, the first mathematical formula to deduce, demonstrates the AVL insertion and deletion in different tree shape, the node which started to lose balance and how balance and which end of the balance node,and gives a complete code for the realization of the algorithm.

关 键 词：AVL 二叉树 平衡因子 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]