4.Union/Find operation: Show that a tree obtained by applying the
weighting rule for Union is bounded above by O(log n).
我看到98年交大資聯的題目
http://i.imgur.com/lqUZ8S8.jpg
http://i.imgur.com/yGbYogn.jpg
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 看教授了..

http://ppt.cc/piGR wiki上有說明..