本系列博客習(xí)題來自《算法(第四版)》商乎，算是本人的讀書筆記，如果有人在讀這本書的祭阀，歡迎大家多多交流鹉戚。為了方便討論，本人新建了一個微信群(算法交流)专控，想要加入的抹凳，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外伦腐，本人的個人博客 http://www.kyson.cn 也在不停的更新中赢底，歡迎一起討論
算法(第4版)
知識點
- 路徑壓縮
題目
1.5.14 根據(jù)高度加權(quán)的 quick-union 算法。給出 UF 的一個實現(xiàn)蔗牡，使用和加權(quán) quick-union 算法相同的策略颖系，但記錄的是樹的高度并總是將較矮的樹連接到較高的樹上嗅剖。用算法證明 N 個觸點的樹的高度不會超過其大小的對數(shù)級別辩越。
1.5.14 Weighted quick-union by height. Develop a UF implementation that uses the same basic strategy as weighted quick-union but keeps track of tree height and always links the shorter tree to the taller one. Prove a logarithmic upper bound on the height of the trees for N sites with your algorithm.
