素集合データ構造
Findで根ノードまでのリンクをたどっているとき、各ノードは同じ代表を共有しているので、それらを根ノードに直接接続できる。このため、Find は再帰的にたどったノードが全て親ノードとして根ノードを指すように変更する。こうすると木構造はより平坦になり、その後の操作が高速化される。以下に Find の改良版を示す。
これらの手法は相補的であり、これを共に行うことで各操作の償却実行時間は O ( α ( n ) ) {\displaystyle O(\alpha (n))} となる。ここで α ( n ) {\displaystyle \alpha (n)} は関数 f ( n ) = A ( n , n ) {\displaystyle f(n)=A(n,n)} の逆であり、 A {\displaystyle A} は非常に高速に大きな値になるアッカーマン関数である。 α ( n ) {\displaystyle \alpha (n)} はその逆関数なので、実用的な n {\displaystyle n} の値に対しては常に 5 未満の値になる。したがって、各操作の償却実行時間は事実上非常に小さな定数となる。
実際、これは漸近最良である。Fredman と Saks は1989年、どのような素集合データ構造でも1回の操作あたり平均で Ω ( α ( n ) ) {\displaystyle \Omega (\alpha (n))} のノードにアクセスするとした。