二叉排序树结点删除算法的另一种思路

树的应用是数据结构的一个重点内容,而二叉排序树结点删除算法是树的应用的难点内容。二又排序树是指二叉树中任一结点,如有左子树,则左子树各结点的数据城必须小于该结点的数据域;如有右子树,则其右子树备结点的数据域必须不小于该结点的数据域。其特点是对该树进行一次中序遍历,打印出各结点的数据域值,可得到一个非递减序列,所以也可以看作是排序算法的一种。如果要求删除二又排序树的某一个结点,删除之后的树依然是二叉排序树,称为二叉排序树结点的删除。二叉排序树结点删除的算法,目前使用较多的是根据被删除是否二叉排序树…     

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

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

一种有效的丰满树算法

本文提出了一种新的有效的丰满树数据结构及其插入、删除、查询、中序周游等的基本算法。这种数据结构不用指针场,而用顺序地址标法来保持树中结点的联系,从而使空间复杂度大为减少,而且其算法也得以简化。在插入、删除的结点个数相对于文件规模不算太大的情况下,该算法的时间复杂度也是比较好的。     

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型--等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).     

基于多元分类树示例学习算法的改进

以往基于多元分类树示例学习算法的适用范围，只限于每优选一个属性结点都至少能导致一个树叶结点的情况。本文给出的改进算法无此限制，从而拓宽了基于多元分类树示例学习方法的应用范围。     

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

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

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

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

基于主干树的最小代价组播路由算法

提出基于主干树的最小代价组播路由算法,该算法首先在网络中找出K个代价最小的结点,然后以这K个结点形成一棵树,并称这棵为主干树,然后将不在主干树上的成员结点加入到树上,最后剪去非成员的叶结点。该算法的时间复杂度O(n^3)。该算法所构造的组播树代价略低于MPH算法和KMB算法。     

数据流重组中Hash-Splay查找算法

针对高速网络取证目前所面临的问题,围绕提高网络数据流重组效率,在数据流重组算法中分析比较了几种典型的查找算法,并将Hash表和Splay树组合成Hash-Splay查找算法.该算法首先建立Hash表,然后将所有的TCP连接结点分配到各个表项,每个表项用Splay树将该表项的所有连接结点组织起来.查找时,根据连接标识通过Hash函数计算出Hash地址,再对该Hash地址对应的Splay树进行查找,找到后按照Splay树的操作规则进行查找、插入和删除等操作.由于根据连接标识找到对应Splay树的时间开销很小,可以忽略不计,因此Hash-Splay算法的复杂度可以看作是每棵Splay树操作的平均复杂度,算法同时具有Hash表和Splay树的优点,查找效率比Hash表和Splay树的都高.     

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

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

关于树中广播问题的一种算法

讨论树中广播问题的一般情形,在树T中任意两个结点u_i,u_j之间通一次电话所需单位时间数ωt(u_i,u_j)为任意值的条件下,给出了一种新的算法BROADCAST-LHM.该算法可确定T中任意结点u的广播数b(u,T).T的广播数b(T)以及T的广播中心BC(T),且时间复杂度为O(N~2)。     

一种平衡树的研究之五

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

树的一种线性化算法

给出了一种树的线性化算法以及从线性化结果重构树的算法.这种线性表表示法比树的其它表示法更简洁、更易管理、更节约空间.在线性表表示方式下,实现了树的求结点双亲、求结点孩子、求树的高度3个运算.从具体实现过程可以看出,线性表表示法对树的常见运算的实现都比较方便.     

基于链表结构的频繁模式树构造

FP-Growth算法在关联规则挖掘中是最经典的算法,主要通过频繁模式树(FP树)避免生成候选频繁项目集.针对FP-Growth算法中耗费内存严重的问题,采用链表存储方式,给出了FP-Growth算法的实现方法,其中单个结点采用链表形式来产生,频繁模式树采用左孩子右兄弟的存储结构来组织.在此基础上利用索引表,实现了对频繁模式树中共同前缀结点的快速查找,提高了频繁模式树构造的效率,解决了FP树构造算法中数据存储的瓶颈问题.最后以天体光谱数据和城市土壤数据作为数据集分别对该算法进行测试,实验结果表明,该方法的构造效率要明显优于基于顺序结构的FP-Growth算法.     

一种平衡树的研究

本文给出一种平衡树(BT)的定义,对BT的性质进行了证明,然后对BT定义了遍历算法,最后给出了用BT实现集合14种操作(过程或函数)的定义。     

一种基于CHT的可扩展非对称二分查找平衡算法

从讨论非对称二分查找树的平衡问题出发,给出了一种通用的平衡权函数构造方法,解决了Waldvogel等在算法优化过程中提出的启发式平衡权函数构造问题,优化了非对称二分查找树平衡算法,使得CHT(collection of hash tables)算法很容易扩展到128 bit的IPv6地址.实验表明,该算法与Waldvogel等在特殊情况下给出的推测结果基本符合,能很好地适应IP前缀分布的变化,具有很好的适应性和可扩展性.     

浅谈一种扩展的数据结构——跳表

跳表(SkipList)可以被看为是二叉树(BinaryTree)的一种替代品。这种扩展的数据结构采用了概率算法以维持树的平衡。该算法对跳表来说非常简单而且也非常快速。这使跳表相对其它数据结构有更多的吸引力。在这篇文章里,笔者将对跳表的结构和基于跳表结构的查找、插入、删除的算法进行讨论。     

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

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

哈夫曼树的图形化算法设计

哈夫曼树是一类带权路径长度最小的树,由于它的非线性结构导致其很难实现图形化.为了排版需要以及更直观地了解哈夫曼树的性征,希望通过一种算法画出易于观察的哈夫曼树,算法建立在传统哈夫曼编码算法基础上,利用哈夫曼编码的工作空间,建立与哈夫曼编码相对应的哈夫曼树,这种树具有结点排列有致、层次分明、结点及结点间路径永不重合的特点.     

基于哈希和合并技术的FP-Growth新算法

对频繁模式增长(FP-Growth)算法进行了改进,用哈希头表代替头表.通过合并频繁模式树(FP-Tree)中支持数相同的结点,压缩了树的规模,有效地节省了空间.实验结果表明,改进后的算法在查找效率上有了大幅度的提高,可以更好地适用于大规模数据集的关联规则挖掘.