知识卡片
并查集取平衡
内容
并查集用父指针树表示连通分量，按大小合并控制树高，路径压缩让后续查找更快。它不是让每次最坏情况都最小，而是通过结构性投资换取长期接近常数的操作成本。
参考来源
- 位置：《你真的会写代码吗-2021》第3章《速度的要求：时间效率》"3.3 最好的平衡：并查集算法（Speed3）"一节（源文件：_epub-src/OEBPS/Text/0013.xhtml）
- 结论依据：原文说明路径压缩"是指将遇到的每个节点都变成根的直接子节点。在遍历树的同时，也修改了树，这可以让未来的操作更加高效"，并指出Speed3并非追求单次最坏情况最优，而是通过摊销分析体现长期接近常数的成本。
- 原始内容：路径压缩技术是指将遇到的每个节点都变成根的直接子节点。在遍历树的同时，也修改了树，这可以让未来的操作更加高效……即使对x.findRootAndCompress()方法的某一次特定调用需要对数时间，路径压缩技术也能确保未来对同一容器上的同一方法的调用……将以常数时间执行。