一种平衡树的研究之五

本文是文[4]的续篇,该文研究两棵平衡树之间的操作,通过两棵平衡树的同时操作,完成两个集合之间的各种运算,如测试集合包含关系(ISSUBSET)、求集合的并(UNION)、求集合的交(INTERSECT)、求集合的差(DEDUCT)、按关键字序列的连接(CONCATENATE)、拆分(SPLIT)、空间压缩(COMPACT)等算法。重要算法给出了时间复杂度证明。     

一种平衡树的研究之二

本文是文[1]的续篇,该文定义了集合运算中公用的各种栈,对BT中结点进行了分类,详细论述了四个函数(Search、Findmax、Findmin、Leftmost)和四个过程(Lmrmax Minorder Minorderl Move)的功能定义与算法的实现,并给出时间复杂度的证明。     

一种平衡树的研究之三

本文是文[2]的续篇,在文[2]Search(f,r,a)函数基础上对平衡树的插入算法Inseart(r,a)进行了深入的研究。在Inseart(r,a)算法中,构造了INSEARTASLEAF(f,a)过程,对该过程中的INSEARTASLEAF31(f,a)算法进行了详细论述,最后给出了Inseart(r,a)时间复杂度的证明。     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

一种快速构建平衡二叉搜索树的算法

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

一种平衡树的研究之四

本文是文[3]的续篇,该文研究如何在一棵平衡树中删除一个结点后仍保持平衡。若删除结点后无法保持平衡,对原平衡树中的有效结点逐个取出进行重建平衡树。本文在给出删除算法(delete)的同时,给出了后根删除(postd)、建树(maketree)、构造(construct)、合成(compost)、嵌入(implant)等算法。最后给出删除算法的时间复杂度证明。     

一种新的树的遍历方法

树是一种非常重要的非线性的数据结构,对它的遍历一般有三种方法:先根序遍历、后根序遍历和按层次遍历.但在实际应用当中,我们可能需要不同于以上三种方法中的任何一种,这就要求我们对树的遍历不能仅仅有以上三种方法.提出了一种新的树的遍历方法,并且还给出了非递归算法的详细描述,以及算法的时间和空间的复杂度分析.     

一种基于二叉平衡树的P2P覆盖网络的研究

F2P覆盖网络是一种对等网之间的逻辑连接构成的应用层网络,由于其易于构建、管理灵活、可扩展性强,在实现瓦联网上的多种应用中发挥着重要的作用,文章首先给出了二叉平衡树的结构,然后在此基础上提出了一个能够同时支持高效的精确查询和范围查询能力的P2P覆盖网络拓扑结构,最后给出了该拓扑网络的节点加入和退出过程。     

一种简化的AVL树的实现方法

平衡二叉查找树是计算机中有效地组织大规模查找数据的主要手段,因为在树的创建、节点的插入、删除过程中都维持了树的平衡.AVL树是平衡二叉查找树,但是AVL树在创建、插入、删除时维护树的平衡操作需要按照平衡因子的不同情况分别进行处理,程序长,实现过程繁杂.本文利用树的高度提出一种新的AVL平衡树数学描述-高度平衡树(HAV...     

基于AVL树的平衡维护研究

本文提出了AVL树的平衡调整简单算法。通过理论分析,表明该算法具有理想的运算效率。与传统的调整方法比较,该算法简单易行、容易理解、形式规范,因此,无论用于教学还是解决实际问题,都有较大的实用价值。     

失效树分析的一种算法

本文介绍相干失效树的一种确定性算法:比特变换——分类去冗算法。本算法程序如稍加改动,即可用于非相干失效树的计算。     

一种基于QAAR-树的空间索引方法

针对QCR-树聚类个数需事先确定和处理高维空间数据时面临着"维数灾难"的问题,通过自动确定K-means算法的聚类个数和初始聚类中心,来提高聚类质量,并对原始高维空间数据进行近似压缩来减少磁盘读写代价,提高查询效率,提出一种QAAR-树空间索引结构,同时给出QAAR-树的插入、删除和查询算法。实验结果表明,QAAR-树的查询性能优于QCR-树,能够有效地处理海量高维空间数据。     

二叉排序树转换成平衡二叉树

结合概念,运用动态图形,用通俗的语言,分析二叉排序树转换成平衡二叉树的过程。     

关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

一种基于路由树的裁剪算法

多点广播技术已日益广泛应用到多媒体通信网络之中,多点广播路由策略是该项技术的关键部分。文章针对现有的多点广播路由策略存在的问题,提出了改进方法并给出了一种基于树型结构的冗余路由信息剪裁算法。     

B-树／B＋树的批量插入算法

本文对传统的B-树／B 树插入算法进行改进,提出了B-树／B 树的批量插入的算法,在理论上估计了该算法的复杂度。并进行了比较实验．实验结果表明：本算法在对大批量的关键字建立索引时。大大提高了B-树／B 树的插入效率。而且同时还适用于更新索引。     

关于к—Suslin树的自乘积树

在定义了一般树的乘积树以后，讨论了文献「１」中关于к－Ｓｕｓｌｉｎ树的自乘积树的一个例题，证明了当к为正则基数时，к－Ｓｕｓｌｉｎ树的自乘积树不再是к－Ｓｕｓｌｉｎ树的自乘积树不再是к－Ｓｕｓｌｉｎ树的自乘积树不再是к－Ｓｕｓｌｉｎ树，并构造了一个ω－Ｓｕｓｌｉｎ树，其自乘积树仍然是ω－Ｓｕｓｌｉｎ树。     

求解度约束最小生成树的一种启发式方法

针对网络设计和优化中度约束最小生成树问题,提出了一种基于贪心思想的启发式算法求解度约束最小生成树.在最小生成树的基础上,将超过度约束的顶点降低度数使之满足度约束条件.经大量数据测试并与其他算法进行比较,表明了该算法的有效性和通用性.     

一种最佳二叉排序树的动态检索算法

给出一种最佳二叉排序树的动态检索算法,其性能优于二叉排序和平衡二叉树,克服了用折半检索方法构造最佳二叉排序树的缺点,且不会因插入结点而发生蜕变,影响检索的性能。