next up previous contents
Next: Pfad-Kompression mit gewichteten Union Up: Union-Find-Datenstruktur Previous: Intrees

Gewichtete Union (erste Verbesserung)

Mache die Wurzel des kleineren Baumes zu einem Kind der Wurzel des größeren Baumes. Die Tiefe des Baumes ist dann $\mathcal{O}(\log{n})$ Es gilt auch: Tiefe des Baumes in worst-case : \fbox {$\Omega(\log n)$}
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999