作者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