[理工] 資結 union-by-height和simple-find

看板Grad-ProbAsk作者 (chiu)時間6年前 (2017/11/12 01:23), 編輯推噓0(0推 0噓 7→)
留言7則, 3人參與, 6年前最新討論串1/1
https://i.imgur.com/d0HmD0g.jpg
想問為什麼樹高頂多是O(log n)? 謝謝大家~~>< -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.10.188 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510420983.A.EFB.html
→
11/12 01:55, 6年前 , 1F
思考如何輸入能使樹高增加，再想對應的點數應該很明顯
11/12 01:55, 1F
→
11/12 14:17, 6年前 , 2F
不好意思還是不太懂><可以說明一下嗎？謝謝!!
11/12 14:17, 2F
→
11/12 21:57, 6年前 , 3F
最好的狀況是：一個當root，其他當子點，level=2
11/12 21:57, 3F
→
11/12 21:57, 6年前 , 4F
最壞的情況是：兩兩Union，每次Union樹高加一，8
11/12 21:57, 4F
→
11/12 21:57, 6年前 , 5F
個數Union，level=4，16 個數Union，level=5.....近
11/12 21:57, 5F
→
11/12 21:57, 6年前 , 6F
似log n
11/12 21:57, 6F
→
11/13 00:58, 6年前 , 7F
喔喔喔懂了~~謝謝><><!!
11/13 00:58, 7F
‣ 更多 q5332159 的文章
文章代碼(AID): #1Q1p7txx (Grad-ProbAsk)