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

[q5332159 (chiu)]

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
→ sarsman: 思考如何輸入能使樹高增加，再想對應的點數應該很明顯
→ q5332159: 不好意思還是不太懂><可以說明一下嗎？謝謝!!
→ htc018220: 最好的狀況是：一個當root，其他當子點，level=2
→ htc018220:       最壞的情況是：兩兩Union，每次Union樹高加一，8
→ htc018220:  個數Union，level=4，16 個數Union，level=5.....近
→ htc018220: 似log n
→ q5332159: 喔喔喔懂了~~謝謝><><!!