Bäume

Definition:
Eine Union-Find-Datenstruktur auf Bäumen speichert jede Menge als gerichteten Baum und verwendet als Mengenname die Wurzel.

Operationen:

1. Find($x$): ausgehend von $x$ zur Wurzel laufen, Kosten $O(TreeHeight)$

2. Union($T_1,T_2$): einen Baum an der Wurzel des anderen Baumes einhängen, Kosten $O(1)$

Find-Komplexität und Verbesserungen:
1. Primitiv: Baumhöhe ist $O(n)$
2. Hänge bei Union den kleineren Baum an den größeren, Baumhöhe ist $O(\log n)$
3. Pfadkompression: hänge bei Find($x$) alle Elemente auf dem Weg nach $x$ direkt an die Wurzel, Baumhöhe ist $O(log^* n)$