| 正如文献[3]所指出的，为了使用方便、减少代码重复、加快编译速度，通常将一个类的使用界面与它的内部实现相分离，这种做法还有利于为相同使用界面的类提供不同的内部实现。本文严格平衡二叉排序树类模板的设计将遵循使用界面与内部实现相分离的原则，以下是严格平衡二叉排序树模板类的使用界面，该程序文件不妨命名为sbbst.hpp。其中仅包含类的数据成员和相对比较简单的成员函数的定义，其他成员函数仅给出其函数原型。
template
structbstnode ｛
datatp data;
bstnode *lch,*rch;
｝;
template
classsbbst {
private:
bstnode*root;
int bstnode_count(bstnode *p);
bstnode* sbbst_construction(
bstnode*a[],int l,int h);
void insert_translation(bstnode*p,
bstnode*a[],int &i,int &flag);
void delete_translation(bstnode*p,
bstnode*a[],int &i,int &flag);
bstnode * binary_search(
bstnode*p, datatp x);
void sbbst_cancel(bstnode*p);
public:
sbbst() {root=0;}
sbbst(datatp d[],int n);
void sbbst_insert(datatpx);
void sbbst_delete(datatpx);
bstnode* sbbst_search (datatp x) {
return binary_search(root,x);
}
~sbbst() {sbbst_cancel(root);}
};
上述成员函数sbbst_construction, insert_translation和delete_translation中的形式参数a，i和flag的类型问题将在下一节予以详细解释。
4 SBBST类属类的详细设计
严格平衡二叉排序树类模板成员函数的设计与文献[1]给出的相应普通函数的设计有以下两点主要不同。
(a)作为辅助存贮空间的动态数组，其数组元素是严格平衡二叉排序树的结点指针，而不是结点本身。因此成员函数sbbst_construction,insert_translation和delete_translation的形式参数a是基类型为bstnode的指针数组，即形式参数a是bstnode的二级指针类型。这样平均查找长度，辅助存贮空间的大小与结点本身的信息量的大小无关，从而可大大减小辅助存贮空间的需求。另一方面，当插入、删除数据元素时避免了严格平衡二叉排序树结点的重新构造，而只需调整结点的左、右孩子结点的指针即可，从而也减少了重构严格平衡二叉排序树的时间开销期刊网。
(b)在文献[1]中递归函数insert-translation和delete-translaton使用静态局部变量i和flag分别表示已被处理的结点个数和处理状态的标志。因为在其自身递归调用时必须保持变量i和flag的值，所以把i和flag定义为静态局部变量是正确的。然而在外部调用上述两个函数时却必须重置i和flag的初值，但静态局部变量并不能区分这两种不同的情况。为了区分这两种不同情况，除了定义变量i和flag作为类模板的数据成员这种明显不可取的方法外，只能把变量i和flag设计成上述两个函数的引用类型（或指针类型）的形式参数；在成员函数sbbst_insert和sbbst_delete中定义局部变量i和flag，在调用上述两个函数时作为相应的的实在参数，并且在调用前必须重置局部变量i和flag的初值。作者认为，在设计递归函数时使用静态局部变量的作用是十分有限的。
下面给出当插入数据元素时，与构造严格平衡二叉排序树有关的成员函数的全部代码。其他成员函数可参阅文献[6]相应的普通函数进行设计。
4.1插入转换成员函数insert-translation
该函数中序遍历待插入元素的严格平衡二叉排序树，按元素值（包括插入元素）的递增次序构造结点指针顺序表（由动态数组表示）。代码如下：
template
void sbbst::
insert_translation(bstnode*p,
bstnode *a[],int &i,int &flag){
if(p!=0){
insert_translation(p->lch,a,i,flag);
if(flag==1||a[i]->data
a[++i]=p;
if (flag!=1) flag=1;
} else {
a[i+1]=a[i];
a[i++]=p;
}
insert_translation(p->rch,a,i,flag);
}
}
4.2构造SBBST成员函数sbbst-construction
该函数基于对结点指针顺序表的二分原理，按后序方式构造严格平衡二叉排序树。所谓后序方式是指：对任何结点，在确定其左、右孩子结点的lch和rch指针之后才确定该结点的lch和rch指针。该函数是十分简洁的递归函数，代码如下：
template
bstnode*sbbst::
sbbst-construction(bstnode *a[],
int l,int h){
bstnode *p;
if(l>h)
return 0;
p=a[(l+h)/2];
p->lch=sbbst-construction(a,l,(l+h)/2-1);
p->rch=sbbst-construction(a,(l+h)/2+1,h);
return p;
}
4.3 插入元素成员函数sbbst-insert
该函数申请表示结点指针顺序表所需的辅助存贮空间和表示插入元素的结点所需的存贮空间，并在调用函数insert_translation前重置局部变量i和flag的初值，最后释放辅助存贮空间。代码如下：
template
void sbbst::sbbst-insert(datatp x){
int n,i=0,flag=0;
bstnode **a;
n=bstnode-count(root);
a=new bstnode *[n+1];
a[0]=new bstnode*
a[0]->data=x;
insert-translation(root,a,i,flag);
root=sbbst-construction(a,0,n);
delete[] a;
}
5 尚待解决的问题
5.1 关于函数值ASL(n)-log2((n+1)/2)估计的一个猜想
当严格平衡二叉排序树的结点个数n=2k-1(k=1,2,3,…)时，本文推论2给出了其平均查找长度渐近性态的最精确的误差估计。由此自然会想到，对一般的严格平衡二叉排序树,即当其结点个数n≠2k-1(k=1,2,3,…)时是否有相同的结论？为此作者对1到232-1=4294967295之间的任意选择的大量数据在计算机上进行了测试。计算结果表明，对随机选择的特定的正整数N(不考虑N=1)都有
0 < ASL(N)-log2((N+1)/2)<1
并且随着N的增大，函数值 ASL(N)-log2((N+1)/2)越来越接近于0。由此作者猜想，结点个数为n（n>1）的严格平衡二叉排序树，若以log2((n+1)/2)作为其平均查找长度ASL(n)的近似值，其绝对误差应满足
0 < ASL(n)-log2((n+1)/2) <1 (n>1) (9)
并且
 （10）
