二叉搜索樹

-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

回答

相關問題