论文部分内容阅读
[摘要]给出一种最佳二叉排序树的动态检索算法。其性能优于二叉排序树和平衡二叉树。克服了用折半检索方法构造最佳二叉排序树的缺点，且不会因插入结点发生蜕变而影响检索的性能。
[关键词]树形目录 最佳一叉排序树 动态检索 算法
中图分类号：O13 文献标识码：A 文章编号：1671－7597（2008）1120082－01
一、引言
由于树形目录的存储结构比线性表作为表的组织形式灵活，所以在数据处理中经常要使用树形目录进行检索。构造树形目录的方法有：二叉排序树，平衡二叉树和最佳二叉排序树。在所有结点的检索概率相等的情况下，最佳二叉排序树的平均比较次数是最少的。
最佳二叉排序树通常采用折半检索方法进行构造，但当检索某个关键字不在最佳二叉排序树中时，需将该关键字插入其中，经过插入之后，最佳二叉排序树可能会发生蜕变而不具有最佳二叉排序树的性能。为了保证插入结点之后仍为最佳二叉排序树，可使用折半检索方法重新进行构造，但其效率甚低。因此，本文提出了一种最佳二叉排序树的动态检索算法。当检索的关键字不在该最佳二叉排序树中时，插入其适当位置，若插入关键字之后，该二叉排序树仍为最佳二叉排序树，则插入完成，否则在发生蜕变的最佳二叉排序树的基础上找到一棵离插入结点最近的、发生蜕变的最小二叉树进行动态调整生成新的最佳二叉排序树。
二、算法原理
为了便于理解算法，在此简述一下最佳二叉排序树的定义和性质。所谓最佳二叉排序树是指平均比较次数最少的二叉排序树；最佳二叉排序树的所有子树均为最佳二叉排序树；最佳二叉排序树除最低层的结点可以不满之外，其余各层的结点均是满的。
（一）定义。二叉排序树中任一结点的左子树上的结点的个数与右子树上结点个数之差，称为结i从因子，用nd表示，即：nd=右子树上结0的个数一左子树上结点的个数。
下而给出判断最佳二叉排序树因插入结点之后发生蜕变的定理。
（二）定理。若一棵最佳二叉排序树插入结点之后，蜕变成非最佳二叉排序树时，应满足下述两个条件：①从根结点至插入结点的路径上一定存在某个结点的nd的绝对值大于等于2；②插入结点的父结点一定为叶子结点。
证先证明条件①，设插入结p之前，最佳二叉排序树为n层，即第n层是不满的，但由于插入结点之后破坏了最佳二叉排序树的性质。所以插入的结点一定是在第n+1层，在最佳二叉排序树中的第n一1层至少有一个结点的分支为1或0,插入的结点的父结点是在第n层上，显然从根结点至插入结点的路径上必有nd的绝对值大于等于2的结点。
条件②用反证法来证明：若插入结点的父结点不是叶子结点，则插入的结点的父结点的分支应为1。那么插入的结点不是在父结点的左字树上就是在右子树上。在插入结点之前未发生蜕变。所以插入此结点之后一也不会发生蜕变。因此不会破坏最佳一叉排序树的性质。
当最佳一叉排序树为n层目_第n层是满的时。插入的结点一定是在第n+1层。插入结点之前从根到第n层上的每个结点的nd均为0。插入结点之后。从根到插入结点的路径上不会出现nd的绝对值大于等于2的结点。显然。不会因插入结点而导致蜕变。
下而举例略加说明。图1是一棵最佳二叉排序树，插入结点80之后的结果如图2所示。从图2中可以看出，插入结点80之后，结点50的nd= 2，满足定理的第一个条件，但结点80的父结点己有左子树为65的结点，它不是插在叶结点上，故不满足条件②。因而插入结点80之后仍为最佳二叉排序树，未发生蜕变不需调整。在图2中插入结点90之后的结果如图3所示，结点50的nd= 3,满足条件①，结点90是插在叶结点80的右子树之上满足条件②，故不满足最佳二叉排序树的性质，需加调整，不满足条件①的除结点50之外。还有结点100。从前而给出的例1可以看出，现在就需要查找到离插入结点最近的且满足条件①和②的r树，然后进行调整。下面归结为几种情况：
（1）如果插入结点之前，从根至插入结点的路径上所有结点的nd= 0，则插入结点后，从根至插入结点路径上的结点的nd变为一1或1，不满足条件①，此时不需要调整。
（2）如果插入结点之前，从根至插入结点的路径上存在nd≠0的结点，则插入结p后的nd的绝对值变小了，则不需要调整，这说明插入的结点是插在结点个数较少的子树上。
（3）如果插入结点是插在结点较多的子树上，但插入结点的父结点不是叶结点，不满足条件②，故不需调整。
（4）如果插入结点是插在较多的子树上，且插入结点是插在叶结点之上，满足条件①和②。此种情况需要调整。
三、算法思想和描述
首先从根结点开始，然后根据要插入结点的关键字值的大小，用指针p查找插入位置，并计算其路径上每个结点的nd的值。若[p→nd]>=2时，则t=p；若[p→nd]+1<1或[p→nd]-1>-1，则t=N ill；若p= Nill，则将插入结点插入其相应正确的位置。
插入结点之后，若t→nd>1，则在t所指结点的右r树上找出一个结点的最小关键字值替换t所指结点的关键字值，并将t原来所指结点的关键字值插入t的左子树上。
插入结点之后。若t→nd<-1，则在t所指结点的左r树上找出一个结点的最大关键字值替换t所指结点的关键字值，并将t原来所指结点的关键字值插入t的右子树上。
四、结论
一般说来，当结点个数相同的情况下，二叉排序树的深度大于平衡二叉树，而平衡二叉树的深度又大于最佳二叉排序树。所以，检索二叉排序树的效率最低，最佳二叉排序效率最高。当需要插入结点时，最佳二叉排序树和平衡二叉树有时需要调整以保持其相应的特性。
本文给出的调整算法是在插入结点之后进行的，只是局限在一个最小的二叉排序树范围之内，克服了用折半检索方法构造最佳二叉排序树的缺点。另外，折半检索算法与最佳二叉排序树的检索性能是一样的。但前者要求检索的关键字是有序的，且应顺序存储这就难以适应动态变化的要求。
参考文献：
[1]Clifford A Shaffer。A Praccion Incrndnction to Daces Strutures and A Lgorchirn A nalysis.New York：Prentice IIall, 1997.
[2]William Ford, William Topp.Data Structures with C++。New York：Prentice IIall, 1996.
[3] XC Zhou-qun, ZhANG Nai-xiiao,YANG Dong-qing et al . Data Structures。Beijing：Higher Education Press,1987.172-176( Ch).
[关键词]树形目录 最佳一叉排序树 动态检索 算法
中图分类号：O13 文献标识码：A 文章编号：1671－7597（2008）1120082－01
一、引言
由于树形目录的存储结构比线性表作为表的组织形式灵活，所以在数据处理中经常要使用树形目录进行检索。构造树形目录的方法有：二叉排序树，平衡二叉树和最佳二叉排序树。在所有结点的检索概率相等的情况下，最佳二叉排序树的平均比较次数是最少的。
最佳二叉排序树通常采用折半检索方法进行构造，但当检索某个关键字不在最佳二叉排序树中时，需将该关键字插入其中，经过插入之后，最佳二叉排序树可能会发生蜕变而不具有最佳二叉排序树的性能。为了保证插入结点之后仍为最佳二叉排序树，可使用折半检索方法重新进行构造，但其效率甚低。因此，本文提出了一种最佳二叉排序树的动态检索算法。当检索的关键字不在该最佳二叉排序树中时，插入其适当位置，若插入关键字之后，该二叉排序树仍为最佳二叉排序树，则插入完成，否则在发生蜕变的最佳二叉排序树的基础上找到一棵离插入结点最近的、发生蜕变的最小二叉树进行动态调整生成新的最佳二叉排序树。
二、算法原理
为了便于理解算法，在此简述一下最佳二叉排序树的定义和性质。所谓最佳二叉排序树是指平均比较次数最少的二叉排序树；最佳二叉排序树的所有子树均为最佳二叉排序树；最佳二叉排序树除最低层的结点可以不满之外，其余各层的结点均是满的。
（一）定义。二叉排序树中任一结点的左子树上的结点的个数与右子树上结点个数之差，称为结i从因子，用nd表示，即：nd=右子树上结0的个数一左子树上结点的个数。
下而给出判断最佳二叉排序树因插入结点之后发生蜕变的定理。
（二）定理。若一棵最佳二叉排序树插入结点之后，蜕变成非最佳二叉排序树时，应满足下述两个条件：①从根结点至插入结点的路径上一定存在某个结点的nd的绝对值大于等于2；②插入结点的父结点一定为叶子结点。
证先证明条件①，设插入结p之前，最佳二叉排序树为n层，即第n层是不满的，但由于插入结点之后破坏了最佳二叉排序树的性质。所以插入的结点一定是在第n+1层，在最佳二叉排序树中的第n一1层至少有一个结点的分支为1或0,插入的结点的父结点是在第n层上，显然从根结点至插入结点的路径上必有nd的绝对值大于等于2的结点。
条件②用反证法来证明：若插入结点的父结点不是叶子结点，则插入的结点的父结点的分支应为1。那么插入的结点不是在父结点的左字树上就是在右子树上。在插入结点之前未发生蜕变。所以插入此结点之后一也不会发生蜕变。因此不会破坏最佳一叉排序树的性质。
当最佳一叉排序树为n层目_第n层是满的时。插入的结点一定是在第n+1层。插入结点之前从根到第n层上的每个结点的nd均为0。插入结点之后。从根到插入结点的路径上不会出现nd的绝对值大于等于2的结点。显然。不会因插入结点而导致蜕变。
下而举例略加说明。图1是一棵最佳二叉排序树，插入结点80之后的结果如图2所示。从图2中可以看出，插入结点80之后，结点50的nd= 2，满足定理的第一个条件，但结点80的父结点己有左子树为65的结点，它不是插在叶结点上，故不满足条件②。因而插入结点80之后仍为最佳二叉排序树，未发生蜕变不需调整。在图2中插入结点90之后的结果如图3所示，结点50的nd= 3,满足条件①，结点90是插在叶结点80的右子树之上满足条件②，故不满足最佳二叉排序树的性质，需加调整，不满足条件①的除结点50之外。还有结点100。从前而给出的例1可以看出，现在就需要查找到离插入结点最近的且满足条件①和②的r树，然后进行调整。下面归结为几种情况：
（1）如果插入结点之前，从根至插入结点的路径上所有结点的nd= 0，则插入结点后，从根至插入结点路径上的结点的nd变为一1或1，不满足条件①，此时不需要调整。
（2）如果插入结点之前，从根至插入结点的路径上存在nd≠0的结点，则插入结p后的nd的绝对值变小了，则不需要调整，这说明插入的结点是插在结点个数较少的子树上。
（3）如果插入结点是插在结点较多的子树上，但插入结点的父结点不是叶结点，不满足条件②，故不需调整。
（4）如果插入结点是插在较多的子树上，且插入结点是插在叶结点之上，满足条件①和②。此种情况需要调整。
三、算法思想和描述
首先从根结点开始，然后根据要插入结点的关键字值的大小，用指针p查找插入位置，并计算其路径上每个结点的nd的值。若[p→nd]>=2时，则t=p；若[p→nd]+1<1或[p→nd]-1>-1，则t=N ill；若p= Nill，则将插入结点插入其相应正确的位置。
插入结点之后，若t→nd>1，则在t所指结点的右r树上找出一个结点的最小关键字值替换t所指结点的关键字值，并将t原来所指结点的关键字值插入t的左子树上。
插入结点之后。若t→nd<-1，则在t所指结点的左r树上找出一个结点的最大关键字值替换t所指结点的关键字值，并将t原来所指结点的关键字值插入t的右子树上。
四、结论
一般说来，当结点个数相同的情况下，二叉排序树的深度大于平衡二叉树，而平衡二叉树的深度又大于最佳二叉排序树。所以，检索二叉排序树的效率最低，最佳二叉排序效率最高。当需要插入结点时，最佳二叉排序树和平衡二叉树有时需要调整以保持其相应的特性。
本文给出的调整算法是在插入结点之后进行的，只是局限在一个最小的二叉排序树范围之内，克服了用折半检索方法构造最佳二叉排序树的缺点。另外，折半检索算法与最佳二叉排序树的检索性能是一样的。但前者要求检索的关键字是有序的，且应顺序存储这就难以适应动态变化的要求。
参考文献：
[1]Clifford A Shaffer。A Praccion Incrndnction to Daces Strutures and A Lgorchirn A nalysis.New York：Prentice IIall, 1997.
[2]William Ford, William Topp.Data Structures with C++。New York：Prentice IIall, 1996.
[3] XC Zhou-qun, ZhANG Nai-xiiao,YANG Dong-qing et al . Data Structures。Beijing：Higher Education Press,1987.172-176( Ch).