5.5.2.1 并查集的优化
原书定位
印刷页P187起,对应PDF第199页。下文为目视整理的知识提要;完整内容见原书对照。
按规模合并:让较小集合的根指向较大集合的根,更新负大小。每次深度增加时所在集合至少翻倍,因此高度为 。
路径压缩:查根过程中将路径上的结点直接改接到根。结合按规模或按秩合并,一系列操作可达到接近常数的 均摊开销。
这里的逆阿克曼界描述均摊操作复杂度,不能一概说任一时刻的树高都不超过 ;一次查找仍可能走较长路径。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P187起,对应PDF第199页。下文为目视整理的知识提要;完整内容见原书对照。
按规模合并:让较小集合的根指向较大集合的根,更新负大小。每次深度增加时所在集合至少翻倍,因此高度为 。
路径压缩:查根过程中将路径上的结点直接改接到根。结合按规模或按秩合并,一系列操作可达到接近常数的 均摊开销。
这里的逆阿克曼界描述均摊操作复杂度,不能一概说任一时刻的树高都不超过 ;一次查找仍可能走较长路径。

