Package TelNetApplication

Class UnionFind<T>

java.lang.Object

TelNetApplication.UnionFind<T>

public class UnionFind<T>
extends Object

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

Constructor	Description
UnionFind(Set<T> s)	Legt eine neue Union-Find-Struktur mit allen 1-elementigen Teilmengen von s an.

Method Summary

Modifier and Type	Method	Description
T	find(T e)	Liefert den Repräsentanten der Menge zurück, zu der e gehört.
static void	main(String[] args)
void	print()
int	size()	Liefert die Anzahl der Mengen in der Partitionierung zurück.
void	union(T s1, T s2)	Vereinigt die beiden Menge s1 und s2.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

UnionFind

public UnionFind(Set<T> s)

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

public T find(T e)

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

public void union(T s1,
 T s2)

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

public static void main(String[] args)