一种构建严格平衡二叉搜索树的非递归算法 被引量：4

1

作者 王防修 周康 《武汉工业学院学报》 CAS 2013年第4期32-34,43,共4页

针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出... 针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。 展开更多

关键词 二叉搜索树 平衡二叉树 严格平衡二叉树 平衡二叉搜索树 严格平衡二叉搜索树

在线阅读 下载PDF 职称材料

随机二叉搜索树的子树 被引量：2

2

作者 苏淳 缪柏其 冯群强 《应用概率统计》 CSCD 北大核心 2006年第3期304-310,共7页

本文讨论随机二叉搜索树上不同大小的子树和与给定某个二叉树同构的子树．利用递归分布等式,我们得出了它们各自数目的期望和方差．最后,用压缩法得出了它们的中心极限定理．

关键词 二叉搜索树 中心极限定理 概率分布的距离 不动点

在线阅读 下载PDF 职称材料

一种快速构建平衡二叉搜索树的算法 被引量：2

3

作者 胡云 黄震宇 《大庆师范学院学报》 2008年第2期20-22,共3页

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

关键词 AVL树 平衡二叉树 二叉搜索树

在线阅读 下载PDF 职称材料

关于出栈序列、二叉树、二叉搜索树三个问题计数的一致性 被引量：2

4

作者 吴集林 《广东广播电视大学学报》 2005年第4期106-107,110,共3页

本文用递归的方法对出栈序列、二叉树、二叉搜索树三种计数问题进行了分析,得到了一个统一的递推关系式,作者分析了这三个问题同解的原因,指出了这三个问题是同构的,对于这三个问题的解,用C++语言编程实现了算法。

关键词 出栈序列 二叉树 二叉搜索树 同构

在线阅读 下载PDF 职称材料

缠藤的二叉搜索树（英文） 被引量：1

5

作者 陈铁灵 EDWARDS Dylon 马俊 《湘潭大学自然科学学报》 CAS 北大核心 2013年第3期1-8,共8页

引入了一个基于节点的,利用二叉搜索树以及有序链表特性的数据结构.节点之间的链接分为两种类型,其中一种用来构造一个链表的结构,另一种用来构造一个二叉搜索树的结构.这种字典类的数据结构提供了O(logn)时间的以键为基础的搜索运算,... 引入了一个基于节点的,利用二叉搜索树以及有序链表特性的数据结构.节点之间的链接分为两种类型,其中一种用来构造一个链表的结构,另一种用来构造一个二叉搜索树的结构.这种字典类的数据结构提供了O(logn)时间的以键为基础的搜索运算,以及当增加和消除元素时的维护过程.另外,此数据结构也以O(logn)的时间来支持容错的搜索,并使得从某个特定元素开始的连续搜索非常有效.双向链表结构和单向链表结构在文章中都分别得到了考虑. 展开更多

关键词 二叉搜索树 字典 有序链表

在线阅读 下载PDF 职称材料

随机二叉搜索树上的若干强极限性质

6

作者 卢霄青 彭维才 《安徽工业大学学报（自然科学版）》 CAS 2009年第1期96-101,共6页

设随机变量Xn,Yn,Zn和Sn,k分别表示大小为n的随机二叉搜索树上的具有0,1,2个子顶点的顶点数目及大小为k的子树的数目,得到了关于它们的一些强极限性质。

关键词 随机二叉搜索树 极限性质 顶点 子树

在线阅读 下载PDF 职称材料

基于动态规划的最优二叉搜索树算法的改进 被引量：1

7

作者 刘岩 《电脑知识与技术》 2008年第12Z期2176-2177,2180,共3页

基于动态规划的最优二叉搜索树构造算法,选择子问题的划分时,r值的循环范围过大,存在不足。本文对此改进,缩小了r值的范围,算法时间复杂度由O(n3)减小至O(n2),并对两个算法的优劣进行了比较。

关键词 动态规划 最优二叉搜索树 算法改进

在线阅读 下载PDF 职称材料

最优二叉搜索树的动态规划算法研究

8

作者 陶荣 赵文静 《电脑知识与技术》 2008年第12Z期2188-2189,共2页

动态规划算法的有效性依赖于问题本身具有最优子结构性质和子问题重叠性质。该文给出了用动态规划算法构造最优二叉搜索树的详细步骤,并用C++语言具体实现了该算法。用一定的空间换取时间,提高了解决本问题的效率。

关键词 动态规划算法 最优子结构 子问题重叠 最优二叉搜索树

