二叉排序树平均查找长度的精确表达式.pdf

《二叉排序树平均查找长度的精确表达式.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、，2015年7月UniversityEducation二叉排序树平均查找长度的精确表达式程希明王昕(北京信息科技大学，北京100192)[摘要]查找长度的精确表达式，需要对二又排序树的平均查找长度进行详细分析，寻找一个平均查找长度的精确表达式及其证明过程。基于二叉树表，提出欧拉常数的一种新的计算方法，对平均查找长度精确表达式进行了算例分析，并与其他经典平均查找长度计算公式加以对比，验证了其正确性。‘[关键词]二叉排序树平均查找长度欧拉常数[中图分类号]TP311．12[文献标识码]A[文章编号]2095—3437(2015)

2、07—0100—02《数据结构》作为一门介于数学、计算机硬件和计算二叉排序树是一种动态树表，树的结构通常不是一机软件三者之间的核心课程，是信息与计算科学相关专次生成的，而是在查找过程中，当树中不存在关键字等业的综合性专业基础必修课。树形结构是该课程的重要于给定值的结点时再进行插入。新插入的结点一定是一内容之一，掌握二叉树的逻辑结构特性、各种存储结构个新添加的叶子结点，并且是查找不成功时，查找路径的特点及适用范围，有助于学生学会对处理的数据建立上访问的最后一个结点的左孩子或右孩子结点。抽象数据类型，并使学生对算法的复杂度有一定

3、的分析崔尚森等田提出了基于表地址前缀分布特点的前缀能力。长度二分查找方案；秦玉平等131给出了常用查找算法平在数据处理中，查找是一种经常使用的操作方法，均查找长度的计算方法，包括查找成功和查找失败平均树表中数据元素的插入和删除均需要进行查找操作。查查找长度的计算。本文给出了一个关于二叉树平均查找找是指在含有若干记录的表中找出关键字值与给定值长度的精确表达式及其证明过程，并给出了算例验证。相同的记录。若表中存在这样的记录，则查找成功，返回一、二叉树的平均查找长度所找到记录的信息或记录在表中的位置；否则查找失查找运算的主要操作是

4、进行关键字的比较，为确定败，返回空记录或空指针。当用线性表作为表的组织形给定关键字在查找表中的位置，需和给定关键字进行比式时，可以有三种查找法，其中二分查找效率最高。但由较，将比较次数的期望值称为平均查找长度。于二分查找要求表中结点按关键字有序，且不能用链表假设任意给定n个记录，每个记录带有可比较大小作存储结构，因此，当表的插人或删除操作频繁时，为维的关键字，将这n个记录排成一棵二叉排序树，假定在护表的有序性，势必要移动表中很多结点。这种由移动查找成功的情况下，要求出这棵二叉排序树的平均查找结点引起的额外时间开销，就会抵消二

5、分查找的优点。长度。也就是说，二分查找只适用于静态查找表，若要对动态不妨设这n个记录中有i个记录的关键字比第一个查找表进行高效率的查找，可采用二叉排序树作为表的记录的关键字小，有n—i一1组织形式。个记录的关键字不比第一二叉排序树，作为树形结构的一个重要类型，又称个记录的关键字小，如图2⑩二叉查找树，亦称二叉搜索树，其存储结构和算法比较所示。图2n个记录的二叉排序树简单，特别适合计算机处理。它或者是一棵空树，或者是由此得到的二叉排序具有下列性质的二叉树【1：(1)它的左子树上的所有结点树在每个记录等概率被查的情况下，其平均查

6、找长度(若存在)的值均小于根结点的值；(2)它的右子树上的为：所有结点(若存在)的值均不P(n)：一[1+ix(P(i)+1)+(n—i一1)×(P(n—i一1)+1)]。小于根结点的值；(3)它的左、其中P(k)表示含k个结点的二叉排序树的平均查右子树也分别为二叉排序树。找长度。由于这n个记录是任意的，所以它们的排列次例如，由一组关键字序具有随机性。(18，5，20，9，6，27，3)可构造图17个关键字的二叉排亭树即下列事件：如图1所示的二叉排序树。[收稿时间]2014—11—13【基金项目]北京市青年英才项目(YETP

7、1508)；北京市教委科技面上项目(KM201411232019)。[作者简介]程希明(1965一)，男，江西人，博士，北京信息科技大学理学院教授。UniversityEducation⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯A“i个记录的关键字比第一个记录的关键孚小，[可++‘+1]=n—i一1个记录的关键字比第一个记录的关键字小”(0，1，2，⋯，n一1)是等概率出现的。．P(1)+·Znn＼J扣咔’+

8、，十11／一n·所以有：(争一)。尸(n)=1∑P(n，)考虑到尸(1)=1，所以P(n)．2(1+})(1++．．。+})一：1+∑[)+(一i一1)P(n—i—1)]3，从而证明了(4)。当n较大时，(4)式有一个近似式：=1+2∑)。(1)．P(n)=21nn+2C一3。(6)其中C