脫節以特殊方式設置？

我們用樹實現了Disjoint Data結構。在這個數據結構makeset()中創建一個具有一個元素的集合，merge(i, j)合併兩棵樹集合i和j，使得高度較低的樹成爲第二棵樹的根的孩子。如果我們以隨機方式做nmakeset()操作和n-1 merge()操作，然後做一個查找操作。在最壞的情況下，查找操作的成本是多少？脫節以特殊方式設置？

I) O(n) 
II) O(1) 
III) O(n log n) 
IV) O(log n)

答案：IV。

任何人都可以提到一個很好的提示，作者得到這個解決方案？當您使用工會通過排名（又稱加權工會）

來源

2016-05-15 Maryam Koj

您能否提供此聲明的來源？ – amit

有一個錯字，我糾正它。這是一個本地考試，並已掃描文檔。 @amit –

我認爲答案是aaaa – user3661613

的O（log n）的發現僅僅是真實的。當我們使用這個優化時，我們總是把排名較低的樹下的樹放在樹的根下。如果兩者具有相同的等級，我們任意選擇，但是將得到的樹的等級增加1。這給出了一個O（log n）在樹的深度上的界限。那就是根我水平以下的節點（相當於秩的樹是> = 我）是在至少2 ^我節點樹我們可以顯示證明這一點（這是與展示尺寸爲的樹相同，其具有的尺寸爲具有日誌n深度）。這很容易通過感應來完成。

Induction hypothesis: tree size is >= 2^j for j < i. 
Case i == 0: the node is the root, size is 1 = 2^0. 
Case i + 1: the length of a path is i + 1 if it was i and the tree was then placed underneath 
      another tree. By the induction hypothesis, it was in a tree of size >= 2^i at 
      that time. It is being placed under another tree, which by our merge rules means 
      it has at least rank i as well, and therefore also had >= 2^i nodes. The new tree 
      therefor has >= 2^i + 2^i = 2^(i + 1) nodes.

來源

2016-05-15 20:15:06

有一個不錯的解決方案+1，但我認爲這裏有一個錯字 – user3661613

對不起，這個問題沒有說按級別結合，說事情不同。不是嗎？ –

@MaryamKoj：你說你合併時把高度較低的樹放在高度較低的樹下。這正是所謂的_union by rank_（_rank_永遠是任何葉子的最深層次）。 –

脫節以特殊方式設置？

回答

相關問題