Re: [理工] [資結]-台大98-資工

[FRAXIS (喔喔)]

※ 引述《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
推 EntHeEnd:嗯嗯 感謝回答
→ EntHeEnd:不過我看之前t大的那個証法比較像求最深的點的深度期望值
→ EntHeEnd:耶... 不過照大大您的觀點 請問是錯在哪裡呢...
→ FRAXIS:我沒有說他錯喔 因為推論的過程很長我也沒一一驗證
→ FRAXIS:但是它網頁上面有寫了
→ FRAXIS:if Dn is the depth of the nth inserted node
→ FRAXIS:we will show that the expected value of Dn
→ FRAXIS:is not more than 2+2log(n).
推 EntHeEnd:喔喔...