一种平衡树的研究之四

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

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

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

红黑树在Linux虚拟内存区域管理中的应用

本文介绍了红黑树在Linux内核下的应用,主要讨论了红黑树在Linux内核中对虚拟内存区域管理的实现。Linux内核中,虚拟内存区域的起始地址存储在红黑树的节点中,红黑树的高效操作使虚拟内存区域的删除、查找和插入的时间复杂度为O(logn)。     

一种基于红黑树的快速查找列表结构

设计并实现了一种基于红黑树的列表结构. 列表中数据存储在红黑树节点中,红黑树的高效查找性能使列表的查找时间复杂度为O(logn). 实验表明,其查找效率比遍历查找快2个数量级以上,与二分查找相当. 该列表结构适合于各种频繁添加、删除、查找的应用.     

红黑树的高度

先证明高度是h的准红黑树至少有2「2h﹁ 2﹂2h」-2个结点.再证明有n个结点的准红黑树的高度至多是2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-o1g2(n 2)」」-2.最后证明有n个结点的红黑树的高度至多是2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-og12(n 2)」」-2,该式比原来的2﹂log2(n 1)」 1准确.有n个结点的红黑树的高度在﹂log2(n 1)」和2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-og12(n 2)」」-2之间.此文进一步完善了红黑树的性质.     

一种有效的丰满树算法

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

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

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

基于改进爬山算法的Bayesian网结构增量学习方法

已建成的贝叶斯网与领域环境间可能存在较大偏差,加之领域本身固有的动态变化特征,因此在观察到新数据时,改善贝叶斯网的性能和优化网络结构是十分必要的.对传统爬山算法进行研究并改进Gamez等提出的爬山算法,该算法通过引入删除结点时的禁忌表和环路禁忌表,避免搜索不必要的冗余结点,提高搜索效率,并给出禁忌表的更新方法.在ALARM数据集上进行实验,结果表明该算法是有效的.     

一种基于DHP的动态链地址关联规则挖掘算法

采用动态链地址法建立Hk 表,提出DLDHP算法,克服DHP算法不能给Ck 中的每个项集单独计数的缺点,在增加Hk 表的空间时也会删除链表中的结点空间,从而Hk 表不会占用较大的内存,最终直接由Hk 表得到频繁k-项集的集合Lk ,不用再次扫描数据库。实验结果表明:DLDHP算法是有效可行的。     

动态分布式层次密钥管理

层次秘密通信在电子商务与电子政务以及其他的具有层次结构的系统中有广泛的应用,本文通过利用单向散列函数的不可逆计算的特性,设计了一个单向的等级加密体制的密钥管理方案,上级组结点可以安全容易的获取下级组结点的密钥,反之不然.并且在方案中实现安全组的动态添加、删除及更新组结点密钥.本方案计算量小、存贮要求低,并且可以实现分布式并行化计算.     

一种带红黑树的哈希表在物流信息系统中的应用研究

针对在节假期间物流业务量急剧增长及大量用户在线查询订单信息而导致物流信息系统响应速度慢的问题,提出了带红黑树的哈希表,有效地提高了订单查询的速度,并将链表和红黑树进行比较,实验结果表明:带红黑树的哈希表在查找时间上有明显优势.     

基于消息的加权负载均衡算法

在研究EAP协议与Diameter协议的基础上,为解决分布式认证系统节点间会话一致性的问题,以及尽可能减少服务节点数量改变时产生的会话迁移数量,提出了一种基于消息的加权负载均衡算法(MOLB)。该算法使用散列法、虚拟节点和红黑树相结合的技术,实现了客户端请求在服务节点间的合理分布。Diameter网络环境中的实验结果表明:与其他常用的负载均衡算法相比,本文算法具有较小的负载均衡度和会话破坏度以及较低的会话破坏分布度。     

频域约束的红-黑小波变换图像复原算法

提出一种频域约束的红-黑小波变换图像复原新算法.该算法引入频域约束因子,对不同频率的部分系数给予不同程度的约束,保证了对有色噪声的压制效果,保留了图像细节信息.利用频域约束的红-黑小波变换提取图像信息,消除了有色噪声和振铃效应,实现了降质图像复原.运用含噪退化的图像进行了实验.结果表明,该方法与维纳滤波、等功率谱方法相比,信噪比RSN及信噪比提高R′SN两个参数均提高了3倍.     

