二元排序树的平均搜索长度的精确表达

二元排序树的平均搜索长度的精确表达式[Eternal Sword Master dlong To]找到该长度的确切表达式，您需要详细分析二元排序树的平均搜索长度，以找到一个准确的表达式平均搜索长度及其证明过程. 基于二叉树表，提出了一种新的欧拉常数计算方法. 分析平均查找长度的精确表达式，并将其与其他经典的平均查找长度的经典计算公式进行比较，以验证其正确性. [关键词]二叉树的平均搜索长度欧拉常数“数据结构”是数学，计算机硬件和计算机软件之间的核心课程. 它是信息和计算科学相关的综合基础必修课. 树结构是本课程的重要内容之一. 掌握二叉树的逻辑结构特征，各种存储结构的特征以及应用范围将有助于学生学习为处理后的数据建立抽象数据类型，并使学生复杂地使用算法. 学位具有一定的分析能力. 在数据处理中，查找是一种常用的操作方法. 在树表中插入和删除数据元素需要进行查找操作. 查找是指在包含多个记录的表中查找具有与给定值相同的键值的记录. 如果表中存在这样的记录，则查找成功，并返回找到的记录的信息或表中的位置；否则，查找将失败二叉排序树查找，并返回空记录或指针. 当使用线性表作为表的组织形式时，有三种搜索方法，而二进制搜索是最有效的.

但是，由于二进制搜索要求表中的节点按关键字排序，并且不能使用链接列表作为存储结构，因此当表插入或删除操作频繁时二叉排序树查找，必须移动表以进行维护表的顺序许多节点. 移动节点导致的额外时间开销将抵消二进制搜索的优势. 换句话说，二进制搜索仅适用于静态查找表. 为了有效地搜索动态查找表，可以将二进制排序树用作表组织形式. 二进制排序树，作为树结构的一种重要类型，也称为二进制搜索树，也称为二进制搜索树. 它的存储结构和算法比较简单，特别适合计算机处理. 它是具有以下属性[1]的空树或二叉树: （1）其左子树上所有节点（如果有）的值小于根节点的值； （2）它的右子树上所有节点的值（如果有的话）不小于根节点的值; （3）它的左和右子树也是二进制排序的. 例如，一组关键字（18、5、20、9、6、27、3）可以构建如图1所示的二进制排序树. 二进制排序树是一种动态树表. 树的结构通常不会一次生成. 而是在树中没有包含等于给定值的关键字的节点时将其插入. 新插入的节点必须是新添加的叶节点，并且是搜索失败时在搜索路径上访问的最后一个节点的左子节点或右子节点. 崔尚森等. [2]提出了一种基于表地址前缀的分布特征的前缀长度二进制搜索方案. 秦玉萍等. 文献[3]给出了常用搜索算法的平均搜索长度的计算方法，包括成功搜索和失败搜索的平均搜索长度的计算.

本文给出了关于二叉树平均搜索长度及其证明过程的准确表达式，并给出了验证示例. 首先，二叉树的平均操作长度. 搜索操作的主要操作是比较关键字. 为了确定给定关键字在查找表中的位置，需要将其与给定关键字进行比较. 比较次数的期望值称为平均搜索. 长度. 假定任何给定的n条记录（每个记录具有可比较大小的键记录）都排列成二进制排序树. 假设如果搜索成功，则需要此二进制排序树的平均搜索长度. 最好假设n个记录中的i个记录的关键字小于第一个记录的关键字，ni-1个记录的关键字不小于第一个记录的关键字，如图2所示. 在以相等的概率检查由此获得的二进制分类树的情况下，平均搜索长度为: 其中P（k）表示具有k个节点的二进制分类树的平均搜索长度. 由于这n个记录是任意的，因此它们具有随机顺序，这是以下事件: Ai =“” i个记录的关键字小于第一个记录的关键字，而ni-1个记录的关键字优于first记录的关键字“ small”（i = 0、1、2，…，n-1）以相同的概率出现. 因此有: Min [4]给出公式（1）的估计上限: P（n）燮1 + 4logn. 二，平均搜索长度的精确表达式下面，我们给出公式（1）的精确表达式.

定理: （1）中P（n）的表达式是要证明: 计算P（n）的递归？ n2-P（n-1）？ （1）式中的（n-1）2. 对（5）进行以下一系列变形: 将上述公式与（5）一起添加，然后左右左右对它们进行排序: 使用引理对其进行排序: 考虑P（1）= 1，则证明（4 ）. 当它较大时，（4）具有一个近似公式: P（n）= 2lnn + 2C-3. 其中C是欧拉常数，0.577215≤C≤0.577216. 3.示例验证我们可以简单地验证定理的正确性. 当n = 3时，三个记录有六种排列，即γhref =“ http://www.sanjiangge.com/book/46/46269/index.html” target =“ _ blank”>永恒剑大师

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-154527-1.html