二叉排序树算法 最佳二叉排序树的动态检索算法之新解
信息
S ¨。I C oN
科学
L L E Y ■-
最佳二叉排序树的动态检索算法之新解
刘禾喜I 刘玉华2
(1．哈师大计算机科学与信息工程学院黑龙江哈尔滨
150025；2．吉林榆树市第二实验中学东校区
吉林省榆树
130400)
【摘要】给出一种最佳二叉排序树的动态检索算法。其性能优q ：-二X 排序树和平衡---X 树．克服了用折半检索方法构造最佳---X 捧序树的缺点，且不会因插入结点发生蜕变而影响检索的性能。
[关键词】埘形月荣最佳一叉排序树动态检索算法中图分类号：013
文献标识码：A
文章编号：1671--7597(2008) 1120082--01
一、引育
．
由于树形目录的存储结构比线性表作为表的组织形式灵活，所以在数据处理中经常要使用树形目录进行检索。构造树形目录的，J 法有：二叉排序树，平衡二叉树和最佳■义排序树。在所有结点的检索概率相等的情况下，最佳二义排序树的平均比较次数是最少的。
最佳二叉排序树通常采用折半榆索方法进行构造，但当检索某个关键字不在最佳■义排序树中时，需将该关键字插入其中，经过插入之后，最佳二叉排序树町能会发生蜕变而不具有最佳■叉排序树的性能。为了保证插入结点之后仍为最传_义排序树，町使用折半检索方法重新进行构造，但其效率其低。因此，本文提{l j 了一种最佳■叉排序树的动态检索算法。当检索的关键宁不在该最佳_叉排序树中时，插入其适当位置，若插入关键宁之后，该二叉排序树仍为最佳_二叉排序树，则插入完成，否则在发生蜕变的最佳二叉排宁树的基础I ：找到一棵离插入结点最近的、发生蜕变的最小二叉树进行动态调整牛成新的最佳二叉排序树。
二、算法原理
为了便于理解算法，在此简述一下最佳二叉排序树的定义和性质。所谓最佳■义排序树是指平均比较次数最少的二叉排序树：最佳二义排序树的所有予树均为最佳二叉排序树；最佳二义排序树除最低层的结点可以不满之外，其余各层的结点均足满的。
(一) 定义。二叉排序树中任一结点的左子树上的结点的个数与右子树上结点个数之差，称为结i 从因子，用nd 表示，即：nd=右子树上结0的个数一左子树上结点的个数。
下而给{lj 判断最佳■叉排序树因插入结点之后发生蜕变的定理。
(二) 定理。若一棵最佳_二叉排序树插入结点之后，蜕变成非最佳二叉
排序树时，应满足下述两个条件：①从根结点争插入结点的路径上。定存在某个结点的nd 的绝对值大于等于2；②插入结点的父结点一定为叶子结点。
证先证明条件①，设插入结P 之前，最佳二叉排序树为n 层，即第n 层是不满的，但由于插入结点之后破坏了最传一叉排序树的性质。所以插入的结点一定足在第n+l 层，在最佳二叉排序树f }J的第n —l 层至少有一个结点的分支为1或0，插入的结点的父结点是在第n 层上，显然从根结点至插入结点的路径上必有nd 的绝对值大于等于2的结点。
条件②用反证法来证明：若插入结点的父结点不是叶子结点，则插入的结点的父结点的分支应为l 。那么插入的结点不是在父结点的左字树I ：就是在右了树上。在插入结点之前未发，卜蜕变。所以插入此结点之后一也不会发生蜕变。因此小会破坏最佳一叉排序树的性质。
当最佳一叉排序树为n 层目第n 层是满的时。插入的结点一定是在第n+l 层。插入结点之前从根到第n 层上的每个结点的nd 均为0。插入结点之后。从根到插入结点的路径卜不会出现nd 的绝对值大于等于2的结点．显然。不会闪插入结点而导致蜕变。
下而举例略加说明。图l 是‘棵最佳二叉排序树，插入结点80之后的结果如图2所示。从图2中可以看出，插入结点80之后，结点50的nd=2，满足定理的第一个条件。但结点80的父结点己有左了树为65的结点，它不是插在
叶结点E ，故不满足条件②。冈而插入结点80之后仍为晟佳二二叉捧序树，未
发生蜕变不需调整。在图2中插入结点90之后的结果如图3所示，结点50的nd=3，满足条件①，结点90是插在叶结点80的右子树之上满足条件②。故不满足最佳二叉排序树的性质，需加调整，不满足条件①的除结点50之外。还有结点100．从前向给出的例1町以看出，现在就需要查找到离插入结点最近
的且满足条件①和②的r 树，然后进行调整。下面归结为几种情况：
(1) 如果插入结点之前，从根至插入结点的路径上所有结点的r i d=0，则插入结点后，从根至插入结点路径上的结点的nd 变为一1或l ，不满足条件①，此时不需要调整。
(2) 如果插入结点之前，从根至插入结点的路径上存在nd ≠0的结点，则插入结P 后的nd 的绝对值变小了，则不需要调整，这说明插入的结点是插在结点个数较少的子树上。
(3) 如果插入结点是插在结点较多的子树上，但插入结点的父结点不是叶结点，不满足条件②。故4i 需调整。
(4) 如果插入结点是捕在较多的子树上，且插入结点是插在叶结点之上，满足条件①和②。此种情况需要调整。
100
／＼
／＼
／＼
50
120
50
120
5D
120
／＼
／＼
／＼
／＼
／＼
／＼
∞
70
110
140
柚
秘1l O
140
／
／＼
／＼
瞄
∞
舒
66
∞
～
精l 量佳一叉捧序舅
瞧2攮入貉点∞之黯
∞
曩3擒入撼点∞之蔚
三、■法思想和描述
首先从根结点开始。然后根据要插入结点的关键字值的大小，用指针p 查找插入位簧，并计算其路径上每个结点的nd 的值。若[p —nd]>=2时。则t =p；若[p —nd 】+l一1，则t =Ni 11；若p ：N i l l ．则将插入结点插入其相应正确的位置。
插入结点之后，若t —nd>1，则在t 所指结点的右r 树上找出一个结点的最小关键字值替换t 所指结点的关键字值，并将t 原来所指结点的关键字值插入t 的左子树E 。
插入结点之后。若t —nd
四、结论
一般说来。当结点个数相同的情况下，■叉排序树的深度大于平衡二叉树，而平衡二叉树的深度义人十最佳_二叉排序树。所以，检索二叉排序树的效率最低，最佳二义排序效率最高。当需要插入结点时，最佳二叉捧序树和平衡_二叉树有时需要调整以保持其相应的特性。
本文给出的调整算法是在插入结点之后进行的。只是局限在一个最小的=叉捧序树范闱之内，克服了用折半榆索方法构造最佳■义排序树的缺点。另外，折半检索算法与最佳二叉排序树的检索性能是一
样的。但前者要求检
索的关键字是有序的，且应顺序存储这就难以适应动态变化的要求。参考文献：
[1]cl i f f or d
A Shaf f er 。A Pr acei on I ncr ndnct i on
t o
D a c e s St r utur es
and
A L gor chi r n
A na l y si S ．
N ew Y or k ：Pr ent i ce
Il a l 1．1997．
[2]W i ll j am
For d 。W i l l i am To pp ．D a t a
St r uct ur es w i th
c++。N ew Y or k ：
Pr ent i ce
I Ia l i 。1996．
[3]X C
Zho u —q un ，z 11A N G
N a i —x i i ao ．Y A N G
D o ng —qi n g
e t
a 1．D a t a
St r uct ur es 。Bei j i ng =H i gh er
E ducat i on Pre s s 。1987．172—176(Ch)．