Question

依次输入元素：10，8，16，5，20，7，12，19，试生成一棵二叉排序树。(1) 画出建立的二叉排序树

依次输入元素：10，8，16，5，20，7，12，19，试生成一棵二叉排序树。(1) 画出建立的二叉排序树。(2) 假定每个元素的查找概率相等，计算查找成功时的平均查找长度。

Answer 1

你是要算法还是本题答案？
本题答案为
10
8 16
5 12 20
7 19
算法为：
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）
在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6
= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。 P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n

二叉树
-1
∴ P（n）= ∑ P（n,i）/ n <= 2(1+I/n)lnn
i=0
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)