低调整率的广义AVL树及其统一重平衡方法

doi:10.11772/j.issn.1001-9081.2015.03.654

计算机应用 ›› 2015, Vol. 35 ›› Issue (3): 654-658.DOI: 10.11772/j.issn.1001-9081.2015.03.654

低调整率的广义AVL树及其统一重平衡方法

江顺亮, 胡世鸿, 唐祎玲, 葛芸, 叶发茂, 徐少平

南昌大学信息工程学院, 南昌 330031

收稿日期:2014-10-16 修回日期:2014-11-24 出版日期:2015-03-10 发布日期:2015-03-13
通讯作者: 唐祎玲
作者简介:江顺亮(1965-),男,江西丰城人,教授,博士生导师,博士,主要研究方向:计算机模拟与仿真、算法分析与设计、人工智能;胡世鸿(1989-),男,江西高安人,硕士研究生,主要研究方向:人工智能;唐祎玲(1977-),女,浙江奉化人,讲师,博士研究生,主要研究方向:算法分析与设计、人工智能;葛芸(1983-),女,江西高安人,讲师,博士研究生,主要研究方向:数字图像检索;叶发茂(1978-),男,江西金溪人,副教授,博士,主要研究方向:数字图像处理、计算机图形学;徐少平(1976-),男,江西九江人,副教授,博士,主要研究方向:图形图像处理、计算机视觉、虚拟手术仿真
基金资助:
国家自然科学基金资助项目(2012D41261091,2011F61163023)

Generalized AVL tree with low adjusting ratio and its unified rebalancing method

JIANG Shunliang, HU Shihong, TANG Yiling, GE Yun, YE Famao, XU Shaoping

School of Information Engineering, Nanchang University, Nanchang Jiangxi 330031, China

Received:2014-10-16 Revised:2014-11-24 Online:2015-03-10 Published:2015-03-13

摘要/Abstract

摘要：

