二叉搜索树

-2

给出一个算法，以一个最初为空的BST开始，并进行'n'个随机插入。使用一个统一的随机数生成器来获取要插入的值。测量生成的BST的高度并将此高度除以log2n。做这个n = 100,500,1000,2000,3000 ....，10000。绘制比率高度/ log2n作为n的函数。比率应该近似恒定（大约2）。验证是这样的。

我的理解：
现在我们都知道BST的高度是log2n，其中'n'是树中元素的数量。如果它是左倾斜/右倾斜树，则高度相等到'n'。所以，如果我们在这里测量身高，我们应该假设插入的高度是随机的。我的意思是，这个比例怎么可能总是在2.
我对此感到头痛。二叉搜索树

来源

2016-08-28 Reckoner

[这]（https://www.sitepoint.com/hierarchical-data-database-2/）将帮助你 –

如果是左倾斜/右倾斜树，则高度等于'n'。所以，如果我们在这里测量高度，我们应该假设插入的高度是多少

这样的二叉树的高度是n。你不必在这里假设任何东西。此外，完美平衡BST的高度的log（n）（不是一般的）

来到你的问题，我想你问找到高度的随机建立二叉树。在这种情况下，您不必计算任何特定二叉树的高度。

即使偏斜树的高度为n，它在均匀随机分布中产生的可能性也非常小。所以，如果你计算随机BST的高度，它会出现O（log n）。

对于精确的计算，是指Randomly build BST has logarithmic height

来源

2016-08-28 05:15:04

是的，我知道，随机建立BST有对数高度......但我所问的是：比率怎么可能总是接近2 ......仔细阅读我的问题......你有解决方案吗？ – Reckoner

你通过链接了吗？他们已经显示预期的身高= 2 * log（n） –

Yupp我已经经历了它现在.......得到它 – Reckoner

回答

相关问题