一种新的删除HB(κ)树的结点的算法

Foster的删除HB(κ)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退.提出一种新的删除HB(κ)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.举例说明新算法的执行过程.证明新算法是正确的.与Foster的删除HB(κ)树的结点的算法相比,新算法不涉及辅助栈的使用.设n是HB(κ)树的结点的个数.新算法的时间复杂性是0(log2n),与Foster的删除HB(κ)树的结点的算法的相同.实验结果表明新算法的平均执行对间比Foster的删除HB(κ)树的结点的算法短.新算法的空间复杂性是O(1),比Foster的删除HB(κ)树的结点的算法低.     

一种新的删除AVL树的结点的算法

所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。     

一种新的删除AA-树结点的算法

Andersson的删除AA-树结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AA-树结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Andersson的算法相比,新算法不涉及辅助栈的使用。设n是AA-树的内部结点的个数,执行新算法时进行O（lbn）次旋转,新算法的时间复杂性是O（lbn）,与Andersson的算法的时间复杂性相同。实验结果表明新算法的平均执行时间比Andersson的算法的平均执行时间短。新算法的空间复杂性是O（1）,比Andersson的算法的空间复杂性低。     

一种新的删除红黑树的结点的算法

提出一种新的删除红黑树的结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。     

CMST问题的新算法

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N~2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.     

一种自适应二级散列算法

计算机70%以上的时间在进行查找工作。传统散列算法[1]具有很好的平均时间复杂性,但最坏时间复杂性为O(k),(k为关键字总数)。完美散列算法查找的时间复杂性一般较小,但插入后解决冲突的最坏时间复杂性均在O(k2)以上。本文结合完美散列算法gperf[2],传统散列算法、平衡树[1]等的优点,提出一种自适应二级散列算法,其查找、插入和删除的最坏时间复杂性远低于O(log2k),接近常数,其最坏空间复杂性为O(k).     

求有向图必经结点的一个有效算法

本文给出在任意有向图中求必经结点的一个算法,以及对应的BASIC语言写的程序。算法使用了深度优先搜索、脱机最小值算法、不相交集的合并算法,以及能体现优先队列功能的2—3树算法,从而使算法的时间复杂性最多为O(nlogn e),空间复杂性最多为O(e),n,e分别为图的结点数和边数。当e≥nlogn时,本算法时间复杂性为O(e),它在一个常数范围内是最优的。     

二个关于平衡树的结点删除算法

本文提出了二个关于平衡树的更好的结点删除算法,它们的主要优点是降低了算法的空间复杂性,这是通过在算法中间过程中改变结点的指针实现的。     

时空最优的AVL树删除算法

本文给出了在AVL树中删除一指定结点的完整算法及一具体例子,分析了算法的复杂度。该算法的时间、空间复杂度分别为O(logn)和O(1),它在时间上和空间上都是最优的。     

最短路径算法的新分析

本文给出了求解最短路径问题的Ford算法的新分析,证明了该算法的时间复杂性为O((d+2)r),这比以前的上界O(nr)要好,并且是最优的,其中n、r分别是有向图中的结点数和边数,d是图中任何以某一初始结点开始的简单路径中的最大向后边数。     

An effective data collection algorithm for wireless sensor network

This paper proposes an effective subtree merging based data collection algorithm for wireless sensor networks (WSNs), named as SMDC algorithm, which can be applied in a new kind of applications in WSNs, i.e., area query application. The SMDC algorithm can prevent unnecessary energy consumption in ancestor nodes for routing through the union of disjoint sets for different subtrees in the network. The SMDC algorithm includes four phases. Firstly the cluster trees are constructed respectively in the target area. Then the disjoint node sets for each subtrees will be found; thirdly the disjoint subtrees are connected via the closest node between two subtrees; and the last phase is to disconnect the subtrees which have been connected to a new tree branch from their previous tree structure. This paper also presents the simulation to compare the SMDC algorithm with some related works including conventional minimum spanning tree algorithm. Simulation results show that the SMDC algorithm can reduce the redundant energy consumption and the number of hops which results in the reduction of total energy consumption. Especially, it is more efficient as the number of sensor nodes in a target area increases.     

Embedding and reconfiguration of spanning trees in faultyhypercubes

