next up previous contents
Nächste Seite: Bäume Aufwärts: Union-Find-Datenstrukturen Vorherige Seite: Union-Find-Datenstrukturen   Inhalt

Listen

Definition:
Eine Union-Find-Datenstruktur auf Listen speichert jede Menge als separate Liste und verwendet als Mengenname das erste Element einer Liste.

Operationen:

1. Find($ x$): ausgehend von $ x$ ist der Anfang der Liste zu suchen, Kosten $ O(n)$, mit Referenz $ O(1)$

2. Union($ L_1,L_2$): Kopiere kürzere Liste ans Ende der längeren Liste, Kosten $ O(1)$, mit Referenz $ O(n)$



2003-10-08