一种新的删除AVL树的结点的算法

所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。     

基于AVL搜索树的证书吊销系统

针对公钥基础设施中的证书吊销问题,提出一种基于AVL。搜索树的解决方案,该方案在查询与更新时的最大时间复杂度始终保持在O（lbn）量级。实验结果表明,该方案是有效的,且对工程实现具有一定指导意义。     

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

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

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

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

巧绘平衡二叉排序树

一棵失衡的二叉树会出现根结点平衡因子是2和-2的两种失衡情况,此时需要采取适当的方法对其进行调整,使之平衡.结合学习实践,给出了绘制平衡二叉排序树的巧妙方法,辅以实例加以说明.     

AVL树算法的动态演示的设计与实现

《数据结构》是计算机学科中一门十分重要的核心课程,而对于算法的理解则是学好该课程的关键。为了使学生更好的理解算法,作为对课堂教学的有益补充,我们设计开发了《AVL树算法的动态演示》,以帮助学生理解数据结构算法。本文通过对这种交互式动态演示的设计实现过程的详细描述,着重讨论了AVL树动态演示的算法实现。     

数据结构二叉排序树的应用研究

随着图书商城的大型化,顾客对图书信息的检索量也随之俱增,如何提高图书信息检索效率已成为急需解决的问题。本文研究基于数据结构二叉排序树的图书信息动态检索方法,采用这种方法可提高图书信息的检索效率。     

AVL树在FAT文件系统中的应用与研究

FAT文件系统是一种适用于各种应用的优秀文件系统管理模式.通过深入分析FAT文件系统簇的组织管理模式,剖析其在实时性能上的不足之处,提出了利用AVL树来组织管理FAT文件系统内连续空闲块信息的新方法,并在此基础实现了文件读写等一系列优化算法.通过仿真测试,优化后的FAT文件系统在保持其兼容性的前提下,能有效地提高文件操作响应的实时性.     

二叉查找树的一种优化结构——Treap

二叉查找树是一种重要的数据结构,但它有一个致命的缺点,就是会退化成线性表,解决这一问题的常用方法是采用平衡树、红-黑树等复杂的数据结构,实现起来比较困难.本文提出一种较为简单的优化结构-Treap,它是采用随机化的思想,将二叉查找树和堆有效结合在一起,从而实现相对平衡的二叉树结构.     

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

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

求解最优二分搜索树

最优二分搜索树的求解在一些实际问题中是经常碰到的，本文首先对该问题以及已有的几种求解算法作一介绍和评述，之后给出求解ＯＢＳＴ的更优算法，以及其正确性证明和算法评价。该算法的时间复杂度为最好的结果９。     

“伸展树——一种高效的索引树”教学设计

数据结构设计的重要目标之一是提高操作速度,特别是检索速度。局部平衡的红黑树、平衡的AVL树等二叉搜索树具有良好的检索性能,非常适合于基于内存的索引,但为防止树形结构退化为线性结构,在插入和删除结点时经常需要旋转,维护数据结构的操作比较复杂。文章阐述伸展树在检索过程中通过自动调整结构,使访问最频繁的结点靠近树结构的根,从而减少访问代价,指出伸展树可以作为各种线性序列的索引组织方法,能在一些需要高效索引的大工程中加以运用。     

二叉排序树查找算法性能分析

查找是计算机中经常要用到的操作。二叉排序树排序树查找属于动态查找类,二叉排序树查找算法与建立算法密切相关。给出了一种计算二叉排序树平均查找长度的算法,希望能对查找算法的研究起到一点作用。     

基于平衡三叉树实现归并算法的研究

本文阐述了如何使用一种新的数据结构“平衡三叉树”来对Netflow数据采集协议采集到的数据进行归并。分析和详细说明了平衡三叉树的算法,通过测试数据证明平衡三叉树算法的性能是稳定和良好的。     

严格平衡二叉排序树类属类

对严格平衡二叉排序树的查找时间复杂度进行了详细分析,给出了平均查找长度的计算公式及其渐进性态的误差估计。基于C＋＋语言的模板,提出了严格平衡二叉排序树类属类的总体设计方案及主要成员函数的详细设计。最后提出了有关严格平衡二叉排序树平均查找长度近似计算的绝对误差的一个猜想,以及有关广义严格平衡二叉排序树的一种构想。     

三阶B树的构造与应用

本文给出两种构造三阶Ｂ树的算法，证明算法的时间复杂性，并给出用三阶Ｂ权实现热力公司的数据管理实例。     

基于AVL树的STL模型快速拓扑重建算法

STL数据格式是目前广泛应用于CAD系统中进行数据交换的标准格式之一。使用三角面片表示实体表面信息。但STL数据格式具有数据冗余和缺乏拓扑信息的缺点,针对这一问题,本文采用半边数据结构,提出一种基于辅助AVL树的STL模型快速拓扑重建算法,能快速有效地去除冗余顶点及实现半边合并。     

动态规划法构建最优二叉查找树的研究

提出动态规划法构建最优二叉查找树的算法模型,并对其进行改进,构造实例表明算法的有效性。     

Concurrent Manipulation of Expanded AVL Trees

The concurrent manipulation of an expanded AVL tree(EAVL tree)s considered in this paper.The presented system can support any number of concurrent processes which perform searching,insertion and deletion on the tree.Simulation results indicate the high performance of the system.Elaborate techniques are used to achieve such a system unavailable based on any known algorithms.Methods developed in this paper may provide new insights into other problems in the area of concurrent search structure manipulation.