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

平衡二叉查找树是计算机中有效地组织大规模查找数据的主要手段,因为在树的创建、节点的插入、删除过程中都维持了树的平衡.AVL树是平衡二叉查找树,但是AVL树在创建、插入、删除时维护树的平衡操作需要按照平衡因子的不同情况分别进行处理,程序长,实现过程繁杂.本文利用树的高度提出一种新的AVL平衡树数学描述-高度平衡树(HAV...     

查找重叠于某点所有区间的一种数据结构

快速查找重叠于某点的所有区间集是计算机图形学、模式匹配及其他应用中急需解决的问题之一.通过介绍了一种用于查找所有重叠于某个特殊点的区间的数据结构区间空指令表,这种数据结构与AVL树具有相似的功能与特性,但执行起来比AVL树简单得多,它能够实现快速查找重叠于某点的所有区间集.搜索包含n个区间的空指令表以寻找重叠于一个点的区间约需时间为O(logn+L),L代表匹配区间的数目,插入或删除一个区间所需时间为O(log2n).图1,参5.     

应用二度正则双图求解二度排列的计数问题

一、引言 n个科研课题,分配给n个科学家进行研究,要求每个科学家恰承担其中两个课题,并且每个课题恰有两个科学家进行研究,问有多少种分配方案了由此类问题,我们可以引出如下的数学模型。 n个不同的元素,每个元素允许重复一次,将它们排到n个不同的位置,使得每个元素恰排在两个不同的位置,并且每个位置上恰排两个不同元素,称其为n个元素的二度排列,奇称(n,2)排列,所有不同的(n,2)排列的种数记为Tn。     

一种特殊的排列问题

先看到两个例子：1、某人分别写了3封不同的信和相应的3个信封，结果把信全部装错了信封，有多少种装法。2、有编号分别为1、2、3、4、5的个人分别坐在编号分别为1、2、3、4、5的个座位上，要求人的编号与座位号不能相同有多少种坐法。以上两个例子实际问题不同，但共抽象的排列意义是相同的，我们把它抽象为：有n个(n≥2)编号分别出心裁1、2……n的n个元素，排在编号码1、2……n的n的位置上（每个位置一个元素），要求元素号与位置号不相同有多少种排列法，这种排列属于一种有限制的排列问题，且有多少元素就有多少限制，当n比较小时可实排…     

全错位排列数公式的某些应用

考虑一个随机试验。假设把n个元素a_1,a_2,……,a_n随机地排到第1号,2号,……n号位置上去(一个位置上放一个元素)。如果每个元素a_i均不在第i号位置(i=1,2,……n),则称此排列是这n个元素的全错位排列,所有这种排列的个数叫做这n个元素的全错位排列数,记作Q_n。 显然,Q_1=0,Q_2=1,Q_3=2一般地,有人证明了(见[1],)对一切不小于2的自然数n,Q_n=n![1/2!-1/3!+…+((-1)~n)/n!] (1) 这是欧拉等人研究过的“错放信笺问题”的一劳永逸的答案。     

浅谈一种扩展的数据结构——跳表

跳表(SkipList)可以被看为是二叉树(BinaryTree)的一种替代品。这种扩展的数据结构采用了概率算法以维持树的平衡。该算法对跳表来说非常简单而且也非常快速。这使跳表相对其它数据结构有更多的吸引力。在这篇文章里,笔者将对跳表的结构和基于跳表结构的查找、插入、删除的算法进行讨论。     

概率古典定义教学探导

随着概率应用日益广泛 ,概率论在中学数学教学中愈来愈显示出其重要性 ,而古典概率又是中学概率论教学的重中之重。因此 ,引导学生深刻理解古典概率的定义 ,正确而又灵活地运用古典概型 ,是全面提高概率教学质量的重要保证 ,笔者就学生在学习古典概率时常出现的一些问题 ,谈谈教学的一点肤浅体会。一、深刻理解定义对于古典概率 ,在我们使用的课本《全日制普通高中教科书 (试验本 )数学第二册 (下 A)》中是这样定义的 :如果一次试验中可能出现的结果有 n个 ,而且所有结果出现的可能性都相等 ,那么每一个结果的概率都是 1n,如果某个事件 A包…     

一类树问题的快速并行算法

本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.     

关于Banach火柴盒问题解的讨论

某数学家随身携带两盒火柴,当他要用火柴时,随意从其中的一盒中取出一根,假定开始时两个火柴盒中各都有 n 根火柴,试问在某一次该数学家发现拿出的那盒火柴已经空时,另一盒中恰有 r 根(0≤r≤n)的概率是多少?这是著名的 Banach 火柴问题。目前许多的大学概率论教科书中都引述或变相引述了这     

可重复全排列的公式生成法

众所周知,关于排列的生成问题是组合论中的重要内容之一。在某些实际问题中,譬如在计算机的算法,有时需要按照一定的法则逐次产生n！个排列。迄今为止,已有许多种生成全部排列的算法,其中有由Johson与Trotter提出的有效的算法,在这一算法中,后一排列可以由前一排列中交换两个相邻元的位置得出;以后,Aзатян对这方法进行了化简。本文讨论可重复(不尽相异)全排列的生成算法,得到了以明显公式的生成算法,以不重复全排列为其特例。这一结果,我们在研究线性偏微分方程(组)柯西问题解析解的新的表示形式时有着重要的应用。     

赛程安排的数学模型

针对题目提出的问题,即怎样编制出一个合理、公平的赛程安排及各队每两场比赛中间相隔的场次数的上限问题,作了详尽、细致、深入的分析,在分析过程中,我们针对参赛球队的个数n可为奇数也可为偶数的情况下,分别用"最优配对排列法"和"循环滚动法"这两种不同的方法来解决,当n为奇数时,用"最优配对排列法"编制赛程;n为偶数时,用"循环滚动法"编制赛程.所谓"最优配对排列法"就是先按顺序给球队两两赋值并找出数值最小且遵循"距离最远、所打场数最少、无相同数值出现"原则的两支球队进行配对并又赋予新的值,再寻找数值最小的两个队进行配对,以此推出,就可以编制最优赛程;而"循环滚动法"就是把球队按顺序编号后分为左、右各一半,然后左一半按序号依次往下排列,右边紧接左边序号由下向上排列,再固定左上角的球队,其它球队按逆时针(或顺时针)方向滚动,从而得出最优赛程.当n为奇数时,我们利用算法语言编制出了一套程序,这样就可以解决n为较大值时,人工无法列出赛程表问题.文中我们利用这两种方法对n的值按顺序进行举例归纳,以表格的形式建立出最优的数学模型,总结出在尽量公平的情况下各队每两场比赛中间相隔的场次的上限值α＝[n/2].     

通讯网络中一类连通性问题研究

考虑通信网络中一类连通性问题.假设某地区面积为S,均匀随机分有n个网站,任意两个网站之间距离小于r(n)时,这两个网站之间可以直接通信,得到的结果是r(n)满足条件πr2(n)=logn+c(n)/nS时,该通信网络随c(n)→+∞以概率1连通.     

关于Dewdney对(m,n)树的两个猜想

1974年Dewdney提出了n维复形上的(m,n)树的概念和关于(m,n)树的两个猜想。本文解决了这两个猜想。指出它们是不成立的,同时证明了纯粹复形是(m,n)树的一个充要条件(定理1)。它的充分条件是不能再减弱的。解决上述问题的方法是引进复形K上的(m,n)关联二分图Ka_ma_n和利用两个定理及其推论。一个定理讨论了K的(m,n)连通与Ka_ma_n的连通的关系;另一个讨论了K中无(m,n)圈与Ka_ma_n无圈的关系。     

关于Sylvester问题的n维Hostinsky公式

1925年Hostinsky得到了关于Sylvester问题的3维Hostinsky公式。在n维欧氏空间的一个凸体内独立随机地取n+2个点,这n+2个点形成凹多面体的概率是多少,这就是n维Sylvester问题,本文将得到n维的Hostinsky公式。引理1 n-1维欧氏空间的n个点(?)_1(x_1~(1),…,x_(n-1)~(1),),……,(?)_n(x_1~(1),…,x_(n-1)~(n))所成多面体的体积是     

关于Sylvester问题的n维Hostinsky公式

1925年Hostinsky得到了关于Sylvester问题的3维Hostinsky公式。在n维欧氏空间的一个凸体内独立随机地取n 2个点,这n 2个点形成凹多面体的概率是多少,这就是n维Sylvester问题,本文将得到n维的Hostinsky公式。引理1 n-1维欧氏空间的n个点Q_1(x_1~(1),…,x_(n-1)~(1)),……,Q_n(x_1~(1),…,x_(n-1)~(1))所成多面体的体积是     

基于AVL树的平衡维护研究

本文提出了AVL树的平衡调整简单算法。通过理论分析,表明该算法具有理想的运算效率。与传统的调整方法比较,该算法简单易行、容易理解、形式规范,因此,无论用于教学还是解决实际问题,都有较大的实用价值。     

组合恒等式的概率证明

用概率证明组合恒等式的主要思路是:针对所要证明的组合恒等式构造出适当的概率模型,求出该模型中有关事件的概率,然后根据概率的一些性质,推出应有的结论.例1 证明 C_(n 1)~k=C_n~k C_n~(k-1) (1)证明对(1)作恒等变形,得C_n~k/C_(n 1)~k C_n~(k-1)/C_(n 1)~k=1 (2)现在我们利用对立事件和的性质,构造一个概率模型:一批产品共 n 1个,待批发出厂.若已知其中混入一个废品,现在从中随机地抽取 k 个产品出来(1≤k≤n 1),问抽到废品的概率是多少?抽出     

平衡树的插入和删去算法

处理平衡树一般使用Adelson方法。本文想修改这个方法,以尽可能避免多余的平衡处理动作。例如依次把内容为3、2、1、4、5的五个结点插入空树,按原方法要两次平衡处理(图1(a)),而用修改方法则不必作平衡处理(图1(b))。     

关于树的第二个最大特征值

令T(n,i)表示顶点数为n,且匹配数为i的所有树的集合,研究了T(4n-1,2n-1)中哪些树的第二个最大特征值等于√1/2[n+1+√(n+1)2-8]的一个猜想.此外,还进一步得到了T(4n-1,2n-1)中树的第二个最大特征值的3个新的上界,并且确定了达到上界的所有的树.     

行列式的公理化定义

给定域F上的n阶方阵A=(a_(ij)),A的行列式的通常定义是定义1 |A|=sum from σ(sgnσ)a_(1,j1)a_(2,j2)…a_(n,jn) (1) 这里sum from σ是对所有n阶排列σ=j_1 j_2…j_n求和,符号 sgnσ={1,当σ为偶排列时,-1,当σ为奇排列时。 由(1)可推出许多众所周知的行列式性质,我们能否从中筛选出最本质的几条,来建立行列式的理论?这实际上是涉及行列式定义的公理化问题。在教学中提出并解决这个问题,对培养学生的数学素质、开拓智力是有作用的。