※ 引述《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