※ 引述《taitin (小南)》之銘言：
: ※ 引述《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同時有大於和小於root兩種情況呢
是分成兩個case討論嗎 ?
: 則 Xj的深度=|G|+|L| 其中|G|,|L|為符合敘述的個數
: 討論|G|在ith插入時的期望值
: 則每次增加高度的期望值為p(Xi)=1/i
請問插入第i的點 增加高度的期望值為什麼是1/i呢
是因為第i個點要插入時 會有i個可能(目前null pointer數)嗎...
然後最後會在最長path的只有其中一個leaf 所以機率是1/i嗎
可是這樣想也怪怪的...
因為是BST那第i個key值要插入 應該不會有i個選擇才對...
或者說是第i個key值 是random number 可是在key range有所限制
前i-1個key值造出來的BST 對第i個選出來的key值的插入位置不會有所限制嗎... ?
我看網頁中他是說p(Xi)是第i個點在最長path中的機率吧
然後path中的點又分成兩個set
一個是key值小於最長path的最後點
一個是key值大於最長path的最後點
這樣插入第i點分兩個set討論
是要怎樣討論呢 不是很懂orz... P(Xi)=1/i 比較像一起討論的機率耶...
: 依序插入N個值後，可得到總高度為
: |G|=p(X1)+p(X2)+...+p(Xn)
: =1+1/2+1/3+1/4+...1/n 為一調和數列
這邊就無法理解 他是說插入的第一個點是root 所以必在path中
所以p(X1)=1吧
可是第一個點要怎樣用分成兩個sublist的情況討論...
所以我會覺得他這個算法比較像一次整個考慮第i點屬於
up-records 或屬於 down-records的機率耶...
看不是很懂...
: =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: 59.126.125.176
※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/06 21:05)