树、森林——树与二叉树的应用（并查集的优化）

一、为什么要优化？
不优化的并查集，树会变得又高又瘦查找祖先速度变慢，最坏退化成链表，时间复杂度 O (n)
所以必须两大核心优化：
路径压缩（查找优化）
按秩合并（合并优化）

1、路径压缩 Find 优化
原理
查找某个结点根结点时把沿途所有结点，直接指向根结点让树变得极度扁平
效果
树层数大幅减少
下次查找一步到位
查找效率几乎 O (1)
递归代码

int find(int x){ if(parent[x] != x) parent[x] = find(parent[x]); //路径压缩 return parent[x]; }

一句话：爷变爹，一路直达根

2、按秩合并 Union 优化
秩 = 树的高度 / 集合结点个数
原理
合并两棵树时矮树的根 挂在 高树的根下面不让树越长越高
树高低 → 小树挂大树
结点少 → 小集合挂大集合
作用
保持树始终短小平衡，不会退化

二、双优化后复杂度
路径压缩 + 按秩合并时间复杂度：阿克曼反函数 α(n)可以理解为常数级 O (1)

三、考点简答总结
路径压缩：优化查找，扁平化树形结构
按秩合并：优化合并，保持树平衡低矮
单独路径压缩：效率极高，但树高度不稳定
单独按秩合并：树平衡，但查找不够快
两者结合 = 并查集最优实现

四、一句话口诀
查找路上路径压，合并高矮不瞎挂，树矮扁平速度快，近乎常数顶呱呱。