共查询到20条相似文献,搜索用时 796 毫秒
1.
B-树是一种平衡的多路查找树,在文件系统中有着很好的应用。该文分析了在B-树中删除一个关键词的几种情形,给出了B-树删除算法的具体实现,有助于对《数据结构》课程中B-树操作的更好理解。 相似文献
2.
3.
唐自立 《计算机工程与应用》2007,43(5):45-48
Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。 相似文献
4.
唐自立 《计算机工程与应用》2007,43(5)
Foster的删除HB(κ)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退.提出一种新的删除HB(κ)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.举例说明新算法的执行过程.证明新算法是正确的.与Foster的删除HB(κ)树的结点的算法相比,新算法不涉及辅助栈的使用.设n是HB(κ)树的结点的个数.新算法的时间复杂性是0(log2n),与Foster的删除HB(κ)树的结点的算法的相同.实验结果表明新算法的平均执行对间比Foster的删除HB(κ)树的结点的算法短.新算法的空间复杂性是O(1),比Foster的删除HB(κ)树的结点的算法低. 相似文献
5.
6.
一种新的删除AVL树的结点的算法 总被引:4,自引:1,他引:3
唐自立 《计算机应用与软件》2005,22(4):107-109
所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。 相似文献
7.
DNA分子特性使得DNA计算具有极大的存储密度和高度的计算并行性。不管何种计算模型,DNA分子的选择和DNA编码都十分重要。提出了DNA计算中的B-树的数据结构设计方法。首先给出了B-树定义及其操作的形式化描述,接着介绍了本计算模型采用的3D结构DNA分子——k-arms分子结构,详细给出了一棵m阶B-树的构造步骤,最后实现了其查找、插入和删除等操作。提出了DNA分子计算的3D结构和分治策略,具有一定的可扩展性和并行性,对DNA计算的其他模型有参考价值。 相似文献
8.
9.
10.
为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法(BTBF)。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。 相似文献
11.
一种新的删除红黑树的结点的算法 总被引:5,自引:0,他引:5
唐自立 《计算机应用与软件》2006,23(1):139-141
提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O(1)次旋转。新算法的时间复杂性是O(log2n)。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O(1)。 相似文献
12.
P2P系统的研究现在较多集中在对非集中式系统的结构及搜索策略上。本文构造了基于语义的一种混合P2P系统,并且给出了各种常规的操作算法。本文首先引入了d-树的概念,并将Racke树的思想引入了P2P查寻操作中,简单分析了各种操作的最坏时间复杂度。 相似文献
13.
本文介绍的新索引结构准平衡树是在对B-树进行改造的基础上提出的。该结构打破了B-树结构的平衡限制,使根结点总是处于充满的状态,从而获得平均有一半数据比同情况下的B-树减少-次I/O的效果。该结构上的查询方法与B-树相同。维护代价仅比B-树有极小的增加。 相似文献
14.
唐自立 《计算机工程与应用》2008,44(12):34-37
Andersson的删除AA-树结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AA-树结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Andersson的算法相比,新算法不涉及辅助栈的使用。设n是AA-树的内部结点的个数,执行新算法时进行O(lbn)次旋转,新算法的时间复杂性是O(lbn),与Andersson的算法的时间复杂性相同。实验结果表明新算法的平均执行时间比Andersson的算法的平均执行时间短。新算法的空间复杂性是O(1),比Andersson的算法的空间复杂性低。 相似文献
15.
针对目前内存数据库中索引缓存失配的问题,在分析了现有内存数据库索引结构基础上,提出了一种缓存敏感T树(CST树)的索引数据结构,详细数据结构描述和操作算法也已给出。通过CST树的缓存次数分析和进行查询、插入等操作性能测试,结果表明CST树能有效减少缓存敏感次数,并且在数据量较小时,CST树的插入、删除速度比T树略慢,而查询速度比T树要快。在数据量较大时,CST树的插入、删除、查询效率都比T树要高。 相似文献
16.
17.
云存储可以为用户提供高质量、按需分配的数据存储服务,使用户用低廉的价格就能享受到海量的存储能力,但是对于用户而言,云存储服务器并不是完全可信,因此会担心存储在云端的数据出现安全性问题,同时为了满足云中的应用,需要完整性验证机制支持全动态操作以及第三方公开认证。因此,提出一种基于全结点存储的云数据完整性方案。引入平衡二叉搜索树结构--结点大小平衡树(SizeBalancedTree,SBT),该结构使得树中所有的结点都可以用来存储实际的数据,相比叶子结点存储的树,无疑减少了服务器上的空间开销,同时降低了树的高度,从而也降低了进行数据插入删除等基本操作的时间复杂度。该方案在支持动态操作上具有更好的效率,能够很好地支持云存储环境下数据完整性验证。 相似文献
18.
在用差别矩阵思想设计的属性约简算法中,由于差别矩阵存在大量重复和无用的差别元素,不仅占用大量的存储空间,而且浪费属性约简的计算时间。为提高这种属性约简算法的效率,结合FP树(频繁模式树)的思想,给出一种新型的数据结构——改进的FP树(IFP_Tree)。改进的FP树可以完全删除差别矩阵中所有重复的差别元素,也可以完全删除无用的差别元素。不但减少了大量的存储空间,还大大提高了属性约简算法的效率。用IFP树设计一种新的快速属性约简算法。实例说明了该算法的有效性。 相似文献
19.
视图增量更新算法作为提高移动数据库响应性能的重要手段已有许多研究。随着XML结构在移动数据库中的应用,现有的算法不适用于目前移动数据库中存储的数据。提出了以XML树型结构为基础的一种新的视图增量更新算法XSIU(XML Structured-based Incremental Update),通过该算法能有效解决视图的增量更新在XML中的实现。实验表明,当带宽急剧下降时,该算法能有效提高移动环境中视图的增量更新性能。 相似文献