4.Union/Find operation: Show that a tree obtained by applying the
weighting rule for Union is bounded above by O(log n).
我看到98年交大资联的题目




103这题是指画出上面那棵树那样吗?
还是写说哪种树符合题目所描述的意思??
我不太懂要如何写这题

我猜是要证根据union weight rule建立出来的树高度（搜寻成本）=O(log n)

Union by weighting rule_K子树接P点为新ROOTCollaping rule(compression)_沿X寻找的node改指向root

我的想法是b-tree是union by weight的worst case，而b-tree高度是log n来当上界，没完整严谨思考，提出来讨论。

这题应该只是要我们做一次union和find就结束了吧证明树高的话应该可以用node数量做强归纳法，但这不是原题的题意

其实我没搞懂原po要问的是文字叙述的那题还是图片的

我是写说Binomail Heap in worst case合并时间O(1)最多有logN棵树 所以为logN

看到楼上推文我发现我上面推错了，*b-tree -> binomial tree

这题果断放弃...考amortization algo?(配分9分,)照JoJo感觉可能有点笔墨分数XD 看教授了..

" target="_blank" rel="nofollow">
wiki上有说明..