计算结果同时表明，ASL(n)-log2((n+1)/2)并非单调函数。也许正是由于函数ASL(n)-log2((n+1)/2)的非单调性增加了证明断言(9)和(10)的难度。
5.2 关于广义严格平衡二叉排序树的一种构想
如果严格平衡二叉排序树允许存在数据元素值（通常是指主关键字值）相等的多个结点时，这些结点在严格平衡二叉排序树中的分布将变得非常复杂。下面对其分布规律作一简单分析。设这些结点中层数最小的结点是n0(不难证明该结点必定存在且唯一)，则其他结点的分布可分为以下两种情况：
(a)若n0的左（右）孩子结点的值等于n0的值，则其他结点可能是n0的左（右）子树的任何结点；
(b)若n0的左（右）孩子结点的值不等于n0的值，则其他结点可能是n0的左（右）孩子结点的右（左）子树的任何结点。
下面的简单例子表明，数据元素值相等的多个结点有可能分布在严格平衡二叉排序树的任何位置上。数据元素值为1，3，5，5，5，7，9的严格平衡二叉排序树如图1所示。
图1 严格平衡二叉排序树
数据元素值为5的结点的分布属于上述情况（b），n0就是根结点。显然，在这样的严格平衡二叉排序树上要确定数据元素值为5的结点位置必须搜索根结点的左、右子树，其搜索效率是十分低的，失去了严格平衡二叉排序树严格二分查找的优越性。为此作者提出一种既保持严格平衡二叉排序树的本质特点，又能应对上述情况的广义严格平衡二叉排序树的构想。其要点是：具有相同值的数据元素只构成广义严格平衡二叉排序树的一个结点，这些数据元素用单向链表表示，其头指针作为广义严格平衡二叉排序树该结点的一个信息。上述例子的广义严格平衡二叉排序树如图2所示。
图2 广义严格平衡二叉排序树
用广义严格平衡二叉排序树取代严格平衡二叉排序树对类属类的总体设计影响不大，其程序代码的修改也非常小。
6 结束语
严格平衡二叉排序树是真正形态平衡的二叉排序树，而传统的平衡二叉排序树未必真正平衡。因此，就概念而言，严格平衡二叉排序树理应取代名不副实的平衡二叉排序树。本文给出的严格平衡二叉排序树类属类作为新的类模板在面向对象程序设计中可应用于高效的数据检索和修改。广义严格平衡二叉排序树是树和线性表的一种混合结构，在多关键字的搜索中是一种值得考虑采用的数据结构。
参考文献:
[1]岑岗,周炳生.严格平衡二叉排序树及其构造[J].计算机工程与应用,2005,41(13):57-60
[2]严蔚敏,吴伟民.数据结构[M].第二版.北京:清华大学出版社,1992:225-226
[3]李师贤,李文军,周晓聪.面向对象程序设计基础[M].北京:高等教育出版社,1998:120-122
[4]W JCollins.Data Structure and STL[M]. Beijing China:Machine Press,2003:353-380
[5]R Lafore.Object Oriented Programming in C++(4th Edition)[M].Beijing China: Electron Press,2003．
[6]Cen Gang and Zhou Bingsheng. The BestBinary Sort Tree and the Implementation of Operations on It[A]. Proceedings ofthe Second International Conference on Computer Science & Education[C],Wuhan China: 2007,pp.264-267．
2/2 首页 上一页 1 2 |
