Union działa w tej implementacji tak samo szybko). Są jednak dwie techniki znacznie poprawiające złożoność:
Pierwsza, zwana łączeniem według rangi, polega na dołączaniu mniejszego drzewa do korzenia większego drzewa. Dla oceny, które drzewo jest większe, używamy heurystycznego sposobu zwanego rangą: pojedynczy element drzewa ma rangę zero, a kiedykolwiek łączymy dwa drzewa o równej randze rangę powstałego drzewa ustalamy na
Z tą poprawką złożoność obu operacji wynosi Odpowiedni pseudokod wygląda tak:
function MakeSet(x) x.parent := null x.rank := 0
function Union(x, y) xRoot = Find(x) yRoot = Find(y) if xRoot.rank > yRoot.rank yRoot.parent := xRoot else if xRoot.rank < yRoot.rank xRoot.parent := yRoot else if xRoot == yRoot yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1
Drugie udoskonalenie, zwane kompresją ścieżki, polega na spłaszczaniu struktur drzewa zawsze, kiedy używamy Find. Każdy węzeł, który napotykamy na naszej drodze podczas szukania korzenia jest natychmiast przepinany tak, aby korzeń był jego ojcem. Tym samym każde następne szukanie reprezentanta będzie znacznie szybsze.