在线阅读 下载PDF 职称材料

基于AVL搜索树的证书吊销系统 被引量：1

9

作者 周海岩 赵建洋 《计算机工程》 CAS CSCD 北大核心 2009年第9期174-175,178,共3页

针对公钥基础设施中的证书吊销问题,提出一种基于AVL搜索树的解决方案,该方案在查询与更新时的最大时间复杂度始终保持在O(lbn)量级。实验结果表明,该方案是有效的,且对工程实现具有一定指导意义。

关键词 公钥基础设施 证书权威 证书吊销 二叉搜索树 AVL搜索树

在线阅读 下载PDF 职称材料

求解最优二分搜索树

10

作者 庞其祥 《软件》 北大核心 1995年第7期61-64,F003,共5页

最优二分搜索树(即Optimal Binary Search Tree,简记为BST)的求解在一些实际问题中是经常碰到的。本文首先对该问题以及已有的几种求解算法作一介绍和评述,之后给出求解OBST的更优算法,以及其正确性证明和算法评价。该算法的时间复杂度... 最优二分搜索树(即Optimal Binary Search Tree,简记为BST)的求解在一些实际问题中是经常碰到的。本文首先对该问题以及已有的几种求解算法作一介绍和评述,之后给出求解OBST的更优算法,以及其正确性证明和算法评价。该算法的时间复杂度为最好的结果9(nlogn)。 展开更多

关键词 最优二分搜索树 二叉搜索树 OBST 数据结构

在线阅读 下载PDF 职称材料

随机二叉树的几种拓扑指标(英文)

11

作者 骆崇亮 冯群强 张曙光 《中国科学技术大学学报》 CAS CSCD 北大核心 2013年第12期967-974,共8页

主要研究了随机二叉搜索树、随机Catalan树、随机数字搜索树这3种随机二叉树模型下的Zagreb指数.首先得到随机二叉搜索树关于该指数的均值和方差,再用一种新的方法即压缩法得到渐近正态性.然后给出了随机Catalan树和随机数字搜索树的同... 主要研究了随机二叉搜索树、随机Catalan树、随机数字搜索树这3种随机二叉树模型下的Zagreb指数.首先得到随机二叉搜索树关于该指数的均值和方差,再用一种新的方法即压缩法得到渐近正态性.然后给出了随机Catalan树和随机数字搜索树的同种指数的渐近正态性.最后简单讨论了两个与Zagreb指数密切相关的拓扑指数即Gordon-Scantlebury和Platt指数. 展开更多

关键词 随机树 拓扑指数 二叉搜索树 Catalan树 数字搜索树 压缩法

在线阅读 下载PDF 职称材料

基于B_树的证书吊销实用系统 被引量：1

12

作者 周海岩 《计算机工程》 CAS CSCD 北大核心 2009年第21期162-163,166,共3页

针对公钥基础设施PKI中证书吊销问题,提出一种B_树解决方案,将查询与更新时的最大时间复杂度始终保持在O(logd((n+1)/2)+1)量级,与其他方案相比,当数据量特别大时,更能显示其优越性,同时介绍基于B_树的证书管理方案。实验结果表明,该方... 针对公钥基础设施PKI中证书吊销问题,提出一种B_树解决方案,将查询与更新时的最大时间复杂度始终保持在O(logd((n+1)/2)+1)量级,与其他方案相比,当数据量特别大时,更能显示其优越性,同时介绍基于B_树的证书管理方案。实验结果表明,该方案对工程实现具有一定指导意义。 展开更多

关键词 公钥基础设施 证书权威 证书吊销 二叉搜索树 B_树

在线阅读 下载PDF 职称材料

快速构建AVL树 被引量：2

13

作者 胡云 《安阳师范学院学报》 2007年第5期61-63,共3页

传统AVL树的构建是从空树开始依次将结点插入进来,每插入一个结点就要判断新得到的新树是否满足AVL树的性质,如满足则继续下一个结点的插入,如不满足则先要将之调整为AVL树再插入下一结点,直至结束。这种方法需要对生成的中间树频繁地... 传统AVL树的构建是从空树开始依次将结点插入进来,每插入一个结点就要判断新得到的新树是否满足AVL树的性质,如满足则继续下一个结点的插入,如不满足则先要将之调整为AVL树再插入下一结点,直至结束。这种方法需要对生成的中间树频繁地进行调整,耗时较多。本文提出了一种新的简单的方法,主旨是采用递归思想实现:先将数据进行排序,然后将中点数据作为AVL树的根,小于中点数据的数据构成AVL树的左子树,大于中点数据的数据构成AVL树的右子树。 展开更多

