-
题名快速构建AVL树
被引量：2
- 1
-
-
作者
胡云
-
机构
无锡市广播电视大学
-
出处
《安阳师范学院学报》
2007年第5期61-63,共3页
-
文摘
传统AVL树的构建是从空树开始依次将结点插入进来,每插入一个结点就要判断新得到的新树是否满足AVL树的性质,如满足则继续下一个结点的插入,如不满足则先要将之调整为AVL树再插入下一结点,直至结束。这种方法需要对生成的中间树频繁地进行调整,耗时较多。本文提出了一种新的简单的方法,主旨是采用递归思想实现:先将数据进行排序,然后将中点数据作为AVL树的根,小于中点数据的数据构成AVL树的左子树,大于中点数据的数据构成AVL树的右子树。
-
关键词
AVL树
平衡二叉树
二叉搜索树
-
Keywords
AVL tree
balanced binary tree
Two forks the search tree
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名AVL树研究与实现
被引量：1
- 2
-
-
作者
解晨
-
机构
中山大学
-
出处
《电脑知识与技术》
2013年第3期1532-1536,共5页
-
文摘
计算机最广为人知的优点之一是其能储存大量的数据,如今随着时代的发展,储存容量更是犹如日进千里一般极速扩展,大容量的硬盘、U盘早已随处可见。然而,要在巨大的数据中搜索出需要的内容却不是一件容易的事,由此,为了能减少在搜索储存数据上的开销,各种适应于不同访问搜索背景的数据结构应运而生。树,便是计算机学科中最基本的数据结构之一,提供了快速的储存和访问性能。该文探究了带有平衡条件的二叉查找树——AVL树的原理,并对其使用C语言进行了实现。
-
关键词
数据结构
平衡二叉查找树
AVL树
-
Keywords
data structure
balanced binary search tree
AVL tree
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论][自动化与计算机技术—计算机科学与技术]
-
-
题名5G路测仪信令合成算法的研究与实现
- 3
-
-
作者
张冰莹
程方
程渝
-
机构
重庆邮电大学通信与信息工程学院
重庆重邮汇测电子技术研究院有限公司
-
出处
《计算机应用与软件》
北大核心
2023年第1期156-162,215,共8页
-
基金
重庆市重点产业共性关键技术创新专项(cstc2019jscx-zdztzx0001)。
-
文摘
针对5G移动通信网络中海量用户数据流量增长,及多样化的业务应用场景需求,传统的LTE信令监测技术已经无法应用于5G新型网络架构。基于以上提出一种适用于5G路测仪的信令监测系统架构,并详细介绍信令监测系统中各模块的具体功能。重点分析5G网络中信令合成的原理及算法,在传统哈希信令合成算法基础上,提出一种基于平衡二叉树的动态哈希查找算法,利用树形结构以减少传统算法在哈希表中搜索数据所消耗的时间,从而快速处理哈希冲突,提高CDR合成的实时性。实验结果表明,改进的哈希信令合成算法可以有效解决CDR合成效率低下、平均遍历时间复杂度高等问题,同时可降低内存空间的资源浪费。
-
关键词
5G路测仪
信令监测
信令合成
平衡二叉树
哈希冲突
-
Keywords
5G driver test instrument
Signaling monitoring
Signaling synthesis
balanced binary search tree
Hash conflicts
-
分类号
TP3
[自动化与计算机技术—计算机科学与技术]
TN929.5
[电子电信—通信与信息系统]
-
-
题名左侧带权凸二分图动态权值匹配
被引量：1
- 4
-
-
作者
祖佺
张苗苗
刘静
-
机构
同济大学软件学院
华东师范大学上海市高可信计算重点实验室
-
出处
《计算机学报》
EI
CSCD
北大核心
2016年第11期2388-2402,共15页
-
基金
国家自然科学基金(61472279,61332008,91318301)资助
-
文摘
动态匹配问题是指在图结构变更的情况下求解某特定匹配,包括添加和删除图中顶点和边的更新操作以及计算匹配信息的查询操作.凸二分图是一类特殊二分图,在其顶点二划分(X,Y)中,Y顶点集为一个全序集,每个x∈X的邻点集在Y中形成一段连续区间.已有的凸二分图动态基数匹配算法不能求解权值匹配,因而该文研究左侧顶点带权凸二分图中动态最大权值匹配问题.文中提出一种问题求解的框架:在更新操作中维护参与匹配的顶点集合,继而在查询操作中计算相应的匹配信息.文中基于交错路定义了可替换集,并证明可通过计算可替换集来维护参与匹配的顶点集;提出紧致子图的概念,证明可替换集的求解等价于紧致子图的求解,从而将传统的通过寻找交替路求解匹配的方法改进为通过寻找子图结构来求解匹配.文中利用凸二分图的凸性质将紧致子图的计算转化为查找该子图中最大或最小y顶点操作,进而结合隐性表征技术在增广平衡二叉查找树数据结构中快速求解,继而设计动态匹配算法在O(log^2|V|)平摊时间下维护更新操作,在最坏线性时间下维护查询操作.较之于已知最好的解决不带权凸二分图动态基数匹配问题的方法,该文提出的方法能在与之相同的时间复杂度下解决难度更高的左侧带权问题.
-
关键词
凸二分图
动态匹配
交错路
紧致子图
隐性表征
平衡二叉查找树
-
Keywords
convex bipartite graph
dynamic matching
alternating path
tight subgraph
implicit representation
balanced binary search tree
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名基于多层混合结构的IPv6路由表查找算法
- 5
-
-
作者
邓亚平
周美红
-
机构
重庆邮电大学计算机科学与技术学院
-
出处
《计算机应用》
CSCD
北大核心
2013年第2期385-389,共5页
-
文摘
针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1～16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17～32位和33～48位分别用二叉平衡树组织,在第四层把49～64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。
-
关键词
路由查找
IPV6
二叉平衡树
最优查找树
线性表
-
Keywords
routing lookup
IPv6
balanced binary tree
optimal search tree
linear list
-
分类号
TP393.071
[自动化与计算机技术—计算机应用技术]
-
-
题名基于SBT全结点存储的云数据完整性
- 6
-
-
作者
周鹏
龙士工
-
机构
贵州大学计算机科学与技术学院
贵州省公共大数据重点实验室
-
出处
《计算机与现代化》
2018年第6期37-41,共5页
-
基金
贵州省公共大数据重点实验室项目(2017001)
-
文摘
云存储可以为用户提供高质量、按需分配的数据存储服务,使用户用低廉的价格就能享受到海量的存储能力,但是对于用户而言,云存储服务器并不是完全可信,因此会担心存储在云端的数据出现安全性问题,同时为了满足云中的应用,需要完整性验证机制支持全动态操作以及第三方公开认证。因此,提出一种基于全结点存储的云数据完整性方案。引入平衡二叉搜索树结构——结点大小平衡树(Size Balanced Tree,SBT),该结构使得树中所有的结点都可以用来存储实际的数据,相比叶子结点存储的树,无疑减少了服务器上的空间开销,同时降低了树的高度,从而也降低了进行数据插入删除等基本操作的时间复杂度。该方案在支持动态操作上具有更好的效率,能够很好地支持云存储环境下数据完整性验证。
-
关键词
云存储
数据完整性
动态操作
平衡二叉搜索树
全结点存储
-
Keywords
cloud storage
data integrity
dynamic operations
balanced binary search tree
total node storage
-
分类号
TP309.2
[自动化与计算机技术—计算机系统结构]
-
-
题名一种新的删除AVL树的结点的算法
被引量：4
- 7
-
-
作者
唐自立
-
机构
苏州大学计算机科学与技术学院
-
出处
《计算机应用与软件》
CSCD
北大核心
2005年第4期107-109,共3页
-
文摘
所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。
-
关键词
AVL树
结点
删除
FOSTER
新算法
时间复杂性
空间复杂性
自上而下
执行过程
时间比
子树
思想
-
Keywords
AVL tree Height-balanced binary search tree Node Deletion Rotation
-
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]
TP311.12
[自动化与计算机技术—计算机科学与技术]
-
