prev up inhalt next


4 Union/Find


Aufgabe:


Verwaltung von disjunkten Mengen S1,...,Sk $\subset$ {1,...,n}

1.)
Zu x $\in$ {1,...,n} finde ein y $\in$ {1,...,k} mit x $\in$ Sy . Bei gleichbleibenden Mengen S1,...,Sk ist das kein Problem!
Aber:
2.)
Zu x,y $\in$ {1,...,n} finde i,j $\in$ {1,...,k} mit x $\in$ Si und y $\in$ Sj , dann bilde Si $\cup$ Sj .

Idee: Für jedes Element aus {1,...,n} führe einen Knoten ein. Diese Knoten faßt man in Bäumen zusammen, die durch ihre Wurzel repräsentiert werden.

Die dazu benötigte Datenstruktur: VAR vater: ARRAY[0..n-1] OF INTEGER,

Dabei gilt: vater[x] = y$\iff$y ist Vater von x
  vater[x] = x$\iff$x ist Wurzel $\iff$x ist Repräsentant.

Daraus ergeben sich folgende Prozeduren:


     PROCEDURE find(x: INTEGER): INTEGER
     (* liefert Repräsentanten von x *)
     BEGIN
          WHILE vater[x] $\neq$ x DO
               x := vater[x];
          END;
     RETURN x;
     END;

     PROCEDURE union(x, y: INTEGER);
     BEGIN
          vater[find(x)] := find(y);
     END;

Die optimale Situation für die find-Prozedur liegt dann vor, wenn der Baum möglichst flach ist, also alle Knoten direkte Söhne der Wurzel sind. Die Prozedur union zerstört diese Situation aber, indem sie die Bäume vereinigt und sie untereinander setzt.

Um diesen Schaden allerdings möglichst klein zu halten, gibt es zwei verschiedene Ansätze:

1.
Hänge den flacheren Baum unter die Wurzel des höheren Baums, merke also die Tiefe eines jeden Baumes in der Wurzel.


2.
Ordne allen Knoten auf dem Weg zur Wurzel die Wurzel als neuen Vater zu:





prev up inhalt next