作者taitin (小南)
看板Grad-ProbAsk
标题Re: [理工] [资结]台大98-资工
时间Sat Feb 6 17:40:03 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个数中，Xj为第j个插入的数字
则可将数列分成两个数列，仅需讨论已下数列
1.{G|Xj<Xi<root key} 1<=i<=j<=n
2.{L|Xj>Xi>root key} 1<=i<=j<=n (<= 小於或等於)
则 Xj的深度=|G|+|L| 其中|G|,|L|为符合叙述的个数
讨论|G|在ith插入时的期望值
则每次增加高度的期望值为p(Xi)=1/i
依序插入N个值後，可得到总高度为
|G|=p(X1)+p(X2)+...+p(Xn)
=1+1/2+1/3+1/4+...1/n 为一调和数列
=O(logn)
同理可证得，|L|=O(logn)
因此random binary search tree 深度为
|G|+|L|=O(logn)
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic10/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.7.249
1F：推 EntHeEnd:感谢回答 ! 02/06 17:55
2F：推 yyc1217:请问为什麽每次增加高度的期望值是1/i呢？ 谢谢 02/06 18:51
3F：推 FRAXIS:那网址只是证明第n个插入节点的期望深度 不是树高 02/06 22:18