通過大小和路徑壓縮聯合設置不相交集合;更高的樹可能成爲短樹的子樹嗎？

Question

你好，這是我第一次在這裏發帖，

我一直在試圖找出一個問題來研究，但一直沒能弄明白：

我們認爲disjoint-的森林實現設置抽象數據類型，按大小和路徑壓縮加權聯合。最初，每個元素都在一個節點樹中。

從上述初始狀態開始：

1. 給UNION的（短）序列並找到操作，其中最後的操作是一種使高樹甲成爲較短的該子樹的UNION樹B（即A的高度嚴格大於B的高度）。

2. 顯示兩棵樹A和B，最後UNION合併

提示：你可以從n個開始= 9個元素，每一個在一個單節點樹。

---

我不確定這是怎麼工作的，因爲較小的樹總是與大樹合併，因爲按大小合併？

謝謝。

Answer 1

我不想回答你的功課，但這個問題已經夠老了，你的學期可能會結束，並且無論如何一個提示應該有足夠的幫助。

有主要路徑壓縮的，因爲大小和工會聯盟之間的區別通過高度。具體而言，路徑壓縮會導致非常高度的節點，因此具有許多節點但高度非常短的樹。例如，這些都是你可以與工會建立兩棵樹找到路徑壓縮：

|T1: o (n=5, h=2) 
| /| |\ 
| o o o o 
|  
|T2: o (n=4, h=3) 
|  /| 
| o o 
|  | 
|  o 

如果一個操作是這兩種樹木中，「工會按職級」的合併和「工會的高度」算法會選擇不同的父母。

實際上，通常使用「按等級結合」。秩是可以在恆定時間內更新的高度的上限，併產生最佳的漸近運行時間。網絡搜索會產生很多關於該算法的很好的解釋。