平衡二叉树的选择调整算法

• 作者: 张红彬 朱宇
• 来源期刊: 中国科学院研究生院学报
• 学科: 工学
• 关键词: 平衡二叉树 选择算法 访问路径 方向指示 非递归
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 论文
• 页码范围: 527-533
• 页数: 7页
• 分类号: TP301.6
• 字数: 5364字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-1175.2006.04.015

摘要

平衡二叉树调整的传统算法是旋转,针对不同的失衡结构分别采用左转、右转、先左转后右转、先右转后左转4种转法.其实,利用平衡二叉树最直观的特性"中为根、小为左、大为右"做调整则更简单,并可直接确定平衡因子.为此本文提出选择调整算法,即选择大中小结点直接对应到上述平衡结构,对插入失衡和删除失衡有对称的分析和描述,算法是非递归的.实1验表明,当结点数量超过10万时,选择算法的构建时间比旋转算法降低20%以上,删除时间下降13%以上.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱宇		2	24	2.0	2.0
2	张红彬		1	14	1.0	1.0