对广义平衡二叉树的检索时间分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇对广义平衡二叉树的检索时间分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

(1.湖南师范大学 校园网络中心,湖南 长沙 410006;2.湖南师范大学 数学与计算机学院,湖南 长沙 410006;3.湖南师范大学 计算机教学部,湖南 长沙 410006)

摘要:根据广义平衡二叉树的特性,针对其检索性能采用理论推算证明的方式进行分析,得到检索时间上限的一个表达式,从而用理论的方式,将广义平衡二叉树检索性能降低的部分限制在一个较小的范围内。

关键词:广义平衡二叉树;高度平衡二叉树;平衡二叉树;检索时间

中图分类号:TP301文献标识码:A文章编号:1009-3044(2009)28-7963-03

Retrieval Time Analysis of General Balanced Trees

CHEN Zhi-xin1, JIA Bo2, TANG Wen-sheng3

(1.Information and Network Center, Hunan Normal University, Changsha 410006, China; 2.College of Mathematics and Computer Sciences, Hunan Normal University,Changsha 410006, China; 3.Department of Computer Education, Hunan Normal University, Changsha 410006, China)

Abstract: According to the property of general balanced trees, analysis the retrieval ability of it by theoretical proof, and makes an expression of upper limit of retrieval time. So limit the reduce rate of retrieval ability into a small area by theoretical method.

Key words: general balanced trees; height-balanced trees; AVL trees; retrieval time

二叉搜索树(BST)作为一种重要的数据结构被广泛的应用,但是由于其形态受到节点插入顺序的影响,深度从log n到n不等,故其检索时间(Retrieval Time)为也在这个范围内,并且有最坏检索时间(Worst Retrieval Time)为n。因此,Adelson-Velskii和Landis在1962年即提出了平衡二叉树(AVL Tree)结构,将对BST的最坏检索时间控制在log n级别,使得对它的检索操作变得稳定且高效,是它作为搜索树结构的优势所在。但是由于维持平衡所需的旋转操作消耗较大,使得在对索引修改频繁的应用中性能较低。Caxton C. Foster(University of Massachusetts)曾在1972年的文章中提出过对平衡二叉树结构的推广,后被称作广义平衡二叉树(高度平衡二叉树,Height balanced tree)并进行了系列的研究。本文在这些基础上针对广义平衡二叉树的检索性能,采用理论证明的方式进行分析,从而得到了更为适用的结果。

平衡二叉树之所以能保证检索的高速和稳定,是因为其平衡的特性,但是这一特性也额外的增加了增删节点时的操作开销,即维持平衡的开销。维持平衡一般采用旋转算法,其时间复杂度也是O(log n)。但是旋转操作并不是每次都需要的,比如当两次删除操作导致某子树的左右子树深度各减少1时,不会发生失衡,也无需进行旋转操作;由此可断言,如果将包含n个节点的AVL Tree的所有形态视为一个集合,假定对其中任意节点的操作频率以及操作方式(增加或删除)是一样的,那么这所有操作中引起失衡的概率是一个常数,而这一常数影响着应用系统的整体性能。

Caxton C. Foster提出的对AVL Tree的一种推广结构,他允许BST的平衡因子被放大到一个较大的正整数范围,降低由于结构变更导致失衡的概率,从而达到提升整体性能的目的。P.L. Karlton与S.H. Fuller等人也在这方面做了一定的研究。与他们主要依赖实验的研究方式不同,本文采用论证的方式分析了这种结构的在检索时的性质。

1 基本概念

高度平衡二叉树(Height balanced tree)的定义由Foster提出,我们描述如下。

定义1:给定整数N,则二叉搜索树HB(N)是容差为N的高度平衡二叉树,当且仅当满足以下条件:

1) T(N)的左子树和右子树的深度差(平衡因子,imbalances)的绝对值|Dleft-Dright|≤N。

2) 任意子树均是容差为N的次平衡二叉树。

由定义不难看出,如果把其中的N替换成1,就成了AVL Tree的定义。事实上,根据这一定义有如下推论:

推论1:HB(0)是满树。显然,所有子树的左右子树完全一致,必然是满树,这是BST最严格的形式,其最坏检索时间就是log n。

推论2:HB(1)是AVL Tree。

推论3:如果一棵二叉搜索树是HB(m),且有m

从定义我们可以可得,N越大时, HB(N)的最坏检索时间越大,对HB(N)的检索费时也越不稳定,但是失衡的概率会越小。在一定的容量(包含一定节点数)以及理想的状态(对每个节点的访问频率相同)下,平均检索时间和平均重构时间均为关于N的函数,分别记为S(N)和R(N),失衡概率也是关于N的函数记为P(N),显然S是增函数,P是减函数,R尚不确定。我们再假定应用程序中,提交的检索请求占比率p,相应的提交变更请求则占1-p;如果变更请求没有造成失衡,那么它的费时可以忽略不计。综合这些考虑,我们可以对该应用程序的平均运行时间做出定义:t(N)=p*S(N)+( 1-p)*P(N)R(N),那么t(N)的极值在t’(N)=0时达到,这就为设计者提供了一个方法,可以使得其编写的应用程序运行在最优状态。

这里我们仅对HB(N)的检索开销进行分析。

2 检索时间分析

很显然,原有的对于AVL Tree的存储、检索、增删节点的算法同样可以应用到广义平衡二叉树中,只需要修改一下对失衡的判定,将|Dleft-Dright|>1改成|Dleft-Dright|>N即可。因此,这些算法的空间开销并没有发生改变,这里主要讨论其时间开销。

