5

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

4

7 回答 7

10

这个问题让我问你是否可以在不实际生成树的情况下明确解决这个问题。

我设法编写了一个应用程序，如果您将 N 个唯一数字的所有可能排列添加到一个简单实现的二叉树中，它可以计算出平均高度的答案。

我得到的答案在这张图中。（X 轴是树中的项目数，蓝线是平均高度，红线是可能的最佳高度）

平均高度到最小高度的图表

N 平均高度
2 2
16 7.039
32 9.280
64 11.679
256 16.783
343 17.896

Granitebolshevik 是对的：如果没有额外的平衡功能，一个简单实现的树可能会成为最佳高度，但在统计上不太可能。

该算法的复杂度为 O(N^2)，计算速度不够快，无法计算出非常大的数字。

于 2009-05-18T10:30:03.063 回答
4

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

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

凭经验测量这种树的平均高度的一种方法是重复创建一棵空树并向其添加 1000 个随机项。使用上述功能测量每个试验的高度，并将它们平均。

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

于 2009-05-14T03:19:44.147 回答
4

这取决于您是否使用任何类型的平衡树结构（例如红黑树）。由于您将随机数插入二叉树，因此可以合理地预期平均深度约为 log2(1000) - 因此值 10 和 11 将是“正常的”。我不确定它会偏离多远。不低于 10 层，可能更深一些。没有平衡的极端情况是 1000 深；随机数不太可能发生这种情况。

于 2009-05-14T03:22:46.277 回答
3

这个问题似乎没有一个简单的答案，尽管有许多数字近似值，例如：

Devroye，卢克。“关于二叉搜索树高度的注释。” ACM 杂志 (JACM) 33.3 (1986): 489-498。

里德，布鲁斯。“随机二叉搜索树的高度。” ACM 杂志 (JACM) 50.3 (2003): 306-332。

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm

这些近似值通常采用以下形式：A ln n - B ln ln n + C

地点A~4.311和地点B~1.953

所以最有用的可能是随机插入的平均高度是O(log n)，但如果你真的需要一个数值近似值，我认为(4.311 ln n - 1.953 ln ln n)对于大的 n 来说已经足够接近了。

对于n=1000，这给出了大约26- 非常适合其他地方报告的实验结果。

于 2013-03-25T06:31:18.610 回答
1

这个问题其实很棘手。答案不会是 1000，因为这是不可能的，但 log2(1000) 也是不可能的，但更不可能取决于树的生长方式。

如果您通过单步执行树来添加一个 int，然后天真地附加它，那么树实际上总是比 log2(1000) 高。

与统计学家交谈，因为这似乎与正态概率分布有关。这些是由许多迭代的随机事件生成的（头部向右一个单位，向左一个单位的尾部），并且随机整数的值在树中迭代，因为它稳定到叶子中。

于 2009-05-14T04:53:12.003 回答
0

这取决于添加的顺序。如果从最小值开始，那么树会更深，因为所有新值都将添加到右子 BST。如果你先添加最大值，那么左边的孩子会很深，而右边的孩子会是空的。

于 2009-05-14T03:18:37.517 回答
-2

正如之前有人提到的，无论您使用什么树，平均高度都是 log2(1000)。确实，根据插入的数字的顺序，实际高度可能会有所不同，但是假设您提到的随机分布的数字，那么实际值通常会接近预期值（这又是 log2 (1000))

于 2009-05-14T04:38:08.093 回答