二叉树查找的平均查找长度是怎样的？
对于11个节点，其构成的二叉树成功的查找长度是
(1x1+2X2+3x4+4x4)/11=33/11
失败的查找长度是
(4x8+3x4)/(8+4)=44/12
举个例子吧。假定数组中的成为二分查找数的内节点，然后补上叶子节点代表查找失败的。 比如只有一个节点a。那么成功的查找会是 1X1/1=1 ，一次比较，高度为1，处以内节点数目。失败的查找应该是不等于1的，还需要两次查找，分别是左右叶子节点，1X2/2=1。
如果是两个节点，假设a和b，并且不失一般性，设b为a的左节点，那么b的两个叶子节点代表失败情况，需要2次查找，a还有一个右节点代表失败情况，需要一次查找，（2X2+1X1）/3=5/3
依次类推就可以了。
平均查找长度与查找表中元素个数 n 无关的查找方法是
顺序查找成功的平均查找长度为 （n+1）\/2 折半查找的为 ((n+1）\/2)*log2(n+1)-1 索引顺序查找为 (((n\/s)+s)\/2)+1 备注：s为表分块后每一块的记录个数 二叉树查找类似于折半查找，哈希（hash）查找应该是无关的
计算各种查找方法在等概率情况下查找成功时的平均查找长度
顺序查找：O(n)折半查找：O(log2n)分块查找：大致 O(n^0.5)二叉排序树：介于O(log2n)和O(n)之间 平衡二叉树：O(log2n)m阶B-树：O(logmn)散列或者音译哈希平均查找长度与结点个数无关的查找方法，ASL的理论值只与装填因子有关
二叉树查找问题
查找二叉树用折半查找法，该方法优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成...
二叉树和hash哪个查找效率更高
原则上来说是hash的查找效率更高。针对具体的情况则不尽然。首先单纯的二叉树的查找效率是不高的，等于是无序数组的遍历，需要转变成二叉排序树或者二叉平衡树才能提升查找效率，查找平均效率为O（logn）。其次hash的映射冲突的发生概率对hash的查找效率影响较大，在映射冲突较小的情况下平均查找效率为O（...
二叉排序树和平衡二叉树效率比较
1、就查找的平均时间性能方面，二叉排序树上的查找与折半查找类似。2、就维护表的有序性方面，二叉排序树更高效，无需移动节点，只需修改指针即可完成二叉排序树的插入和删除操作。
二叉树节点平均查找次数是什么?
2lnN 大概是 1.39lgN
以二分查找方法从长度为7的有序表中查找一个元素时,平均查找长度...
平均查找长度：（1+ 2*2 + 3*4 ）\/ 7 = 17\/7 画一个二叉树 0 \/ \\ 0 0 \/ \\ \/ \\ 0 0 0 0 二分查找，第一层需要比较1次，第二层2个，比较2次，第3层4个比较3次。
...在等概率情况下,查找失败和成功时的asl(平均查找长度)是多少啊...
查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：ASLbn≈lg(n+1)-1 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：二分查找的最坏性能和平均性能相当接近。
队列与二叉树与栈与hash哪个查找效率最高
队列，栈都是不利于查询的逻辑结构，因为他们的元素都需要伴随入队出队，入栈出栈等操作约束来进行元素的遍历，这种遍历显然都是低效的。二叉树本身的查询效率并不高，需要使用二叉排序树或者二叉平衡树才能提升查找效率，在二叉平衡树中查找的平均效率大约是O（logn）。hash是查找效率相对最高的方法，如果...
折半搜索与二叉排序树的时间性能
两者的时间性能如下：1、折半搜索：折半搜索算法适用于有序数组。它通过不断将搜索区间分成两半来缩小查找范围。折半搜索的平均时间复杂度是O(log n)，其中n是数组中的元素数量。2、二叉排序树：二叉排序树是一种特殊的二叉树，其中每个节点的左子树包含小于该节点的值，右子树包含大于该节点的值。在...
势宋天苏：[答案] 二楼正解 最坏情况是深度为N的单支树为(N+1)/2 最好的是形态均匀和折半查找一样大约为 LOG2 N PS:若构造完成,例: 则平均查找长度为:(1*1+2*2+3*4+4*3)/10=2.9
华坪县17523758716： 设一组初始记录关键字序列为(20,12,42,31,18,14,28),则根据这些记录关键字构造的二叉排序树的平均查找长度是 - ？
势宋天苏：[答案] 平均查找长度是19/7
华坪县17523758716： 数据结构 填空题目 二叉排序树的平均查找长度设一组初始记录关键字序列为(20,12,42,31,18,14,28),则根据这些记录关键字构造的二叉排序树的平均查找... - ？
势宋天苏：[答案] 先构造二叉排序树,然后计算就行了: (2*3+2*2+2)/7=1.7
华坪县17523758716： 二叉排序树的不成功的平均查找长度怎么求? - ？
势宋天苏： 按二叉树的公式求.1.就你的BST,结果如下:15的左右子树都为空,也就是左右子树都是外结点,失败时需要比较62、30、15一共3次. 2.48的左右子树都为空,也就是左右子树都是外结点,失败时需要比较62、30、15、48一共4次. 3.56的右子树为空,也就是右子树是外结点,失败时需要比较62、30、56一共3次. 4.74的左右子树都为空,也就是左右子树都是外结点,失败时需要比较62、74一共2次. 5.因此外结点总数为2 *3 + 1 = 7 (其实这个数量一定是关键字个数加1). 6.所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3.
华坪县17523758716： 给定数据序列d={7,16,4,8,20,9,6,18,5},构造一棵二叉排列数,并求出该二叉排列树查找成功的平均查找长度 - ？
势宋天苏： 7 / \ 4 16 \ / \ 6 8 20 / \ / 5 9 18 平均查找长度=1*1+2*2+3*3+4*3=26(第一层一个结点,每个结点比较一次查找成功;第二层两个结点,每个结点比较两次查找成功;第三层三个结点,每个结点比较三次查找成功;第四层三个结点,每个结点比较四次查找成功)
华坪县17523758716： 1.设有序列(45、24、53、12、28、90),请构成一棵二叉排序树,并求其查找成功时的平均查找长度. - ？
势宋天苏： .............4524 5312 28 90 平均时间=1/6(1+2*2+3*3)=7/3
华坪县17523758716： 给定数据序列d={7,16,4,8,20,9,6,18,5},构造一棵二叉排列数,并求出该二叉排列树查找成功的平均查找长度 - ？
势宋天苏： 7 / \ 4 16...
华坪县17523758716： 如何计算二叉排序树的平均长度 - ？
势宋天苏： 一般说来是求的平均成功查找长度,它的值=所有结点高度之和/结点的个数.
华坪县17523758716： 二叉排序树 成功的平均查找长度怎么求 - ？
势宋天苏： 我感觉,二叉排序树的平均查找长度,与构造的,二叉排序树的形态有关,所以这道题的答案应该不是唯一的吧. 满意请采纳.
华坪县17523758716： 数据结构题目高手来？
势宋天苏： 平均查找长度就是log(n),其中以2为底,n是节点总数.因为这里平均查找长度就是log8 = 3
