关于最佳二叉排序树的研究

《关于最佳二叉排序树的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于最佳二叉排序树的研究刘灿齐(同济大学)STUDYONBESTBINARYORDERTREELluo人NQITo,‘U。艺”e犷。‘t梦(厉)AbstractThebes七binaryordertreePlay日animPortan七roloint}10theoryfor.,atasearon七hisPaPer。oea七hea七iearoPer七ie吕osuer.dhImmmlPfh毛eesarede毛ee七ed,Anewme七hodtose七i七15givenand七healgori七hmofi七5revi日iono

2、ndynamies七几七e日5sos.1al七ud拓d,,,,KeywordsBes七treeregul:r七reepa七hbes七bin“ryordortreel’ogu1:、rordorr,.七eequalifiedPoin七。摘要最佳二叉排序树在数据检索理论中占有重要地位本文挖掘了它的一些重要的数学,、性质在此基础上提出了一种建立最佳二叉排序树的新方法并探讨了它在动态情形下的修正算法。,,,,,。关键词最佳树正则树路径最佳二叉排序树(BBO:树)正排树资格点一、引言,,在依关键字检索记录的算法中最佳二叉排序树法是一

3、种高效率的方法已被不少的软。,件设计者采用然而在已有的文献中(如【1〕)提出的建立算法是依赖于记录序列的有序。,。性即先要将记录依关键字排成有序的再用二分法逐一取出各记录来建树这显然是麻。,:。烦费时的本文将设计出一种不经排序直接建树的算法时间代价为O(NlogN):,使用最佳二叉排序树的另一问题是当在树上插入或删除结点时原树的最佳性可能被。,,a破坏一旦破坏怎样修正使其恢复最佳性?Adel,sonVel,,kii和Lndi,曾提出过关于J,,,AVT树的修正算法[1]然而AVL树在检索效率上比最佳二叉排序树差故最佳二叉

4、排序。树的修正算法也将被讨论,,本文首先提出了正则树和最佳树的概念研究了它们内在的数学性质在此垅础上讨。本文19似年U月朋印{义到1。,论了以上两间题的算法由于篇幅所限本文省略了所有定理的证明及一些算法的详细。表达二、正则树和最佳树1.正则树,,。T为空,设T是二叉树从它的根到各结点的长度之和叫它的路径记作尸(T)若,n,,‘。、、。规定P(T)一0否则设结点数为记N(T)一根的左右子树分别记作L(T)R(T)、,设其结点数分别为ab易知一一一一P(T)~P(L(T))卜P(R(T))卜a卜b一P(L(T))+P(R(T

5、))卜(n一1)(1),、,定义1若一个二叉树或为空或它的每个结点的左右子树的结点数相差最多为」则。称它是正则树“,正则树的路径最短,Llog,‘」,定理1在所有结点数为的二叉树中为馨其中L刘表。n,。示不大于,的最大整数一o时此和为0,。定理1的逆命题不成立这由下可见匀.最佳树,二,、二,二、、。为简便计本文约定A(的B(功分别表示夕两数中的最小者最大者n:定义,个结点的最佳树的递归定义是.空二叉树是最佳树;·、,a、,:若。个结点的二叉树的根的左右子树均是最佳树设结点数分别为b满足L,09,”J一二a,a,L,0‘,

6、”,Z一1喊A(石)(B(b)

7、若L(刀)与L(刀)等形且R(D)与R(刀)等形则刀与刃等形。,,,。用、表示等形显然~是一等价关系且若D~E必有N(D)~N(刀),,,。设X~{孰⋯叽}城是结点。(了)表示由了中结点组成的所有。个结点的二叉,。树之集我们称商集口(X)/、闭中的元素为形一个形是由一个二叉树及所有与它等形的二叉树组成的集合。,,显然若一个形中有一个二叉树是最佳树(正则树)则它所有的二叉树也是最佳树(正,。则树)此时我们称该形为最佳形(正则形),当任选一个形中的一二叉树作为代表忽略各结点的具体内容而都看成实点(称这些实,。,点为位置点)即

8、可用实点二叉树直观地表示一个形口(厂)/~中形的个数其实与Z无关。n,,,仅与。有关如~3时。(工)/~有五个形直观表示如图1其中第一个是最佳形(恰好。可以推出:也是正则形)口(工)/~中形的数目口(哟满足已(O)一1u·naG(,)一仔()G(一1一)(,‘>1)艺八/<>图1,.最佳二叉排序树及其数目,,。当中