针对传统AVL(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念。统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋转操作。广义AVL树放松了AVL树的平衡约束,允许左右子树树高相差不超过N(N≥1),当更新操作(插入/删除)执行后,广义AVL树只在平衡约束条件不满足时采用统一重平衡算法进行调整。理论分析与实验结果表明,广义AVL树的调整率随着N的增大而显著降低:N为5时,调整率低于4%;N为13时调整率低于千分之一。广义AVL树的调整率远低于红黑树等经典数据结构,适合并发应用。

关键词: 广义AVL树, 放松平衡约束, 重平衡, 调整率

Abstract:

The traditional AVL (Adelson-Velskii and Landis) tree programming has been faced with the problem of too much code, complex process and high adjusting ratio. To solve these problems, a unified rebalancing method was developed and a generalized AVL (AVL-N) tree was defined. The unified rebalancing method automatically classifies the type of the unbalanced node in AVL tree and uses a new way to adjust the tree shape without using standard rotations. AVL-N tree with relaxed balance allows the height difference between the right sub-tree and left sub-tree doesn't exceed N(N ≥ 1). When insertions and deletions have been performed in AVL-N tree, the height difference between the right sub-tree and left sub-tree of some nodes may be higher than N. At that time the unified rebalancing would be applied to rearrange the unbalanced node's descendants. The simulation results indicate that the adjusting ratio of AVL-N tree reduced significantly with N increasing, it is less than 4% for N=5 and less than 0.1% for N=13. The adjusting ratio of AVL-N tree is far below other classic data structures, such as red-black tree, and allows for a greater degree of concurrency than the original proposal.

Key words: generalized Adelson-Velskii and Landis (AVL) tree, relaxed balance constraint, rebalancing, adjusting ratio

中图分类号:

TP311.12

江顺亮, 胡世鸿, 唐祎玲, 葛芸, 叶发茂, 徐少平. 低调整率的广义AVL树及其统一重平衡方法[J]. 计算机应用, 2015, 35(3): 654-658.

JIANG Shunliang, HU Shihong, TANG Yiling, GE Yun, YE Famao, XU Shaoping. Generalized AVL tree with low adjusting ratio and its unified rebalancing method[J]. Journal of Computer Applications, 2015, 35(3): 654-658.

参考文献

[1] SHAVIT N. Data structures in the multicore age[J]. Communications of the ACM, 2011,54(3):76-84.
[2] JUAN B, YADRAN E. A concurrent red black tree[J]. Journal of Parallel and Distributed Computing, 2013,73(4):434-449.
[3] BRONSON N G, CASPER J, CHAFI H, et al. A practical concurrent binary search tree[C]//Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York:ACM, 2010:257-268.
[4] AFEK Y, KAPLAN H, KORENFELD B, et al. CBTree: a practical concurrent self-adjusting search tree[C]//Proceedings of the 26th International Conference on Distributed Computing. Berlin: Springer, 2012,7611:1-15.
[5] LARSEN K S. AVL trees with relaxed balance[J]. Journal of Computer and System Sciences, 2000,61(3):508-522.
[6] CHEN C, ZHANG K, TAN L, et al. Concurrent non-blocking self-organizing linked list algorithm[J]. Computer Engineering, 2013,39(8):31-37.(陈春光,张坤龙,谭龙飞,等.并发非阻塞自组织链表算法[J].计算机工程,2013,39(8):31-37.)
[7] LIU S, XING Y, LIU H. Lock-free implementation of concurrent binary search tree[J]. Journal of Computer Applications, 2012,32(10):2736-2741.(刘少东,邢永康,刘恒.无锁并发二叉搜索树的实现[J].计算机应用,2012,32(10):2736-2741.)
[8] FAITH E, PANAGIOTA F, ERIC R, et al. Non-blocking binary search trees[C]//Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. New York: ACM, 2010:131-140.
[9] HERLIHY M, LEV Y, LUNCHANGCO V, et al. A provably correct scalable concurrent skip list[C]//Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing. New York: ACM, 2003:92-101.
[10] DENG J. Data structure[M]. 2nd ed. Beijing: Tsinghua University Press, 2012:211-217.(邓俊辉.数据结构[M].2版.北京:清华大学出版社,2012:211-217.)
[11] ZHANG B. Discussion on teaching of balancing the binary tree[J]. Computer Education, 2009,32(4):17-18.(张标汉.平衡二叉树调整教学探讨[J].计算机教育,2009,32(4):17-18.)
[12] ZHU Y, ZHANG H. Selection method for AVL tree rebalancing[J]. Journal of the Graduate School of the Chinese Academy of Sciences, 2006,23(4):527-533.(朱宇,张红彬.平衡二叉树的选择调整算法[J].中国科学院研究生院学报,2006,23(4):527-533.)
[13] WANG F, ZHOU K. A non-recursive algorithm of constructing strict balance two binary search tree[J]. Journal of Wuhan Polytechnic University, 2013,32(4):32-34.(王防修,周康.一种构建严格平衡二叉搜索树的非递归算法[J].武汉工业学院学报,2013,32(4):32-34.)

低调整率的广义AVL树及其统一重平衡方法

Generalized AVL tree with low adjusting ratio and its unified rebalancing method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	赵丹枫, 林俊辰, 宋巍, 王建, 黄冬梅. 低冗余计算的可达性查询保持图压缩策略[J]. 计算机应用, 2020, 40(2): 510-517.
[2]	白宇郭显娥. 求解云计算压力测试中并行任务密度的高速算法[J]. 计算机应用, 2014, 34(7): 1839-1842.
[3]	郭栋王伟曾国荪. 基于一致性树分布的数据分布式存储方法[J]. 计算机应用, 2013, 33(12): 3432-3436.
[4]	白宇郭显娥. 中缀算术表达式的轻量化求值算法[J]. 计算机应用, 2013, 33(11): 3163-3166.
[5]	白宇郭显娥. 深度优先稳定原地归并排序的高效算法[J]. 计算机应用, 2013, 33(04): 1039-1042.
[6]	李文闯章永平潘瑜春. 移动地理信息系统中的多源异构数据融合模型[J]. 计算机应用, 2012, 32(09): 2672-2674.
[7]	凌绪雄王社国李洋苗再良. 无项头表的FP-Growth算法[J]. 计算机应用, 2011, 31(05): 1391-1394.
[8]	张涛，于雪芹. 基于XDR纲要的空间元数据存储策略[J]. 计算机应用, 2005, 25(07): 1590-1591.
[9]	周勇，何建农，涂平. 自动调配的层次网格空间索引技术[J]. 计算机应用, 2005, 25(06): 1401-1404.
[10]	魏红宁. 基于SPRINT方法的并行决策树分类研究[J]. 计算机应用, 2005, 25(01): 39-41.