在一棵深度为h的具有n个元素的二叉排序树,查找所有元素的最长查找长度为？

Question

A:n
B:log2n
C:(h+1)/2
D:h

Answer 1

在一棵深度为h的具有n个元素的二叉排序树,查找所有元素的最长查找长度为h。

从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂性大致为O(log2n)。

从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂性为O(n)。

扩展资料：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；

（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

参考资料来源：百度百科-二叉排序树

Answer 2

O(log2(n))是时间复杂度,而二叉排序树查找成功的平均查找长度为: ASL = [(n+1)/n] * log2(n+1) - 1推导过程如下:假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,假设也是满二叉树, n与h的关系, 有公式: n = (2^h) - 1 也就是: h = log2(n+1)对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:ASL = (1*1 + 2*2) / 3对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:ASL = (1*1 + 2*2 + 3*4) / 7对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:ASL = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) / n [等式1]对于[等式1]里的1*1 + 2*2 + 3*4 + ... + h*2^(h-1)该数列有h项: 1*2^0, 2*2^1, 3*2^2, ... , h*2^(h-1)其总和S = 1*2^0 + 2*2^1 + 3*2^2 + ... + h*2^(h-1) [等式2]等式两边同乘以2,有: 2*S = 1*2^1 + 2*2^2 + 3*2^3 + ... + (h-1)*2^(h-1) + h*2^h [等式3]用[等式3]减去[等式2]有:S = h*2^h - (2^0 + 2^1 + 2^2 + 2^3 + ... + 2(h-1)) [等式4]其中(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))是等比数列求和,设: M = (2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))等式两边同乘以2,有: 2*M = (2^1 + 2^2 + 2^3 + ... + 2^h)两个等式相减,有: M = 2^h - 1将M代入[等式4]有: S = h * 2^h - (2^h - 1) = (h-1) * 2^h + 1 [等式5]因为 h = log2(n+1),将h代入[等式5],有:S = [ log2(n+1) - 1 ] * 2^[log2(n+1)] + 1 = [ log2(n+1) - 1 ] * (n+1) + 1 = (n+1) * log2(n+1) - n也就是 S = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) = (n+1) * log2(n+1) - n将上述S代入[等式1],有: ASL = [(n+1) * log2(n+1) - n] / n = [(n+1)/n] * log2(n+1) - 1所以,二叉排序树查找成功的平均查找长度为: ASL = [(n+1)/n] * log2(n+1) - 1 [公式1]其时间复杂度是: O(log2(n))假设有一颗平衡的二叉排序树,高度h=4,总结点数n=11,不是满二叉树: 36 / \ 24 52 / \ / \ 10 30 41 90 / \ / / 8 12 38 61根据[公式1],查找成功的平均查找长度为:ASL = [(n+1)/n] * log2(n+1) - 1 = [(11+1)/11] * log2(11+1) - 1 约等于 2.91逐个结点计数,平均查找长度为:ASL = (1*1 + 2*2 + 3*4 + 4*4) / 11 = 33 / 11 = 3假设有一颗平衡的二叉排序树,高度h=4,总结点数n=15,是满二叉树: 36 / \ 24 52 / \ / \ 10 30 41 90 / \ / \ / \ / \ 8 12 28 31 38 42 61 91根据[公式1],查找成功的平均查找长度为:ASL = [(n+1)/n] * log2(n+1) - 1 = [(15+1)/15] * log2(15+1) - 1 = 49/15逐个结点计数,平均查找长度为:ASL = (1*1 + 2*2 + 3*4 + 4*8) / 15 = 49/15本回答被网友采纳

Answer 3

D
就是折半查找，先和根节点比较大的在右，小的在左，依次下去，最后查找到的肯定是叶子结点，最长的是叶子结点最远的，自然就是最深的，所以是深度