按秩合并

一句话理解

按秩合并且把矮的挂到高的下面。

为什么要学

避免退化成链。

讲解

秩近似高度或用集合大小。和路径压缩一起，复杂度 Ackermann 反函数，近乎常数。

例子

小树挂大树，深度增加更少。

常见错误

• 按秩和路径压缩同时用时秩不再是精确高度，仍可当上界。
• 把大树挂小树下面。