作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] [資結]-台大98-資工
時間Sun Feb 14 12:10:48 2010
※ 引述《EntHeEnd (...)》之銘言：
: Prove that the average height of the BST after inserting n integer values
: {1,2,...,n}in a random order is O(log n)
: 請問這題要怎樣證呢 ?
這題要按照定義來做。
之前版上的作法是證明第n個節點插入時候的深度的期望值，雖然也是O(lg n)，
我想兩者並不等價，因為該節點未必會增加樹高，有可能是插在靠近root的地方。
很多書上也有證明隨機插入n個節點之後，每個節點深度的期望值，也是O(lg n)，
但是也不是這題要的。
假設X(n)是隨機插入n個節點之後的期望高度。
按照定義，一個樹的高度是1 + Max(左子樹高度, 右子樹高度)
如果root是第i大的整數，在這種條件下樹的期望高度就是
1 + Max(X(i-1), X(n-i))
又插入的順序是隨機的，所以root是第i大的機率是1/n
n
因此 X(n) = (1/n)Σ 1 + Max(X(i-1), X(n-i))
i=1
然後解遞迴，就可得到X(n)的Closed Form。
話雖如此，但是分析很複雜
（
http://en.wikipedia.org/wiki/Random_binary_tree#The_longest_path）
不過這題只是要求一個上限值，所以也不用去解開。
按照Cormen書上的方法，必需要用多一個隨機變數Y(n) = 2^X(n)
（我想大概是沒有其他簡單的辦法吧）
root是第i大的整數的時候，Y(n) = 2 * Max( Y(i-1), Y(n-i))
所以可得遞迴關係式
n
Y(n) = (2/n)Σ Max( Y(i-1), Y(n-i))
i=1
n
<=(2/n)Σ Y(i-1) + Y(n-i)
i=1
n-1
<=(4/n)Σ Y(i)
i=0
接下來就用一般方法解開，是一個多項式。X(n) = lg Y(n) = O(lg n)
（省略了很多細節，不過大致上是如此，想要看嚴謹的證明就看書吧）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 EntHeEnd:嗯嗯 感謝回答 02/14 12:44
2F：→ EntHeEnd:不過我看之前t大的那個証法比較像求最深的點的深度期望值 02/14 13:28
3F：→ EntHeEnd:耶... 不過照大大您的觀點 請問是錯在哪裡呢... 02/14 13:30
4F：→ FRAXIS:我沒有說他錯喔 因為推論的過程很長我也沒一一驗證 02/14 14:13
5F：→ FRAXIS:但是它網頁上面有寫了 02/14 14:13
6F：→ FRAXIS:if Dn is the depth of the nth inserted node 02/14 14:14
7F：→ FRAXIS:we will show that the expected value of Dn 02/14 14:14
8F：→ FRAXIS:is not more than 2+2log(n). 02/14 14:15
9F：推 EntHeEnd:喔喔... 02/14 14:17