※ 引述《EntHeEnd (...)》之銘言：
: ※ 引述《taitin (小南)》之銘言：
: : 假設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討論嗎 ?
抱歉這邊錯了，應該要修正成
1.{G|for all Xi;Xk>Xi>Xj;1<=k<=i<j<=n}
2.{L|for all Xi;XK<Xi<Xj;1<=k<=i<j<=n} (<= 小於或等於)
G的意思是，所有在位置j之前，Xk為key值大於Xj的數字
而Xi，為Xk到Xj中所有符合的數字
例如： 21 9 4 25 8 19 29 17 5 6 4 30
若Xj選定為 17
則Xk可為21 25 19 29 >Xj的數字 且k<j
又Xi必須在 21<Xi<17，之間，故為21 19
簡單說就是數列中，大於Xj的數字且成遞減排序
L恰好相反
數列中，小於Xj的數字且成遞增排序
: : 則 Xj的深度=|G|+|L| 其中|G|,|L|為符合敘述的個數
: : 討論|G|在ith插入時的期望值
: : 則每次增加高度的期望值為p(Xi)=1/i
: 請問插入第i的點 增加高度的期望值為什麼是1/i呢
就討論G中，要使XK>Xi>Xj，及討論，Xj為最小值的機率
因此，在1~j中，j恰為最小值的機率就是1/j
然而，這跟j位在第幾個位置有關係，可以肯定的是，j以後的數字完全不用考慮
因此依照j可能在的位置的期望值，可知道p(Xj)=1/j
又j在每個位置的機率相同，因此總共的期望值就變成
|G|=p(X1)+p(X2)+...+p(Xn)
: 是因為第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: 61.230.227.76