推 winnie48: 非常謝謝你! 12/22 08:45
→ winnie48: 我再依照這些提示想想看! 12/22 08:48
※ 引述《winnie48 (winnie)》之銘言：
: 想請問 binary search tree 最好的情況下 height = log (n) , 但是 worst case = n
: ，n 是元素個數。那麼要怎麼證明 random 建立的 binary search tree height = log(n
: ) ??
: 實在是不太會這種要考慮到機率的情況，拜託大家解答了！謝謝！
給定 n 個元素為插入 BST 的元素集合。
假設插入BST的順序是均勻隨機分布。
此時建出來的樹 T 本身就是一個隨機物件。
那T的高度 Height(T) 也是一個隨機變數
所以 Height(T) 的期望值就是期望高度 = E[Height(T)]
可以證明為O(lg n)。
但是這性質很弱，因為他只證明期望值，沒有提供concentration。
所以需要一個比較強的性質，像是
Pr(Height(T) > c * lg n) = o(1)
也就是，T的高度大於 c * lg n的機率很小。
不過這證明起來比較麻煩。
插入的期望深度又稍微不一樣，要看你怎麼定義插入的東西。
令D(x, T)表示把 x 插入到 T 的深度。
如果插入的元素是任意的，討論worst case。
你是在找 Max_x E[D(x, T)]，注意這時候T是隨機變數。
Max_x E[D(x, T)]應該頂多比 E[Height(T)] 多一而已。
如果插入的元素是隨機的（你要先定義好隨機的意義是什麼）
你是在找 Avg_x E[D(x, T)]，不過這數值不可能大於Max_x E[D(x, T)]
舉例來說，令 T 中的元素是 a1, ..., an, 且ai <ai+1，
假設隨機的意義是 x 在 ai和ai+1中間的機率是均等的 for all i。
此時Avg_x E[D(x, T)] 必定會小於 Max_x E[D(x, T)]。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419175248.A.D98.html