按秩合并

8 分钟

合并时把“矮”的树挂到“高”的树下,避免树越长越高。用 rank 或 size 记录高度或大小,让根始终是更大的那棵。配合路径压缩,均摊近乎 O(1)(反阿克曼级)。

小纸条

两棵高度相同的树合并后,新树的高度如何变化?

登录 后可看答案

按秩合并 · 算法进阶 · op599 课程