约 8 分钟
合并时把“矮”的树挂到“高”的树下,避免树越长越高。用 rank 或 size 记录高度或大小,让根始终是更大的那棵。配合路径压缩,均摊近乎 O(1)(反阿克曼级)。
两棵高度相同的树合并后,新树的高度如何变化?
登录 后可看答案