一种快速构建平衡二叉搜索树的算法被引量：2

下载PDF

导出

摘要根据一个数据序列构建AVL树,传统算法是从空树开始依次将结点进行插入,每插入一个结点后都要判断插入结点后的新树是否还是AVL树,如是则继续插入下一个结点,如不是则先要将之调整为AVL树再插入下一个结点,直至结束。这种方法的不足是很多时候需要对生成的中间树进行调整,耗时较多。针对这种情况,如果只是为了得到最终的AVL树,而不要求考虑原来数据插入的顺序,可以先将数据进行排序,然后采用递归思想进行构建:将中点数据作为AVL树的根,小于中点数据的数据用来构成AVL树的左子树,大于中点数据的数据用来构成AVL树的右子树。

作者胡云黄震宇

机构地区无锡市广播电视大学

出处《大庆师范学院学报》 2008年第2期20-22,共3页 Journal of Daqing Normal University

关键词 AVL树平衡二叉树二叉搜索树

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

引文网络
相关文献

参考文献4

1殷人昆,徐孝凯编著..数据结构习题解析用面向对象方法与C++语言描述[M].北京:清华大学出版社,2002:249.
2朱宇,张红彬.平衡二叉树的选择调整算法[J].中国科学院研究生院学报,2006,23(4):527-533. 被引量：11
3赵华增,肖朋生,房明辉,蒋爱荣,李艳.基于重构的AVL树的新算法及实现[J].沈阳工业学院学报,2004,23(2):35-37. 被引量：2
4孙宁平,中村良三,孙文玲.AVL平衡树插入算法的平均特性[J].中央民族大学学报（自然科学版）,2000,9(1):30-38. 被引量：3

二级参考文献8

1Knuth Donald E. The Art of Computer Programming, Volume 3/Sorting and Searching[ M]. Addison - Wesley Publishing Company,Inc. Philippines, 1973. 被引量：1
2WilliamFord WilliamTopp 刘卫东译.数据结构(用C++描述)[M].北京:清华大学出版社,1998.. 被引量：1
3EllisHorowitz SartajSahni DineshMehta 周维真译.用C++描述数据结构[M].北京:国防工业出版社,1997.. 被引量：2
4CliffordA Shaffer 张铭译.数据结构与算法分析[M].北京:电子工业出版社,1998.. 被引量：5
5Yan WM,Wu WM.Data Structures (C Language).Beijing:Tsinghua University Press,1997.233 ～ 238(in Chinese) 被引量：1
6Lu KC.Introduction to Computer Algorithm-Design and Analysis.Beijing:Tsinghua University Press,1996.161 ～ 164(in Chinese) 被引量：1
7William Ford,William Topt.Data Structures with C ++.Beijing:Tsinghua University Press,1997.721 ～728 被引量：1
8Clifford A,Shaffer.A Practical Introduction to Data Structures and Algorithm Analysis (C + + Edition) (2nd ed.).Beijing:Publishing House of Electronics Industry,2002.280 被引量：1

共引文献11

1韩璐,林华坚.基于选择调整算法的AVL树快速增删算法的研究与实现[J].广东通信技术,2007,27(12):72-75.
2许松.非结构化P2P网络拓扑结构的改进机制[J].计算机工程与应用,2009,45(10):110-112. 被引量：3
3王鑫宁,魏振钢,李崇.基于二叉排序树的缓冲机制在污染源监控系统中的研究[J].工业控制计算机,2011,24(11):70-71.
4朱洪浩.数据结构中平衡二叉树的教学探讨与研究[J].赤峰学院学报（自然科学版）,2012,28(5):19-21. 被引量：5
5王防修,周康.一种构建严格平衡二叉搜索树的非递归算法[J].武汉工业学院学报,2013,32(4):32-34. 被引量：4
6陈云.基于松弛迭代的快速路网平衡网格化算法[J].测绘与空间地理信息,2014,37(5):103-106. 被引量：2
7江顺亮,胡世鸿,唐祎玲,葛芸,叶发茂,徐少平.低调整率的广义AVL树及其统一重平衡方法[J].计算机应用,2015,35(3):654-658. 被引量：2
8杨金龙,李昕昕,龚勋.基于拆分旋转法的平衡二叉树的构建[J].电脑知识与技术,2018,14(10Z):3-5. 被引量：1
9徐懿彬,徐学荣.一种新型有序数据结构:容量平衡三叉查找树[J].计算机工程与应用,2017,53(9):63-71. 被引量：3
10刘慧,张兆维.平衡二叉树的五步失衡调整方法探索[J].计算机时代,2020(11):78-81. 被引量：3

