[理工] [DS] binary search tree height
想請問 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
→
12/21 19:21, , 1F
12/21 19:21, 1F
推
12/21 22:17, , 2F
12/21 22:17, 2F
→
12/21 22:18, , 3F
12/21 22:18, 3F
→
12/21 22:18, , 4F
12/21 22:18, 4F
→
12/21 22:19, , 5F
12/21 22:19, 5F
→
12/21 22:20, , 6F
12/21 22:20, 6F
推
12/21 22:45, , 7F
12/21 22:45, 7F
推
12/21 22:58, , 8F
12/21 22:58, 8F
→
12/22 08:40, , 9F
12/22 08:40, 9F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：