推 EntHeEnd:感謝回答 ! 02/06 17:55
推 yyc1217:請問為什麼每次增加高度的期望值是1/i呢？ 謝謝 02/06 18:51
推 FRAXIS:那網址只是證明第n個插入節點的期望深度 不是樹高 02/06 22:18
※ 引述《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