同被引文献8

1岑岗,周炳生.严格平衡二叉排序树及其构造[J].计算机工程与应用,2005,41(13):57-60. 被引量：7
2徐孝凯,贺桂英.数据结构(c语言描述)[M].北京:清华大学出版社,2008. 被引量：2
3谭浩强.实用数据结构[M].北京:清华大学出版社,2008. 被引量：1
4孙晓辉,王劲林,陈晓.实时系统中的动态内存分配算法[J].计算机工程,2008,34(8):80-81. 被引量：7
5王刚.基于二分查找法实现对馆藏书目的查重处理[J].黑龙江教育学院学报,2008,27(4):159-160. 被引量：3
6王防修,周康.一种构建严格平衡二叉搜索树的非递归算法[J].武汉工业学院学报,2013,32(4):32-34. 被引量：4
7郭猛,胡秀香,邵国金.混合语义相似度计算优化模糊查询的智能信息检索算法[J].科学技术与工程,2014,22(23):97-102. 被引量：4
8熊平,朱天清,金大卫.一种面向决策树构建的差分隐私保护算法[J].计算机应用研究,2014,31(10):3108-3112. 被引量：12

引证文献2

1王防修,刘春红.基于双链表的严格平衡二叉树建立[J].武汉轻工大学学报,2015,34(3):75-79. 被引量：1
2魏志威,王防修.一种无需借助栈的严格平衡二叉树建立[J].武汉轻工大学学报,2015,34(4):47-50.

二级引证文献1

1俞祥基,蒲俊良,周川,张隆春,唐林,陈巧灵.利用区间管理算法实现的TCP流重组技术[J].通信技术,2022,55(12):1650-1658.

1胡云.快速构建AVL树[J].安阳师范学院学报,2007(5):61-63. 被引量：2
2刘岩.基于动态规划的最优二叉搜索树算法的改进[J].电脑知识与技术,2008,0(12Z):2176-2177. 被引量：1
3赵华增,肖朋生,房明辉,蒋爱荣,李艳.基于重构的AVL树的新算法及实现[J].沈阳工业学院学报,2004,23(2):35-37. 被引量：2
4郭芳.三种三叉树存储结构的比较[J].安康师专学报,1999,11(1):47-51. 被引量：3
5Clark,D,李淑兰.八字树[J].微型计算机,1995,15(2):79-81.
6周艳聪,董永峰,崔晓欣,杨阔.基于信息预处理的分组动态二进制防碰撞算法[J].计算机工程与科学,2014,36(10):2041-2046.
7陶荣,赵文静.最优二叉搜索树的动态规划算法研究[J].电脑知识与技术,2008,0(12Z):2188-2189.
8许宪东,关毅,洪炳镕,朴松昊,钟秋波,蔡则苏.基于改进NSGA-Ⅱ的仿人机器人上楼梯运动规划方法[J].高技术通讯,2014,24(9):982-990.
9韦春龙.卫星接收故障诊断专家系统的研究[J].信息网络安全,2012(2):81-83. 被引量：1
10Alex Fedorov,韩磊.在Delphi中使用SQL Server的XML特性(五)——插入、更新、删除数据[J].Internet信息世界,2002(8):95-97.

大庆师范学院学报

2008年第2期

浏览历史

内容加载中请稍等...

一种快速构建平衡二叉搜索树的算法被引量：2

参考文献4

二级参考文献8

共引文献11

同被引文献8

引证文献2

二级引证文献1

相关作者

相关机构

相关主题

浏览历史

一种快速构建平衡二叉搜索树的算法 被引量：2

参考文献4

二级参考文献8

共引文献11

同被引文献8

引证文献2

二级引证文献1

相关作者

相关机构

相关主题

浏览历史

一种快速构建平衡二叉搜索树的算法被引量：2