二叉搜索树的平均高度

Question

添加1000个随机整数时,如何计算二叉搜索树的平均高度？平均身高是多少？

Answer 1

这个问题让我问你是否可以在没有实际产生树木的情况下明确地解决这个问题.

我设法编写了一个应用程序,可以计算出如果你将N个唯一数字的每个可能的排列添加到一个天真实现的二叉树中的平均高度的答案.

我得到的答案都在这张图中.(X轴是树中的项目数,蓝线是平均高度,红线是最佳可能高度)

N     Average Height
2     2
16    7.039
32    9.280
64    11.679
256   16.783
343   17.896

Granitebolshevik是对的:它是可能的,但在统计上不太可能一个天真实施的树将是最佳高度,没有额外的平衡功能.

该算法的复杂度为O(N ^ 2),并且计算真正的大数字的速度还不够快.

Answer 2

您可以使用以下递归定义计算二叉树的高度：

height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))

凭经验测量此类树的平均高度的一种方法是重复创建一棵空树并向其中添加 1000 个随机项。使用上述函数测量每次试验的高度，并取平均值。

我怀疑你的任务可能是找到二叉树平均高度的公式。