一种采用最优二叉查找树的二维工程图内容认证零水印算法

为了对二维工程图内容的完整性进行认证,提出一种基于最优二叉查找树的零水印算法.首先对二维工程图中各个实体的拓扑结构进行编码,再与实体的句柄值相结合,进行小波分解后利用细节系数构造零水印.试验与分析表明该算法对不改变二维工程图内容的整体缩放、旋转、平移等操作具有较好的鲁棒性,对改变二维工程图内容的操作,如局部平移、实体删除、实体添加等恶意操作极度敏感,同时该算法还能够对二维工程图内容的篡改具有一定的定位能力.

一种构建最优二叉查找树的贪心算法

分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。

二叉查找树的分析与探讨

在给定的关键字进行序列编排的各种系统软件或应用软件中,"动态查找"是一种快速有效的查找方法。为了更好地掌握"动态查找"应用过程,对二叉查找树的求解过程进行了详细的分析和算法描述。

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

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

基于贪心算法构建最优二叉查找树

分析二叉查找树与赫夫曼树各自的特点,提出了一种构建最优二叉查找树的算法即贪心算法,并用VC++程序设计语言编码实现.实验结果表明:贪心算法不仅趋于稳定、时间效率明显优于动态规划算法,而且还实现了其数据规模达到20 000时空间上的突破.

二叉查找树的函数式语义实现

二叉查找树是数学建模、算法分析中常用的数据结构。函数式语义具有无副作用特性与类型高度抽象能力,用其表达数学模型简练明了。本文采用属于函数式语义的类haskell伪码实现了二叉查找树,并进行了相关算法分析。

在二叉查找树上删除结点的算法与实现

本文首先介绍了在二叉查找树上删除结点的典型算法,然后将其与2004年上半年全国计算机软件考试软件设计师级下午试题五中所采用的算法作了分析与比较,并对考生答题中出现的问题进行了讨论。

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

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

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

平衡二叉查找树是计算机中有效地组织大规模查找数据的主要手段,因为在树的创建、节点的插入、删除过程中都维持了树的平衡.AVL树是平衡二叉查找树,但是AVL树在创建、插入、删除时维护树的平衡操作需要按照平衡因子的不同情况分别进行处理,程序长,实现过程繁杂.本文利用树的高度提出一种新的AVL平衡树数学描述—高度平衡树(HAVL),并进行了理论分析:HAVL在旋转操作的同时维持节点的高度信息,从而使位于上层的函数不必重新计算统计域,维持树的平衡的各种情况可以统一简洁处理,该数学描述简洁,程序实现直观,程序实现代码量小,维持平衡的C语言代码是一般AVL平衡树的代码长度的大约1/5左右.实验结果表明,HAVL能够保持AVL树的优秀特性,运行时间更短.

AVL树研究与实现

计算机最广为人知的优点之一是其能储存大量的数据,如今随着时代的发展,储存容量更是犹如日进千里一般极速扩展,大容量的硬盘、U盘早已随处可见。然而,要在巨大的数据中搜索出需要的内容却不是一件容易的事,由此,为了能减少在搜索储存数据上的开销,各种适应于不同访问搜索背景的数据结构应运而生。树,便是计算机学科中最基本的数据结构之一,提供了快速的储存和访问性能。该文探究了带有平衡条件的二叉查找树——AVL树的原理,并对其使用C语言进行了实现。

左侧带权凸二分图动态权值匹配

动态匹配问题是指在图结构变更的情况下求解某特定匹配,包括添加和删除图中顶点和边的更新操作以及计算匹配信息的查询操作.凸二分图是一类特殊二分图,在其顶点二划分(X,Y)中,Y顶点集为一个全序集,每个x∈X的邻点集在Y中形成一段连续区间.已有的凸二分图动态基数匹配算法不能求解权值匹配,因而该文研究左侧顶点带权凸二分图中动态最大权值匹配问题.文中提出一种问题求解的框架:在更新操作中维护参与匹配的顶点集合,继而在查询操作中计算相应的匹配信息.文中基于交错路定义了可替换集,并证明可通过计算可替换集来维护参与匹配的顶点集;提出紧致子图的概念,证明可替换集的求解等价于紧致子图的求解,从而将传统的通过寻找交替路求解匹配的方法改进为通过寻找子图结构来求解匹配.文中利用凸二分图的凸性质将紧致子图的计算转化为查找该子图中最大或最小y顶点操作,进而结合隐性表征技术在增广平衡二叉查找树数据结构中快速求解,继而设计动态匹配算法在O(log^2|V|)平摊时间下维护更新操作,在最坏线性时间下维护查询操作.较之于已知最好的解决不带权凸二分图动态基数匹配问题的方法,该文提出的方法能在与之相同的时间复杂度下解决难度更高的左侧带权问题.

一种规则集快速压缩算法

实际应用中的规则集表现出很强的聚集特性,针对这一特性提出一种规则集快速压缩算法.快速压缩算法是一个由粗到细的先分类再合并压缩的过程,首先通过使用Hash函数将提取的规则信息散列并以散列值作为查找关键字构建二叉查找树实现粗略分类,然后在树结点对应的Hash函数冲突列表中逐条比较完成精确分类,最后合并冲突列表中的规则实现压缩.实验结果表明,与逐条规则逐个域比较的简单压缩方法相比,快速压缩算法在保持较高压缩率的前提下,能够将压缩时间平均减少90%以上.

基于前缀码的快速编码算法研究

针对目前符号序列的编码存在编码速度慢的问题,提出了一种通过减少平均查找长度来提高编码速度的算法。根据符号概率的大小,设计了顺序查找、大概率优先查找和小概率优先查找三种编码算法。通过对这三种编码算法的平均查找长度的分析比较,结果表明:大概率优先查找算法的平均查找长度最短。根据符号本身的大小,设计了折半查找和二叉排序树查找两种编码算法。通过对这两种编码算法的平均查找长度的分析比较,结果表明折半查找编码算法的平均查找长度最短。因此,最优的编码算法应从大概率优先查找算法和折半查找算法之中选择其一。算例表明,为了提高符号序列的编码速度,对同一符号序列的编码,应从大概率优先查找算法和折半查找算法中选择平均查找长度最短的算法作为编码算法。