[理工] [DS] binary search tree height

[winnie48 (winnie)]

想請問 binary search tree 最好的情況下 height = log (n) , 但是 worst case = n
，n 是元素個數。那麼要怎麼證明 random 建立的 binary search tree height = log(n
) ??
實在是不太會這種要考慮到機率的情況，拜託大家解答了！謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419150524.A.BF9.html
→ galapous: CLRS沒記錯的話有，很長
推 FRAXIS: 你要先搞清楚你是要證明什麼..
→ FRAXIS: 是RBST的期望高度為O(lg n)
→ FRAXIS: 還是RBST的高度為O(lg n) with high probability..
→ FRAXIS: 第一種的性質比較弱 證明比較簡單
→ FRAXIS: 第二種就比較難一點 需要用到一些機率不等式..
推 qoojordon: 請問F大,前者(期望高度)是指加入一個點的期望深度嗎?
推 FRAXIS: 不是  你說的又稍微不一樣了..
→ winnie48: 要證明的比較像是期望高度!