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

严格平衡二叉排序树类属类_平均查找长度.doc严格平衡二叉排序树类属类_ 平均查找长度论文导读: :本文对严格平衡二叉排序树的查找时间复杂度进行了详细分析, 给出了平均查找长度的计算公式及其渐进性态的误差估计。基于 C++ 语言的模板, 本文提出了严格平衡二叉排序树类属类的总体设计方案及主要成员函数的详细设计。本文最后还提出了有关严格平衡二叉排序树平均查找长度近似计算绝对误差的一个猜想以及有关广义严格平衡二叉排序树的一种构想。论文关键词:严格平衡二叉排序树,平均查找长度,模板,类属类 1 引言作者在文献[1] 中提出了二叉树结点的严格平衡因子、严格平衡二叉树和严格平衡二叉排序树的概念, 证明了严格平衡二叉树的平衡性态优于传统的平衡二叉树; 严格平衡二叉排序树的查找时间复杂度优于传统的平衡二叉排序树。该文提出的构造严格平衡二叉排序树的算法以及插入、删除元素时二叉排序树的严格平衡化过程与传统的相应算法相比较, 具有更简单和自然的优点。本文将对文献[1] 中提出的严格平衡二叉排序树的查找时间复杂度问题进行详细分析并对其渐近性态的误差作出估计。严格平衡二叉排序树是最优的二叉排序树,并且插入、删除元素又十分方便,因此它非常适合于作为动态查找表的存贮结构。本文应用 C++ 语言的模板机制, 给出严格平衡二叉排序树类属类的总体设计和主要成员函数的详细设计,希望为文献[4] 中给出的标准模板类库提供新的模板类。本文下面的叙述中, 术语“严格平衡二叉排序树”通常用 SBBST 表示, 特别是在标题中。 2 SBBST 查找时间复杂度分析 SBBST 平均查找长度的计算公式文献[1] 提出了等概率情况下平均查找长度的计算问题, 下面的定理 1 给出了由严格平衡二叉排序树的结点个数计算其平均查找长度的公式。定理 1 设严格平衡二叉排序树的结点个数为 n, 则其平均查找长度 ASL(n) 的计算公式为证明根据文献[1] 的定理 3 ,结点个数为 n 的严格平衡二叉排序树的深度, 而深度为 d 的严格平衡二叉排序树的前 d-1 层的结点构成满二叉树, 其结点个数为 2d-1-1 ( 参阅文献[1] 的引理) ,所以该严格平衡二叉排序树第 d 层的结点个数为 n-(2d-1-1) 。因此(1) 令(2) 则(3) (3)-(2) 得但等比级数之和所以 x=1-2d-1+(d-1)2d-1=1-2d+d*2d-1(4) 将(4) 代入(1) 得 ASL(n)=(1-2d+d*2d-1+(n+1)d-d*2d-1)/n =((n+1)d+1-2d)/n (5) 将代入(5) 即得定理 1 得证。推论 1 若严格平衡二叉排序树的结点个数 n=2k-1(k=1,2,3,…), 则其平均查找长度 ASL(n) 的计算公式为证明当 n=2k-1(k=1,2,3,…) 时, 所以推论 1 得证。文献[2] 中给出的静态查找表二分查找的计算公式与推论1 的计算公式一致,但只是定理 1 的特例。推论 2 若严格平衡二叉排序树的结点个数 n=2k-1(k=1,2,3,…), 则 log2((n+1)/2) 作为平均查找长度 ASL(n) 的近似值,其绝对误差满足 0< ASL(n)-log2((n+1)/2)≤1 并且证明由推论 1得(6) 因为 log2(n+1)/n>0 , 同时函数是严格单调减小函数,当 n=1 时 log2(n+1)/n=1 ,并且所以由( 6 )可知推论 2 的两个结论成立。由推论 2 可知, 对满二叉排序树即结点个数 n=2k-1(k=1,2,3,…) 的严格平衡二叉排序树而言,函数 log2((n+1)/2) 最精确刻划了其平均查找长度 ASL(n) 的渐近性态。 SBBST 平均查找长度渐近性态的误差估计由上述推论 2 自然会想到,对非满二叉排序树即结点个数 n≠2k-1(k=1,2,3…) 的严格平衡二叉排序树是否有类似的结论呢?下面的定理 2 和推论 3 部分地回答了这个问题。定理 2 结点个数为 n 的严格平衡二叉排序树,若以 log2((n+1)/2) 作为其平均查找长度 ASL(n) 的近似值,则其绝对误差满足证明由文献[1] 的定理3, 结点个数为n 的严格平衡二叉排序树的深度, 而深度为d 的满二叉树的结点个数为 2d-1, 所以 n≤2d-1, 即 1-2d≤-n 。由本文定理 1得但,即 d-1<log2(n+1), 所以(7) 另一方面,根据文献[1] 的引理,显然 n≥2d-1, 所以 2n-1≥2d-1, 即 1-2d≥1-2n, 由此得但, 所以(8) 由(7) 和(8) 得定理 2 得证。推论 3 结点个数为 n 的