添加 1000 个随机整数时,如何计算二叉搜索树的平均高度?平均身高是多少?
这个问题让我问你是否可以在不实际生成树的情况下最终解决这个问题。
我设法编写了一个应用程序,如果您将 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),并且速度不够快,无法计算真正大的数字。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)