基于平衡因子的AVL树设计实现

平衡二叉树又称AVL树,得名于它的发明者G．M．Adelson—Velsky和E．M．Landis。作为一种常用的数据结构,许多教科书都详细描述了实现的算法,但是基本都是根据不同树形LL、RR、LR、RL给出相应逻辑,而且都是直接给出结论。而文中则以平衡因子为出发点,揭示了不同树形的一致性算法,第一次以数学公式推演,论证了AVL插入和删除操作在不同树形情况下,哪个节点开始失去平衡,怎么平衡以及哪个节点平衡结束,并给出算法的完整实现代码,使AVL的实现一致、简单、易懂。     

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

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

用C语言实现的AVL树查找方法

按照AVL树给定的算法模型,阐述了实现平衡二叉树内部查找和外部查找的过程和方法,并给出了用C语言实现的有关函数的源程序清单。     

度约束单源多目的路径问题的遗传算法

提出了一种求解度约束单源多目的路径寻优问题的遗传算法,算法采用节点路径形式的编码表示一棵生成树,并设计了相应的实现树形结构的交叉和变异算子,以及节点度的改变算法.本算法实现了具有树形结构染色体的遗传进化,数值实验表明了算法的有效性.该算法可以应用于大规模网络中求解目的节点比较多的路径寻优问题.     

面向凝聚式层次聚类算法实现的矩阵存储数据结构研究

快速查找、扩张、收缩是凝聚式层次聚类算法快速实现对相似度／距离矩阵存储的基本要求。本文提出了基于十字链表和平衡二叉树的复合数据结构CrossAVL用于矩阵的存储,给出了查找、扩张,收缩操作的实现并对其时间复杂度进行了分析。实验结果表明,Cross AVL对快速要求能够较好地满足。     

能量平衡和树型路由的AODVjr改进算法研究

在短距离无线通信技术的研究中,ZigBee的AODVjr算法在保持了AODV的原始功能的基础上,只选择最佳路由路径传输.但由于每个节点需保存路由表,因而增大了路由成本,并且上述算法未提出有效的措施来维持整个网络的能量平衡.确保节点不过度使用或经常空闲对低速率无线网络的节能优化尤为重要.为此提出一种基于能量平衡和树形结构的AOD-vjr改进算法.新算法首先判断传输数据类型,根据不同类型数据采取不同路由发现过程,然后在转发数据选择下一跳路由节点时要估计所有可选路径节点的剩余能量.为避免某些能量低的节点快速耗尽剩余能量而停止工作,在可选路径中选择剩余能量最多的节点完成数据的转发,从而控制网络能量的平衡.仿真结果表明,改进的AODVjr路由算法可有效减少网络开销,延长网络寿命.     

树形探测法及其在矿井排水智能流向计算中的应用

提出了确定复杂管路网络中流体流向的计算方法--树形探测法,通过将管路网络转化为树形拓扑结构,借助基于仿生算法的树形递归原理,在已知节点驱动类型的基础上,确定流体在整个系统各环节的流向。借助计算机语言C#,利用泛型参数技术、接口技术和基于委托技术的Observer设计模式实现了“树形探测法”通用组件接口。该算法被应用于神华神东锦界煤矿复杂排水系统的计算机仿真平台中,将闸阀、水泵和接头作为节点,管道作为边,利用树形探测法确定水流流向,应用效果较好。     

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

STL数据快速拓扑重建关键算法

在反求工程中,散乱数据点云的曲面重构常采用三角网格模型,建立三角网格之间拓扑关系的速度是影响曲面重建效率的关键因素之一．本文提出了基于V—F结构的平衡二叉树（AVL）顶点聚合算法,简化数据文件的存储容量至原来的18％～25％,并有效地去除了大量冗余数据点;采用虚AVL的快速邻边搜索优化算法,实现了相邻半边的快速搜索,高效地构建半边拓扑结构,最后通过各种零件重建速度的比较说明本文方法是高效的、可扩展的．     

时空最优的AVL树删除算法

本文给出了在AVL树中删除一指定结点的完整算法及一具体例子,分析了算法的复杂度。该算法的时间、空间复杂度分别为O(logn)和O(1),它在时间上和空间上都是最优的。