关键词 AVL树 平衡二叉树 二叉搜索树

在线阅读 下载PDF 职称材料

“伸展树——一种高效的索引树”教学设计

14

作者 张铭 《计算机教育》 2013年第17期8-10,共3页

数据结构设计的重要目标之一是提高操作速度,特别是检索速度。局部平衡的红黑树、平衡的AVL树等二叉搜索树具有良好的检索性能,非常适合于基于内存的索引,但为防止树形结构退化为线性结构,在插入和删除结点时经常需要旋转,维护数据结构... 数据结构设计的重要目标之一是提高操作速度,特别是检索速度。局部平衡的红黑树、平衡的AVL树等二叉搜索树具有良好的检索性能,非常适合于基于内存的索引,但为防止树形结构退化为线性结构,在插入和删除结点时经常需要旋转,维护数据结构的操作比较复杂。文章阐述伸展树在检索过程中通过自动调整结构,使访问最频繁的结点靠近树结构的根,从而减少访问代价,指出伸展树可以作为各种线性序列的索引组织方法,能在一些需要高效索引的大工程中加以运用。 展开更多

关键词 数据结构 索引 二叉搜索树 伸展树

在线阅读 下载PDF 职称材料

EMPC中基于混合树型结构的点定位算法

15

作者 修晓杰 《杭州电子科技大学学报（自然科学版）》 2019年第3期65-72,共8页

针对显式模型预测控制中点定位问题,提出一种基于多维查找树的混合树型结构,树型结构分为"树干"、"树梢"和"叶子"三部分。"树干"部分以轴对准超平面作为划分超平面,使用分段仿射控制率数量作... 针对显式模型预测控制中点定位问题,提出一种基于多维查找树的混合树型结构,树型结构分为"树干"、"树梢"和"叶子"三部分。"树干"部分以轴对准超平面作为划分超平面,使用分段仿射控制率数量作为计算准则;"树梢"部分以边界超平面作为划分超平面,使用二叉搜索树结构,并通过划分阈值,限制二叉搜索树的高度;混合树型结构非叶子节点保存划分超平面信息,叶子节点保存分段仿射控制率信息。实验结果表明:算法能有效减少存储需求,提高在线查找效率,并能很好地协调预处理、在线计算和存储需求之间的关系。 展开更多

关键词 显式模型预测控制 K-D树 二叉搜索树 混合树型结构 分段仿射控制率

在线阅读 下载PDF 职称材料

基于节点兴趣非结构化P2P网络搜索机制研究

16

作者 庄伟 《计算机技术与发展》 2018年第5期68-72,共5页

随着网络用户以及网络资源的增长,P2P网络,一种在对等者(peer)之间分配任务和工作负载的分布式应用架构,引起了广泛关注。由于具有较好的可用性、可扩展性,非结构化P2P网络成为P2P网络研究的热点。现今对于非结构化P2P网络资源搜索算法... 随着网络用户以及网络资源的增长,P2P网络,一种在对等者(peer)之间分配任务和工作负载的分布式应用架构,引起了广泛关注。由于具有较好的可用性、可扩展性,非结构化P2P网络成为P2P网络研究的热点。现今对于非结构化P2P网络资源搜索算法的研究主要是在洪泛算法的基础上进行一定的改进,但这些算法存在明显的问题:一是算法在搜索过程中有一定的盲目性,搜索效率不高;二是搜索过程中会向所有邻居节点发送消息从而产生大量的冗余消息,易造成网络阻塞。针对上述问题,提出一种基于节点兴趣的非结构化P2P覆盖网络拓扑结构,在相似度较高的节点之间建立二叉搜索树来降低查询消息转发的盲目性并提高搜索效率。仿真结果表明,与传统的洪泛算法相比,提出的非结构化P2P网络搜索机制查询时间更短,查询消息量更少,搜索效率更高。 展开更多

关键词 P2P网络 拓扑结构 兴趣相似度 二叉搜索树

在线阅读 下载PDF 职称材料

八字树

17

作者 Clark,D 李淑兰 《微型计算机》 北大核心 1995年第2期79-81,共3页

关键词 八字树 数据结构 二叉搜索树

在线阅读 下载PDF 职称材料

LLRB算法的函数式建模及其机械化验证

18

