中国科学院大学学报 ›› 2006, Vol. 23 ›› Issue (4): 527-533.DOI: 10.7523/j.issn.2095-6134.2006.4.015
• 论文 • 上一篇 下一篇
朱 宇; 张红彬
1清华大学100084;
2中国科学院研究生院100039
收稿日期:
修回日期:
发布日期:
ZHU Yu, ZHANG Hong-Bin
1 Tsinghua University
2 Graduate School of Chinese Academy of Sciences
Received:
Revised:
Published:
摘要: 平衡二叉树调整的传统算法是旋转,针对不同的失衡结构分别采用左转、右转、先左转后右转、先右转后左转四种转法。其实,利用平衡二叉树最直观的特性“中为根、小为左、大为右”做调整则更简单,并可直接确定平衡因子。为此本文提出选择调整算法,即选择大中小结点直接对应到上述平衡结构,对插入失衡和删除失衡有对称的分析和描述。算法是非递归的。实验表明当结点数量超过10万时,选择算法的构建时间比旋转算法降低20%以上,删除时间下降13%以上。
关键词: 平衡二叉树, 选择算法, 访问路径, 方向指示, 非递归
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
中图分类号:
TP301.6
朱 宇; 张红彬. 平衡二叉树的选择调整算法[J]. 中国科学院大学学报, 2006, 23(4): 527-533.
ZHU Yu, ZHANG Hong-Bin. Selection Method for AVL Tree Rebalancing[J]. , 2006, 23(4): 527-533.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://journal.ucas.ac.cn/CN/10.7523/j.issn.2095-6134.2006.4.015
http://journal.ucas.ac.cn/CN/Y2006/V23/I4/527