P2P网络通信树群发算法研究

深入分析P2P通信规则,以并发通信时间最短为目标,提出了一种新型的群发通信树构建算法——“困难节点”优先通信树算法.对比支路优先试加节点通信树算法,更加合理的布局各个节点在通信树中的位置,模拟结果表明,“困难节点”优先通信树算法的通信效率优于支路优先试加节点通信树算法.     

一类度约束最小生成树问题的Dijkstra算法

度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。     

—种改进型的B＋树在文件管理中的应用

文件管理是操作系统和数据库的重要组成部分,B-树和B＋树在这方面有着重要的应用,但并不总适合海量数据的访问尤其在大型数据库中,因此希望改进B＋树。首先制定叶子节点和目录节点的文件个数的调整规则,以达到较好的平衡;然后选择恰当的叶子节点中的文件个数m和目录节点中的目录项数n,使文件访问时间最少;最后实验证明较之简单使用B＋树作为文件管理的算法具有良好的性能。为解决大型数据的文件管理提供了新的思路。     

一种新的模糊决策树算法 ——基于加权毕达哥拉斯模糊熵

传统的模糊决策树虽然可以从模糊数据中抽取模糊分类规则,但只能获取节点的隶属度信息,无法得出样本数据对于节点的非隶属度和犹豫度信息,导致数据分类的准确率不高。针对此,基于毕达哥拉斯模糊集理论,提出了一种新的加权毕达哥拉斯模糊决策树算法（Weighted Pythagorean Fuzzy Decision Tree,WPFDT）。首先,通过改进的K-means聚类算法得到连续属性数据的聚类中心,并结合三角模糊数对连续数据进行模糊处理;其次,定义并计算每一个属性的加权毕达哥拉斯模糊熵,选择加权毕达哥拉斯模糊熵最小的属性作为决策树根节点,在根节点下递归选择模糊熵最小的属性作为分裂节点,同时通过阈值控制树的规模,得到从根节点到叶子节点路径的模糊规则以及模糊规则的隶属度、非隶属度以及犹豫度,并完成预测分类,直至生成WPFDT模型;最后,选取UCI上的3个医学数据集（Haberman、Breast Cancer、Parkinson）进行实验,在分类准确率和得出模糊规则的数量与3种传统决策树算法（模糊ID3算法、C4.5算法、CART算法）比较,实验结果表明：WPFDT在分类精度和树大小上都优于其他传统决策树算法,并且有较高的召回率和精确率。     

基于Rough集的决策树算法

针对基于Rough集的经典分类算法值约简算法等不适合大数据集的问题，提出了基于Rough集的决策树算法。采用一个新的选择属性的测度——属性分类粗糙度作为选择属性的启发式，该测度较Rough中刻画属性相关性的测度正区域等更为全面地刻画了属性分类综合贡献能力，并且比信息增益和信息增益率的计算更为简单。采取了一种新的剪枝方法——预剪枝，即在选择属性计算前基于变精度正区域修正属性对数据的初始划分模式，以更有效地消除噪音数据对选择属性和生成叶节点的影响．采取了一种与决策树算法高度融合的简单有效的检测和处理不相容数据的方法，从而使算法对相容和不相容数据都能进行有效处理。对UCI机器学习数据库中几个数据集的挖掘结果表明，该算法生成的决策树较ID3算法小，与用信息增益率作为启发式的决策树算法生成的决策树规模相当。算法生成所有叶节点均满足给定最小置信度和支持度的决策树或分类规则，并易于利用数据库技术实现，适合大数据集。     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.     

基于基因结构树模型的红外图像分割研究

针对红外图像分割的特点,采用基因结构树模型。首先通过由根节点至节点顺序累加获取属性为结构树模型的生长代价;接着判决规则为结构树分支节点距离计算,借助分支节点之间的夹角表示,夹角越小,则分支节点距离越小;最后从基因树中选择其中似然值最大的作为最优树,给出了算法流程。实验仿真结果显示算法对红外图像分割很好地保留目标区域,有较为简洁平滑的边缘,分割质量评价的定量结果优。