HB(N)的检索时间取决于HB(N)的深度,其最坏检索时间实际上就是HB(N)的深度,而平均检索时间则是小于最坏检索时间的一个值,因此,我们针对其深度进行分析。

命题1:对于深度为D的HB(N),其D/(N+1)层以上部分为满树。

证明:

设从上至下,x是第一个不健全的节点(没有左子树或右子树),P(x)是求父节点的函数,D(x)是求深度的函数。

由于x缺少一棵子树,所以其另一颗子树的深度不超过N,否则x不是HB(N),故D(x) ≤N+1。而x是P(x)的子树之一,故另一棵子树深度不超过D(x)+N,所以D(P(x))≤2(N+1)。同理P(x)是P2(x)的子树,故P2(x)的另一子树深度不超过2(N+1)+N+1=3(N+1)……

重复以上操作可得:D(Pl(x)) ≤(l+1)(N+1)

设Pl(x)是树的根节点,故D=D(Pl(x)) ≤(l+1)(N+1),故l≥[D/(N+1)]-1。

而Pl(x)是根,x=P0(x)是第一个不健全节点,所以从根开始,完整的层数为l+1层,故D/(N+1)层以上部分为满树。

命题2:深度为D的HB(N)至少包含αD-1个节点,其中α是αN+1-αN-1在(1,2 ]之间的根。

首先来看α的存在性,我们定义函数f(α)= αN+1-αN-1,它在(0,∞]上是连续的,且有f(1)=-1

为了简便,下文中将用αN表示αN+1-αN-1在(1,2 ]之间的根。

为了证明命题2,这里先证明两个引理。

引理1:αNN≤N+1

证明:

假设αNN>N+1,根据αN定义有1=αNN(αN-1)>(N+1)(αN-1),所以,αN

在N≥0时,[1+(1/(N+1))]N是趋向于自然对数底数e的增函数,e≈2.718

因此,假设不能成立,有αNN≤N+1。

引理2:自然数D≤N+1时,αND-1≤D。

证明:

将D视作未知数,N视为常数,由此αN也是常数。

令f(D) =αND,有f''(D)=αND(lnαN)2>0,所以f(D)是递增的凹函数。

令g(D)=D+1,是线性函数。

当D=1时,有f(D)=αN≤2=D+1=g(D)。

当D=N+1,有f(D)=αNN+1,根据αN定义,得到f(D)=αNN+1,又根据引理1,可f(D)≤N+2=g(D)。

根据凹函数的性质可以推断,当D≤N+1时均有f(D) ≤g(D)成立,即αND-1≤(D)。

下面证明命题2:

使用归纳法,令C(t)表示二叉树t的节点个数,Left(t)和Right(t)分别表示t的左右子树。

当D≤N+1时,容差为N的平衡二叉树t的极端形式就是链表,所以C(t)≥D,根据引理2可得C(t)≥αNN-1,命题2成立。

设当D∈[1,p]且p≥N+1时命题2成立,则D=p+1时,t可以看作两棵T(N)加上一个根节点组成的二叉树。这两棵T(N)中一棵深度为p,另一棵的深度在[p-N,p]上,否则t将不满足容差为N的平衡条件,并且很显然,这两棵子树的深度都在[1,p]区间上了。根据假设,t的节点个数可如下计算:

■

根据αN定义,C(t)=αNp-NαNN+1-1=αNp+1-1,即D=p+1时命题2也成立。

综上所述,在D为自然数的情况下,均有命题2成立。

推论4:包含n个节点的T(N)深度不超过log(n+1)/logαN。

由此可见, T(N)和满树在最坏检索时间相差倍数不超过logα0/logαN,这个倍数的取值与N的关系从表1和图1、图2中可以清晰反映。

3 结论

本文用理论方法考查了广义平衡二叉树的深度范围,得到了取值范围的上限表达式,并且这个上限表达式是便于计算的。从而我们能够迅速的得到,当我们设定容差N后,其检索时间的最大范围,为应用程序设计者提供了很好的理论依据。

但是,本文证明的结果所能指示的仅仅是一个上界,而不是上确界,也就是说实际的最坏检索时间比这个结果还要小,而平均检索时间则更加小。这是本文结果的缺陷所在,同时又证明了广义平衡二叉树确实有比AVL Tree更好的应用价值。

参考文献:

[1] Adel'son-Vel'skii G M, Landis E M. An algorithm for the organization ofinformation[J].Doklady Akad. Nauk. USSR 146,2,1962.

[2] Foster C C. A generalization of AVL trees[J].Communications of the ACM,1973,16(8).

[3] Karlton P L, Fuller S H, Scroggs R E, et al. Performance of Height-Balanced Trees[J].Communications of the ACM,1976,19(1).

[4] 唐自立.一种新的删除HB(k)树的结点的算法[J].计算机工程与应用.2007,43(5):45-48.

[5] Andersson A. General Balanced Trees[J].Journal of Algorithms,1999(30):1-18.

[6] Pfaff B. Performance Analysis of BSTs in System Software[D].ACM SIGMETRICS Performance Evaluation Review,2004.

[7] Baer J L, Schwab B. A Comparison of Tree-Balancing Algorithms[J]. Communications of the ACM,1977,20(5).

[8] Ottmann T H, Six H W. One-Sided k-Height-Balanced Trees[J]. Computing,1979,(22):283-290.