平均查找长度

平均查找长度=每个结点的深度的总和/总结点数因为在这棵树中：深度为1的结点有1个深度为2的结点有2个深度为3的结点有4个深度为4的结点有3个所以深度总和为1*2+2*2+3*4+4*3 总结点数为10。

平均查找长度(二叉排序树平均查找长度)

二叉排序树平均查找长度

二叉排序树平均查找长度为：ASL=∑（本层高度*本层元素结点个数）/结点总数。

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

二叉排序树相关术语：

1、根节点：根节点是一个没有双亲结点的结点，一棵树中最多有一个根节点。

2、边：边表示从双亲结点到孩子结点的链接。

3、叶子结点：没有孩子结点的结点叫作叶子结点。

4、兄弟结点：拥有相同双亲结点的所有孩子结点叫作兄弟结点。

5、祖先结点：如果存在一条从根节点到结点q的路径，其结点p出现在这条路径上，那么就可以吧结点p叫作结点q的祖先结点，结点q也叫做p的子孙结点。

6、结点的大小：结点的大小是指子孙的个数，包括其自身。

拉链法平均查找长度怎么算

拉链法平均查找长度计算：数组长度10散列函数x%7，如13先计算散列13%7=6，如果没有冲突的话会被放在第六个格子里。

对于含有n个数据元素的查找表，查找成功的平均查找长度：ASL=∑PiCi（i=1，2，3，n），先构造散列表，再将查找到每个关键码的探查次数求和，除以关键码的总个数就是ASL，这个数据序列的结果就是17/12。

基本概念

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。

Hash表的平均查找长度

Hash表的平均查找长度

Hash表的平均查找长度包括查找成功时候的平均查找长度和查找失败时候的平均查找长度。

查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。

分块查找平均查找长度计算公式是什么

设关键字个数为n，在各关键字等概率查找的前提下，

1、顺序查找的平均查找长度ASL=(n+1)/2，

2、在n趋于无穷大时，折半查找的ASL=((n+1)log2(n+1))/n - 1，当n大于50时，ASL约等于log2(n+1)-1

3、设分块查找中将长为 n 的表分成均等的 b 个块，每块 s 个元素，则 b = (n / s)上取整，如果索引表中采用顺序查找，则ASL=(b+1)/2+(s+1)/2；如果索引表中采用折半查找，则ASL=(s+1)/2+log2(b+1)-1

平均查找长度与时间复杂度的区别

平均查找长度，在查找过程中一次查找的长度是指需要比较的关键字次数，而平均长度则是所有查找过程中进行关键字的。比较次数的平均值。

时间复杂度一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和即为tn，它是该算法问题规模n的函数。时间复杂度主要分析tn的数量级算中基本运算的平度。与tn同数量级，因此通常采用算法中基本运算的频度fn来分析时间复杂度。