W przeciwnym wypadku, będzie dostępny później jako Find(u).ancestor, w momencie pokolorowania v na czarno.
Poniżej znajduje się zoptymalizowana wersja funkcji MakeSet, Find, and Union działających na zbiorach rozłącznych.
funkcja MakeSet(x) x.parent := x x.rank := 0
funkcja 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
funkcja Find(x) if x.parent == x return x else x.parent := Find(x.parent) return x.parent
Przypisy
Bibliografia . .
Kategoria:Drzewa (informatyka) Tarjan