From 1b8170e589abaf4863579cf2e4c5a27b13d08056 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Fri, 4 Dec 2015 23:52:40 +0100 Subject: Renaming variable in union find data structure. Old name was misleading. --- datastructures/unionFind.cpp | 12 +++++++----- tcr.pdf | Bin 231120 -> 231397 bytes 2 files changed, 7 insertions(+), 5 deletions(-) diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp index 4b13dbf..3f7df97 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,6 +1,8 @@ // Laufzeit: O(n*alpha(n)) -// "size" ist obere Schranke für die Höhe der Bäume. -vector parent, size; +// "height" ist obere Schranke für die Höhe der Bäume. Sobald Pfadkompression +// angewendet wurde, ist die genaue Höhe nicht mehr effizient berechenbar. +vector parent // Initialisiere mit Index im Array. +vector height; // Initialisiere mit 0. int findSet(int n) { // Pfadkompression if (parent[n] != n) parent[n] = findSet(parent[n]); @@ -8,11 +10,11 @@ int findSet(int n) { // Pfadkompression } 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; + if (height[a] < height[b]) parent[a] = b; + else if (height[b] < height[a]) parent[b] = a; else { parent[a] = b; - size[b]++; + height[b]++; } } diff --git a/tcr.pdf b/tcr.pdf index cf23d7d..0626d6a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3