Improvements in datastructures chapter.

1 files changed, 9 insertions, 7 deletions

diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
index 1ee532c..4b13dbf 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -1,19 +1,21 @@
-vector<int> parent, rank2; //manche Compiler verbieten Variable mit Namen rank
+// Laufzeit: O(n*alpha(n))
+// "size" ist obere Schranke für die Höhe der Bäume.
+vector<int> parent, size;
 
-int findSet(int n) { //Pfadkompression
+int findSet(int n) { // Pfadkompression
 	if (parent[n] != n) parent[n] = findSet(parent[n]);
 	return parent[n];
 }
 
-void linkSets(int a, int b) { //union by rank
-	if (rank2[a] < rank2[b]) parent[a] = b;
-	else if (rank2[b] < rank2[a]) parent[b] = a;
+void linkSets(int a, int b) { // Union by rank.
+	if (size[a] < size[b]) parent[a] = b;
+	else if (size[b] < size[a]) parent[b] = a;
 	else {
 		parent[a] = b;
-		rank2[b]++;
+		size[b]++;
 	}
 }
 
-void unionSets(int a, int b) {
+void unionSets(int a, int b) { // Diese Funktion aufrufen.
 	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
 }