关于二叉树的高

用二叉树作检索工具,D.E.Knuth曾作过详尽的介绍(见The Art of Computer Programming,Vol.3,Second edition,§6.22,1973 By Addison-wesley Publishing Company),它的特点是:在检索时,可像二分法一样,以正比于log_2N(N为记录个数)的比较次数找到所要记录,而在新记录插入时,又可用链结办法而不必移动记录的位置。因而它具有记录顺序排列和链结排列这两种优点。二叉树方法的缺点是其随机性很大。在文件生成时,随着记录出现的次序不同,生成的二叉树也不同,有能达到比log_2N大得多的比较次数,因而影响检索速度。本文讨论的是与二叉树检索速度直接相关的二叉树的高,或称最大路径长。文中给出了有确定节点数和确定高度的二叉树数目的计算公式,也研究了N个记录的各种可能排列和它们所生成的二叉树之间的对应关系,并由此计算了各个高度的概率分布。最后对平均高度提出了一个经验公式。