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

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

对改变线索二叉树结点结构中左右标志域涵义的探讨

给出了线索二叉树结点结构中ltag和rtag域新的涵义,讨论了新涵义对求先序后继结点算法、后序前趋结点算法以及求先序遍历算法带来的效果.     

基于集合的红黑树结点删除算法的实现

通过分析红黑树的定义和结点删除算法的具体步骤及实现细节,针对实际应用中存在的运用前台逻辑删除结点效率低下的问题,采用直接在后台实现删除操作来提高效率;并以面向集合的Transact-SQL语言为工具,在SQL SERVER 2005数据库上实现了红黑树结点删除算法。     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

结点度数组表示下的二叉树上两个算法的优化

先从理论上证明结点度数组表示下的二叉树上结点之间存在的某种关系 ,然后运用该关系 ,优化求二叉树上任意一个结点的左儿子结点和父亲结点的两个算法 .     

在二叉排序树上删除一个结点的算法改进

清华大学版《数据结构》教材上在二叉排序树上删除一个结点的算法存在不足,给出一个改进算法,并讨论了两种特殊情况下算法处理的方法。     

基于KD树最优投影划分的k匿名算法

针对现有数据发布隐私保护保护算法中的"局部最优"划分问题,提出了一种基于KD树最优投影划分的k匿名算法.首先,在全局范围内对每一个属性维度进行遍历,根据投影距离方差值衡量每个维度的离散度,并确定最优维度;然后,在最优属性维度上,计算其划分系数值,并确定最优划分点.进一步引入一种改进的KD树结构,与传统的KD树结点是一个数据点不同,新设计的KD树中的每个结点均是一个集合.用经过划分点并垂直于最优维度的超平面将一个结点分成两部分,分别作为其左、右孩子结点.最后通过理论分析证明了本文算法的正确性,用实验比较和验证了算法的性能,实验结果显示所提算法平均概化范围减小10%~22%,能够实现更优的划分和更好的数据集可用性.     

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

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

一种构建n个结点的二叉树所有形态的算法

给出了一种基于二叉排序树构建具有n个结点的二叉树所有不同形态的算法,该算法简单明了,易于理解和实现.     

B-树在查找第K大数中的应用

查找第K大数问题在计算机技术中具有重要的意义。本文提出一种基于B-树的第K大数查找算法,该方法在B-树的每个结点增加计数域来记录每个子树中关键字的个数,利用B-树的查找算法和计数域实现第K大数的查找以提高查找效率。     

一种平衡树的研究之四

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

基于统计的网页净化模板生成算法

同一个站点的大部分网页拥有几乎相同的DOM标签树,处理后的标签树作为一个模板,该站点的所有网页只保留这个模板中叶子节点包含的内容,由此可以实现这个站点的所有网页的净化。首先对一个站点内的一组样本网页提取内容块树,针对每个树统计每个标签节点包含的文本字数,同级节点只保留字数最多的一个,从而生成单边子树UST;然后把这组UST合并,同级节点中出现次数最多的即为重要内容节点,把这些节点串起来就构成重要单边子树PUST;最后比对每个父节点与子节点之间的字数,当比值超过一个阈值时则删除子节点以下的所有节点,从而生成该站点的重要单边子树SPUST。这个SPUST就是该站点的网页净化模板。     

基于内容的多媒体检索技术

在对海量的多媒体数据进行检索时,传统的基于数值/字符的信息检索技术并不能满足要求.因此,基于内容的多媒体检索技术的研究应运而生,其检索的依据主要是多媒体的特征向量值,因此多媒体信息特别是图像的特征向量的组织直接影响到数据检索的效率.对基于内容的多媒体检索技术进行了研究,同时借鉴基于关键字的检索技术,引进了二叉排序树来组织图像的特征向量,利用二叉排序树算法进行特征向量值的检索,提高了图像检索的效率.     

基于GPU的并行八叉树生成算法

提出了一种新颖的完全在GPU端以并行方式构造八叉树的算法。克服了以往GPU八叉树生成算法难以构建结点间的邻接关系以及对应用领域的局限性等困难,适用于在GPU中对散乱点云数据、三角网数据以及离散数据场数据构建八叉树。该方法以紧密排列的方式线性存储各层八叉树结点同时避免存储空结点信息,有效节约了存储空间并且提高了逐层并行遍历八叉树的效率。与传统的CPU单线程递归分割构造八叉树的算法相比较,速度可以提高一个数量级。     

二叉树构造算法解析

构造与遍历一棵二叉树历来为数据结构中不可缺少的内容。构造二叉树经典的算法通常都是以遍历二叉树为基础的,先决条件已知二叉树结点的左右孩子情况,或者是由先序和中序遍历序列、中序和后序遍历序列惟一确定一棵二叉树。通过对二叉树结构特点的分析,提出了三种不同的构造二叉树的算法,并加以分析。     

一种基于二叉树结构表达的二维实体布局算法

利用二叉树表达二维实体布局问题,得到一个完全自动的二维实体布局算法,算法的复杂性Ｏ（ｎ）,其中ｎ是区域树的结点数;提出了区域树面积因子,子树正方形、正方形子树新概念,给出了一个精美的旋转区域树的方法,证明了若干基本定理。     

基于滑动窗口的数据流中近期频繁项挖掘

提出了一种在单独数据流中挖掘近期频繁项的算法MRFI。该算法采用基于对时间敏感的滑动窗口的模式,保证了挖掘结果的时效性,并利用循环队列和二叉排序树实现了简单高效的数据存储和处理,该方法是一种近似算法,它可以消除历史数据对挖掘结果的影响。实验采用IBM数据发生器产生合成数据,证明了该算法的有效性。     

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

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

基于二叉推荐树的可信评估模型

在网络安全领域,可信被定义为一个实体期望另外一个实体执行某个特定动作的可能性大小。为了加强网络的安全性,允许某个结点去评估其他结点的可信性是非常重要的。本文主要讨论的是对可信事件的推荐评估。首先介绍了可信的相关概念和特性;接着,网络被抽象成一个有向图,在该图中,顶点代表实体或用户,边被看成可信关系,这样,评估过程可以看成是在有向图当中寻找最短路径问题,通过对影响推荐信任的因素分析,得到间接信任计算公式,为每个结点建立一个二叉推荐树,用来存储该结点能够推荐的结点以及这些结点推荐信任值,并在每个周期后动态地调整和整理该二叉推荐树;最后,对该模型的有效性进行了分析。     

二叉树的顺序表存储

目前,对二叉树存储结构主要有顺序存储结构和链式存储结构(二叉链表)2种.其中顺序存储结构主要用于完全二叉树,而链式存储结构可用于所有的二叉树,是比较常用的存储结构.但是这种二叉链式存储结构由于叶子结点指针域不能被利用,存在大量的空指针而导致整个树存储密度低下.同时,应用这种二叉链式存储,对二叉树进行遍历、结点查询等操作时,需要用到显式或隐式栈,进而增加各种算法额外的空间,导致空间复杂度较高,而且各种操作过程也相对较复杂.为了提高二叉树的存储密度,降低各种处理算法的空间复杂度,简化对二叉树的遍历、结点查询、线索化等有关操作的具体实现过程,结合完全二叉树存储的思想,采用增加虚拟结点的方式对二叉树的实际结点编号,提出改进的二叉树存储结构——顺序表存储结构.