拟合度
二叉排序树平均查长度的精确表达式作者：程希明 王昕来源：《大学教育》2015年第07太平洋cs
期构造区 [摘 要]查长度的精确表达式，需要对二叉排序树的平均查长度进行详细分析，寻一个平均查长度的精确表达式及其证明过程。基于二叉树表，提出欧拉常数的一种新的计算方法，对平均查长度精确表达式进行了算例分析，并与其他经典平均查长度计算公式加以对比，验证了其正确性。
[关键词]二叉排序树 平均查长度 欧拉常数
[中图分类号] TP311.12 [文献标识码] A [文章编号] 2095-3437（2015）07-0100-02
《数据结构》作为一门介于数学、计算机硬件和计算机软件三者之间的核心课程，是信息与计算科学相关专业的综合性专业基础必修课。树形结构是该课程的重要内容之一，掌握二叉树的逻辑结构特性、各种存储结构的特点及适用范围，有助于学生学会对处理的数据建立抽象数据类型，并使学生对算法的复杂度有一定的分析能力。
在数据处理中，查是一种经常使用的操作方法，树表中数据元素的插入和删除均需要进行查操作。查是指在含有若干记录的表中出关键字值与给定值相同的记录。若表中存在这样的记录，则查成功，返回所到记录的信息或记录在表中的位置;否则查失败，返回空记录或空指针。当用线性表作为表的组织形式时，可以有三种查法，其中二分查效率最高。但由于二分查要求表中结点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分查的优点。也就是说，二分查只适用于静态查表，若要对动态查表进行高效率的查，可采用二叉排序树作为表的组织形式。 二叉排序树，作为树形结构的一个重要类型，又称二叉查树，亦称二叉搜索树，其存储结构和算法比较简单，特别适合计算机处理。它或者是一棵空树，或者是具有下列性质的二叉树逆变效率[1]：（1）它的左子树上的所有结点（若存在）的值均小于根结点的值;（2）它的右子树上的所有结点（若存在）的值均不小于根结点的值信道增益;俊余（3）它的左、右子树也分别为二叉排序树。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议