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