作者 左正康 黄志鹏 +4 位作者 黄箐 孙欢 曾志城 胡颖 王昌晶 《软件学报》 EI CSCD 北大核心 2024年第11期5016-5039,共24页

基于机器定理证明的形式化验证技术不受状态空间限制,是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法.LLRB(left-leaning red-black trees)是一种二叉搜索树变体,其结构比传统的红黑树添加了额外的左倾约束条件,在验证时... 基于机器定理证明的形式化验证技术不受状态空间限制,是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法.LLRB(left-leaning red-black trees)是一种二叉搜索树变体,其结构比传统的红黑树添加了额外的左倾约束条件,在验证时无法使用常规的证明策略,需要更多的人工干预和努力,其正确性验证是一个公认的难题.为此,基于二叉搜索树类算法Isabelle验证框架,对其附加性质部分进行细化,并给出具体化的验证方案.在Isabelle中对LLRB插入和删除操作进行函数式建模,对其不变量进行模块化处理,并验证函数的正确性.这是首次在Isabelle中对函数式LLRB插入和删除算法进行机械化验证,相较于目前LLRB算法的Dafny验证,定理数由158减少至84,且无需构造中间断言,减轻了验证的负担;同时,为复杂树结构算法的函数式建模及验证提供了一定的参考价值. 展开更多

关键词 LLRB 函数式建模 机械化验证 Isabelle定理证明器 二叉搜索树

在线阅读 下载PDF 职称材料

集装箱船全航线预配优化模型与算法研究 被引量：6

19

作者 张维英 林焰 +2 位作者 纪卓尚 孙文志 余报楚 《大连理工大学学报》 EI CAS CSCD 北大核心 2008年第5期673-678,共6页

集装箱船全航线配载问题属于NP-hard问题.为降低问题求解难度,提出了解决全航线配载问题的分解算法,即将配载问题分解为Bay位选择和Bay位中集装箱排序两个子问题.将Bay位选择看成是"装箱问题",以不同属性集装箱作为待装"... 集装箱船全航线配载问题属于NP-hard问题.为降低问题求解难度,提出了解决全航线配载问题的分解算法,即将配载问题分解为Bay位选择和Bay位中集装箱排序两个子问题.将Bay位选择看成是"装箱问题",以不同属性集装箱作为待装"物品",以船舶上的Bay位为箱子,以最优装箱(即使用箱子的数量最少)及集装箱在每个港口的倒箱数量最少为目标进行总布置配载;Bay位中集装箱排序是将Bay位选择阶段分配到不同Bay位的集装箱按某些规则进行排序,确定其在Bay位中的具体箱位.主要研究了Bay位选择阶段的模型及算法.实例模拟结果表明该方法可行,为集装箱船全航线配载优化提供了一个实用的模型. 展开更多

关键词 集装箱船 预配 装箱算法 二叉搜索树 全航线

在线阅读 下载PDF 职称材料

基于改进NSGA-Ⅱ的仿人机器人上楼梯运动规划方法

20

作者 许宪东 关毅 +3 位作者 洪炳镕 朴松昊 钟秋波 蔡则苏 《高技术通讯》 CAS CSCD 北大核心 2014年第9期982-990,共9页

针对当前仿人机器人运动优化算法多采用对能耗、稳定性及速度等单目标优化而存在一定的局限性的问题,提出了一种基于多目标优化的仿人机器人上楼梯运动优化方法。针对NSGA-Ⅱ——经典的带精英策略的非支配排序遗传算法(NSGA)的快速非支... 针对当前仿人机器人运动优化算法多采用对能耗、稳定性及速度等单目标优化而存在一定的局限性的问题,提出了一种基于多目标优化的仿人机器人上楼梯运动优化方法。针对NSGA-Ⅱ——经典的带精英策略的非支配排序遗传算法(NSGA)的快速非支配排序效率较低的问题,提出了一种基于自调整二叉搜索树的改进NSGA-Ⅱ方法,并采用改进的NSGA-Ⅱ算法实现了仿人机器人上楼梯运动参数优化。通过仿真和实际实验对比了优化前后仿人机器人的能耗和稳定性。实验表明,采用这种方法能克服单目标优化的缺点,在同时满足多个目标需求的同时有效地实现仿人机器人上楼梯。 展开更多

关键词 仿人机器人 多目标优化 带精英策略的非支配排序遗传算法(NSGA—Ⅱ) 自调 整二叉搜索树

在线阅读 下载PDF 职称材料