The problem of tolerating faulty nodes in hypercubes has been studied by many researchers either by using spares or by reconfiguration. Algorithms for tolerating faulty nodes and links in hypercubes are presented. The algorithms are based on using general spanning trees (GST), complete unbalanced spanning trees (CUST), and balanced spanning trees (BST) for reconfiguring the hypercube to avoid faulty nodes and links. The algorithms contain two phases: the first phase involves the construction of the spanning tree and the second one is for reconfiguring the hypercube should a faulty node be detected. The reconfiguration process consists of two basic steps. First, the faulty node is disconnected from the spanning tree. Then, a new spanning tree is constructed by reconnecting the children of the faulty node to the spanning tree. One hundred percent single fault correction (avoidance) and almost 100 percent fault correction (avoidance) of double and triple faults are achieved by the proposed algorithms for hypercubes having a dimension of n⩾6. Simulation results for the algorithm under more than three faults also are presented. For any k faulty nodes (1⩽k⩽2ⁿ-1), the reconfiguration algorithm may be applied k times to avoid these k faulty nodes as long as no combination of any two of the faults results in a blocking situation. The proposed reconfiguration algorithms tolerate all possible single-link faults. The reconfiguration algorithms are extended to tolerate (k⩽n-1) multiple faults, causing blocking situation, with a backtracking     

Drawing dynamic trees

A tree-drawing algorithm that addresses the weaknesses of current approaches to constructing graphical user interfaces is presented. Present algorithms either do not let you draw tree nodes of varying shapes and sizes or they draw such trees in a way that does not produce trees as compact as they could be, which is especially important when diagramming a large system. Also, they cannot reuse layout information when the trees changes, so after every change the layout must be recomputed and the tree redrawn. The main difference between these traditional approaches and the author's approach is that his algorithm is more geometric. Unlike other algorithms, it uses an explicit representation of node and subtree contours, and it stores every contour as a polygon. It has three advantages over traditional algorithms. It allows one to draw trees with nodes of any polygonal shape compactly. The data structure supports insert and delete operations on subtrees. It is simple to implement, yet flexible     

Minimum Cost Partitions of Trees with Supply and Demand

Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every demand vertex v of T must be supplied an amount of ??power,?? equal to the demand of v, from exactly one supply vertex through edges in T. Each edge e of T has a direction, and is assigned a positive integer which represents the cost required to delete e from T or reverse the direction of e. Then one wishes to obtain subtrees of T by deleting edges or reversing the directions of edges so that (a)?each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and (b)?every edge is directed away from the supply vertex in each subtree. One wishes to minimize the total cost to obtain such subtrees from T. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem.     

Algorithms for constructing minimal deduction graphs

Two algorithms for constructing minimal deduction graphs (MDG) for inferring rules and facts in an extended version of the Horn clause logic are described. A deduction graph (DG) is minimal if the number of arcs in the graph is minimized. Horn clauses (HC) are extended to Horn formulas (HF), such that the head or the body of an HF can be a conjunction of positive literals or a disjunction of the bodies of some rule instances, respectively. Each algorithm constructs an MDG from its source to its sink, whose arcs infer the HF `if source then sink'. The construction of an MDG is based on a sound and complete set of inference rules of reflexivity, transitivity, and conjunction for HFs which proceeds by expanding a tree rooted at its sink until its source has a successful backtracking to the root. Then the MDG is extracted from the tree. The nodes being expanded in such a tree are classified into seven types, which are assigned by different priorities for their growing into subtrees or for their pruning to reduce the tree space     

结合用户兴趣的微博信息传播模式挖掘*

由于信息传播模型是社区挖掘、社区影响力研究的基础,文中提出结合用户兴趣的信息传播模型,设计基于频繁子树的信息传播微观模式挖掘方法.首先,基于微博社交网络图表示及用户多标签建模,将微观信息传播模式转换为频繁子树挖掘问题.然后,针对微博社交网络图单节点多标签特性,设计多标签节点树的频繁子树挖掘算法(MLTreeMiner).最后,结合主题提取方法,使用MLTreeMiner挖掘信息传播模式.在人工数据集上的实验表明,MLtreeMiner能高效地对多标签节点树进行频繁子树挖掘.针对新浪微博真实数据的实验也验证方法的有效性.     

基于动态状态树的回溯算法

介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.