2023年二叉排序树算法最佳二叉排序树的动态检索算法之新解.docx

2023年二叉排序树算法最佳二叉排序树的动态检索算法之新解 信息 S ¨。I C oN 科学 L L E Y - 最佳二叉排序树的动态检索算法之新解 刘禾喜I 刘玉华2 (1哈师大计算机科学与信息工程学院黑龙江哈尔滨 150025；2吉林榆树市其次试验中学东校区 吉林省榆树 130400) 【摘要】给出一种最佳二叉排序树的动态检索算法。其性能优q ：-二X 排序树和平衡-X 树克服了用折半检索方法构造最佳-X 捧序树的缺点，且不会因插入结点发生蜕变而影响检索的性能。 关键词】埘形月荣最佳一叉排序树动态检索算法中图分类号：013 文献标识码：A 文章编号：1671-7597(2023) 1120232-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 四、结论 一般说来。当结点个数相同的状况下，叉排序树的深度大于平衡二叉树，而平衡二叉树的深度义人十最佳_二叉排序树。所以，检索二叉排序树的效率最低，最佳二义排序效率最高。当须要插入结点时，最佳二叉捧序树和平衡_二叉树有时须要调整以保持其相应的特性。 本文给出的调整算法是在插入结点之后进行的。只是局限在一个最小的=叉捧序树范闱之内，克服了用折半榆索方法构造最佳义排序树的缺点。另外，折半检索算法与最佳二叉排序树的检爽性能是一 样的。但前者要求检 索的关键字是有序的，且应依次存储这就难以适应动态改变的要求。参考文献： 1cl 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 11997 2W 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 3X 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 1D a t a St r uct ur es 。Bei j i ng =H i gh er E ducat i on Pre s s 。1987172176(Ch)