[問題] randomly built binary search tree

[mqazz1 (無法顯示)]

用 n 個node

隨機建立二元搜尋樹

這顆樹預期的高度是O(lgn)


請問要怎麼證明呢?

我看cormen是擺在12.4節

可是除了cormen用的方法之外

還有別的方法可以證明嗎?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.25.34
推 LPH66:個人覺得再怎麼變都不脫同一條思路: 遞迴地由兩子樹建立全樹