Package TelNetApplication
Class UnionFind<T>
java.lang.Object
TelNetApplication.UnionFind<T>
Klasse für Union-Find-Strukturen.
Unterstützt die effiziente Verwaltung einer Partionierung (disjunkte Zerlegung)
einer Grundmenge.
union benötigt O(1) und find benötigt O(log(n)).
- Since:
- 24.01.2015
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
UnionFind
Legt eine neue Union-Find-Struktur mit allen 1-elementigen Teilmengen von s an. s ist die Grundmenge der Partionierung.- Parameters:
s
- Grundmenge
-
-
Method Details
-
find
Liefert den Repräsentanten der Menge zurück, zu der e gehört.- Parameters:
e
- Element- Returns:
- Repräsentant der Menge, zu der e gehört.
- Throws:
IllegalArgumentException
- falls e nicht zur Grundmenge gehört.
-
union
Vereinigt die beiden Menge s1 und s2. s1 und s2 müssen Repräsentanten der jeweiligen Menge sein. Die Vereinigung wird nur durchgeführt, falls s1 und s2 unterschiedlich sind. Es wird union-by-height durchgeführt.- Parameters:
s1
- Element, das eine Menge repräsentiert.s2
- Element, das eine Menge repräsentiert.- Throws:
IllegalArgumentException
- falls s1 oder s2 nicht zur Grundmenge gehören.
-
print
public void print() -
size
public int size()Liefert die Anzahl der Mengen in der Partitionierung zurück.- Returns:
- Anzahl der Mengen.
-
main
-