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