严格平衡二叉排序树类属类_平均查找长度

论文导读:：本文对严格平衡二叉排序树的查找时间复杂度进行了详细分析，给出了平均查找长度的计算公式及其渐进性态的误差估计。基于C++语言的模板，本文提出了严格平衡二叉排序树类属类的总体设计方案及主要成员函数的详细设计。本文最后还提出了有关严格平衡二叉排序树平均查找长度近似计算绝对误差的一个猜想以及有关广义严格平衡二叉排序树的一种构想。
论文关键词：严格平衡二叉排序树，平均查找长度，模板，类属类
 

1 引言

作者在文献[1]中提出了二叉树结点的严格平衡因子、严格平衡二叉树和严格平衡二叉排序树的概念，证明了严格平衡二叉树的平衡性态优于传统的平衡二叉树；严格平衡二叉排序树的查找时间复杂度优于传统的平衡二叉排序树。该文提出的构造严格平衡二叉排序树的算法以及插入、删除元素时二叉排序树的严格平衡化过程与传统的相应算法相比较，具有更简单和自然的优点。本文将对文献[1]中提出的严格平衡二叉排序树的查找时间复杂度问题进行详细分析并对其渐近性态的误差作出估计。

严格平衡二叉排序树是最优的二叉排序树，并且插入、删除元素又十分方便，因此它非常适合于作为动态查找表的存贮结构。本文应用C++语言的模板机制，给出严格平衡二叉排序树类属类的总体设计和主要成员函数的详细设计，希望为文献[4]中给出的标准模板类库提供新的模板类。

本文下面的叙述中，术语“严格平衡二叉排序树”通常用SBBST表示，特别是在标题中。

2 SBBST查找时间复杂度分析

2.1 SBBST 平均查找长度的计算公式

文献[1]提出了等概率情况下平均查找长度的计算问题，下面的定理1给出了由严格平衡二叉排序树的结点个数计算其平均查找长度的公式。

定理1 设严格平衡二叉排序树的结点个数为n，则其平均查找长度ASL(n)的计算公式为

证明 根据文献[1]的定理3，结点个数为n的严格平衡二叉排序树的深度,而深度为d的严格平衡二叉排序树的前d-1层的结点构成满二叉树，其结点个数为2^d-1-1（参阅文献[1]的引理），所以该严格平衡二叉排序树第d层的结点个数为n-(2^d-1-1)。因此

(1)

令

(2)

则

(3)

(3)-(2)得

但等比级数之和

所以

x=1-2^d-1+(d-1)2^d-1=1-2^d+d*2^d-1(4)

将(4)代入(1)得

ASL(n)=(1-2^d+d*2^d-1+(n+1)d-d*2^d-1)/n

=((n+1)d+1-2^d)/n (5)

将代入(5)即得

定理1得证。

推论1 若严格平衡二叉排序树的结点个数n=2^k-1(k=1,2,3,…),则其平均查找长度ASL(n)的计算公式为

证明当n=2^k-1(k=1,2,3,…)时，

所以

推论1得证。文献[2]中给出的静态查找表二分查找的计算公式与推论1的计算公式一致，但只是定理1的特例。

推论2 若严格平衡二叉排序树的结点个数n=2^k-1(k=1,2,3,…),则log₂((n+1)/2)作为平均查找长度ASL(n)的近似值，其绝对误差满足

0< ASL(n)-log₂((n+1)/2)≤1

并且

证明 由推论1得

(6)

因为log₂(n+1)/n>0，同时函数是严格单调减小函数，当n=1时log₂(n+1)/n=1，并且

所以由（6）可知推论2的两个结论成立。

由推论2可知，对满二叉排序树即结点个数n=2^k-1(k=1,2,3,…)的严格平衡二叉排序树而言，函数log₂((n+1)/2)最精确刻划了其平均查找长度ASL(n)的渐近性态。

2.2 SBBST平均查找长度渐近性态的误差估计

由上述推论2自然会想到，对非满二叉排序树即结点个数n≠2^k-1(k=1,2,3…)的严格平衡二叉排序树是否有类似的结论呢？下面的定理2和推论3部分地回答了这个问题。

定理2 结点个数为n的严格平衡二叉排序树，若以log₂((n+1)/2)作为其平均查找长度ASL(n)的近似值，则其绝对误差满足

证明 由文献[1]的定理3 ,结点个数为n的严格平衡二叉排序树的深度,而深度为d的满二叉树的结点个数为2^d-1,所以n≤2^d-1,即1-2^d≤-n。由本文定理1得

但，即d-1<log₂(n+1),所以

(7)

另一方面，根据文献[1]的引理，显然n≥2^d-1,所以2n-1≥2^d-1,即1-2^d≥1-2n,由此得

但,所以

(8)

由(7)和(8)得

定理2得证。

推论3 结点个数为n的严格平衡二叉排序树，若以log₂((n+1)/2)作为其平均查找长度ASL（n）的近似值，则其绝对误差满足

-1< ASL(n)-log₂((n+1)/2)<2

推论3的绝对误差估计不依赖于严格平衡二叉排序树的结点个数，显然是定理2的化简。遗憾的是，对非满二叉排序树即结点个数n≠2^k-1(k=1,2,3,…)的严格平衡二叉排序树，作者尚未得到如上述推论2相同的结论。本文最后一节将对此问题作进一步的讨论。

3 SBBST类属类的总体设计

作者应用C++语言的模板机制，把严格平衡二叉排序树类属类用类模板表示。文献[5]指出，在设计类模板时，并不只是类本身要转化为模板，其他使用可变数据类型的结构都必须设计成模板。所以,设计严格平衡二叉排序树的类模板时，首先必须把严格平衡二叉排序树的结点结构模板化。

 1/2    1 2 下一页 尾页