【摘要】 平衡二叉查找树是计算机中有效地组织大规模查找数据的主要手段,因为在树的创建、节点的插入、删除过程中都维持了树的平衡.AVL树是平衡二叉查找树,但是AVL树在创建、插入、删除时维护树的平衡操作需要按照平衡因子的不同情况分别进行处理,程序长,实现过程繁杂.本文利用树的高度提出一种新的AVL平衡树数学描述—高度平衡树(HAVL),并进行了理论分析:HAVL在旋转操作的同时维持节点的高度信息,从而使位于上层的函数不必重新计算统计域,维持树的平衡的各种情况可以统一简洁处理,该数学描述简洁,程序实现直观,程序实现代码量小,维持平衡的C语言代码是一般AVL平衡树的代码长度的大约1/5左右.实验结果表明,HAVL能够保持AVL树的优秀特性,运行时间更短.更多还原

【Abstract】 Balance binary search tree is the main way to organize the data for searching in the large scale data,because the tree is maintain balanced when create tree,insert node into tree and delete node form tree.The classical AVL tree is most widely used balance binary search tree,which maintains balance when inserting node,deleting node and creating tree according to the balance factor;the process is tedious and program is long.We propose a new mathematic model of AVL tree using the height of tree:Height AVL(HAVL) tree and analysis of its performance.The HAVL tree maintains the height of sub tree of AVL during rotation so that the upper maintain process do not compute the information repeatly.The principle of HAVL tree is as same as AVL tree;but it is concise and easy to be implemented;the length of code of HAVL maintaining balance implemented using C language is about 20% of AVL.The experiment shows the HAVL inherits the advantage of AVL and run faster.更多还原