# Zajęcia 08.03.2021 - Union-find

###### tags: `Informatyka 1PR`

Mamy dane $n$ elementów (np. wierzchołków grafu). Początkowo elementy nie są ze sobą w żaden sposób związane. Chcemy na nich skonstruować strukturę zbiorów rozłącznych. Co to znaczy? Początkowo każdy z elementów należy do "swojego" zbioru, do którego nie należy żaden inny wierzchołke. Naszym celem będzie skonstruowanie struktury danych, która będzie realizowała następujące operacje:
- $find(v)$ - zwróć **reprezentanta** zbioru, w którym jest $v$,
- $union(u, v)$ - połącz ze sobą zbiory, w których znajdują się $u$ oraz $v$.

Co mamy na myśli przez **reprezentanta** zbioru? W zasadzie to dokładnie to co oznacza to słowo - dla każdego zbioru będziemy w pewien sposób wybierać który element go reprezentuje i dla wszystkich każdego elementu chcielibyśmy umieć szybko znajdować reprezentanta zbioru, do którego należy [ten element]. Reprezentantami zbioru będą dokładnie te wierzchołki $v$, dla których zachodzi zależność `repr[v] = v`.

Obie te operacje można wykonywać w bardzo prosty sposób: utrzymujemy globalną tablicę `repr[1..n]` która będzie utrzymywać informację o reprezentacie każdego elementu (elementy utożsmamiamy z liczbami od $1$ do $n$). Początkowo `repr[i] = i` dla każdego $i$ od $1$ do $n$ (tj. każdy element jest reprezentantem swojego zbioru). Wtedy:
- `union(u, v)` mozemy zaimplementować w następujący sposób:

    void union(u, v) {
        u = find(u);
        v = find(v)l
        repr[u] = v; 
    }

Nie dzieje się za wiele - union jedynie zmienia (będziemy mówić *przepina*) reprezentanta zbioru, w którym jest $u$, teraz jest nim reprezentant zbioru, w którym jest $v$.
- `find(v)` implementujemy podobnie jak implementowaliśmy naiwne sprawdzanie, czy jeden wierzchołek jest przodkiem innego:

    int find(int v) {
        if (repr[v] == v) return v;
        return find(repr[v]);
    }

Implementacja wynika z prostej zależności: albo ja jestem swoim reprezentantem, albo jest to reprezentant elementu, na który wskazuje `repr[v]`.

digraph G {
    rankdir="BT"
    {
        rank=same
		node [shape=circle];
        1 
        7
        10
    }
    {
    rank=same
		node [shape=circle];
        2 
        3
    }
    {
        rank=same
		node [shape=circle];
        8 6
    }
    
    subgraph clusterA{
		pencolor=white
		node [shape=circle];
        1 -> 1
        3 -> 1
        2 -> 1
        6 -> 2
        8 -> 2
        4 -> 8
	}

    subgraph clusterB {
    
        pencolor=white
        node [shape=circle]
        7 -> 7
        5 -> 7
        9 -> 5
    }
    
    subgraph clusterC{
        pencolor=white
        node[shape=circle]
        10->10
        15->10
        14->10
        13->10
        12->10
        11->10
    }
    label="Rysunek 1. Przykładowa struktura naszych zbiorów. Strzałka z u do v oznacza,\nże repr[u] = v.Teraz słowo \"przypinanie\" ma więcej sensu. Można myśleć o tym\ntak, że przepinamy strzałki (ale tylko z tych wierzchołków, które wskazują na siebie)."
}    

Niestety, taka realizacja naszej struktury jest zdecydowanie za wolna. Nietrudno znaleźć przykład, w którym operacja `find(v)` będzie zabierać czas liniowy względem liczby elementów, a co za tym idzie, `union(u, v)` będzie działał równie wolno (bo korzysta z `find`). Spróbuj sam(a) pomyśleć nad takim przykładem!

Spróbujmy sobie powiedzieć, kiedy dokładnie `find` działa *wolno* i jak można to naprawić. Zobaczmy, że `find` będzie przechodził po krawędziach drzewa, dopóki nie dojdzie do reprezentanta zbioru (myślmy o nim jak o korzeniu). Zatem rozmiar drzewa nie ma dla nas dużego znaczenia. Gorzej dla nas jest wtedy, kiedy drzewo jest *wysokie*, tj. odległości od korzenia do liści są duże.

Naszym celemem jest takie zmodyfikowanie funkcji `union`, żeby zapewnić, że wysokości powstałych drzew są niskie. W tym celu wprowadzamy pojęcie **rangi** drzewa. Rangą drzewa będziemy nazywać liczbę opisującą długość najdłuższej *gałęzi* drzewa, czyli jakiejś ścieżki od korzenia do liścia (liczymy liczbę krawędzi na tej ścieżce). Przykładowo, na rysunku 1. ranga lewego drzewa to 3, ranga środkowego drzewa to 2, a ranga prawego drzewa to 1.

Od teraz `union` będzie działał w następujący sposób:
:::info
`union(u, v)` wyznacza reprezentantów `u` oraz `v` i sprawdza które z drzew reprezentujących zbiory `u` oraz `v` jest wyższe. Następnie przypina reprezentanta niższego drzewa do reprezentanta wyższego drzewa.
:::

Jak zaraz się okaże, taka optymalizacja znacząco ogranicza możliwą wysokość otrzymywanych drzew. Zanim to, musimy się jeszcze zastanowić jak sprawdzać jakie są wysokości drzew? Najprostszym i naturalnym sposobem będzie utrzymywanie dodatkowej tablicy `ranga[1..n]`, dla której zachodzi zależność `ranga[v] = ranga drzewa v`. Początkowo `ranga[i] = i` dla wszystkich $i$ od $1$ do $n$. Jak aktualizować taką tablcię? Jeśli chcemy przypiąć wierzchołek $u$ do wierzchołka $v$, to zachodzą dwie możliwości:
- `ranga[u] > ranga[v]`. Wtedy nie chcemy przypinać $u$ do $v$, tylko $v$ do $u$.
- `ranga[u] < ranga[v]`. Nietrudno wtedy zauważyć, że ranga $v$ nie ulegnie zmianie.
- `ranga[u] == ranga[v]`. Wtedy ranga $v$ zwiększy się o dokładnie $1$.

digraph G {
    rankdir="BT"
    node [shape=circle]
    {
        rank=same
        1 9
    }
    {
        rank=same
        2 3
    }
    {
        rank=same
        6 5 4
    }
    subgraph clusterA{
        pencolor=white
        1 -> 1
        3 -> 1
        4 -> 3
        5 -> 3
        2 -> 1 [color=red, style=dashed]
        6 -> 2
        7 -> 6
    }
    subgraph clusterB {
        pencolor=white
        9 -> 9
        8 -> 9
        10 -> 8
        12 -> 11
        13 -> 11
        11 -> 9 [color=red, style=dashed]
    }
    label="Rysunek 2. Na lewo łączymy drzewa tych samych wysokości, zatem wysokość otrzymanego\ndrzewa jest większa o 1. Na lewo dodajemy drzewo niższe to wyższego, więc\notrzymane drzewo ma taką samą wysokość."
}

Jak się okazuje, otrzymujemy bardzo dobre ograniczenie na wysokości takich drzew: teraz wynosi ona $\lceil\log n\rceil$. Pokażemy to korzystając z indukcji matematycznej, udowadniając następujące twierdzenie:

:::success
**Twierdzenie 1.** Jeśli drzewo utworzone przez `union` ma wysokość $r$, to należy do niego co najmniej $2^r$ wierzchołków.
:::

Zastanówmy się najpierw jakie są konsekwencje tego twierdzenia. Powiedzmy, że połączyliśmy ze sobą już wszystkie wierzchołki, tj. wszystkie elementy należą do jednego zbioru. Gdyby wysokość utworzonego drzewa byłaby większa niż $\lceil\log n\rceil$, to wg twierdzenia liczba elementów takiego drzewa musiałaby wynosić więcej niż $2^{\log n} = n$, co jest oczywistą sprzecznością. Zatem w żadnym momencie działania algorytmu żadne z drzew nie przekracza tej wysokości.

**Dowód twierdzenia.** Dowód przebiega indukcyjnie względem rozmiaru drzewa.
- Baza indukcji: Widzimy, że jeśli wysokość drzewo ma rozmiar $1$, to jego wysokość wynosi $1$, zatem twierdzenie jest prawdziwe.
- Krok indukcyjny: Załóżmy, że twierdzneie jest prawdziwe dla drzew o liczbie wierzchołków mniejszych niż $n$. Weźmy teraz dowolne drzewo $n$ wierzchołkowe i załóżmy, że jego wysokość wynosi $r$. To drzewo musiało powstać przez `union` dwóch mniejszych drzew. Mamy dwa przypadki:
- Jedno drzewo miało wysokość $r$, a drugie mniejsze niż $r$: wtedy podpięliśmy drugie drzewo do pierwszego. Ponadto z założenia indukcyjnego wynika, że pierwsze drzewo miało co najmniej $2^r$ wierzchołków, a zatem $n > 2^r$ (no bo nasze drzewo musi mieć więcej wierzchołków, niż drzewa z których je utworzyliśmy).
- Oba drzewa miały tę samą wysokość $r - 1$. Wtedy arbitralnie wybraliśmy, które drzewo podpiąć do którego. Jednakże, z założenia indukcyjnego oba drzewa musiały mieć co najmniej $2^{r-1}$ wierzchołków, a zatem nasze drzewo ma co najmniej $2^{r-1} + 2^{r-1} = 2^r$ wierzchołków. $\blacksquare$

<!-- Załóżmy teraz, że mamy dwa drzewa, oba wysokości $r$ (jeśli jedno byłoby niższe, to wysokość się nie zmienia, a liczba wierzchołków rośnie, co działa jedynie na naszą korzyść). Z założenia indukcyjnego liczba wierzchołków w obu drzewach wynosi co najmniej $2^r$. Gdy połączymy te drzewa, to jego wysokość będzie wynoscić $r + 1$. Jednakże liczba wierzchołków w tym drzewie to teraz co najmniej $2^r + 2^r = 2\cdot 2^r = 2^{r + 1}$, a zatem teza nadal jest spełniona, co dowodzi jej prawdziwości.
-->
Zmieniona operacja `union` wygląda teraz następująco:

void union(int v, int u) {
    u = find(u);
    v = find(v);
    if (ranga[v] < ranga[u])  
        repr[v] = u;
    else                      
        repr[u] = v;
    
    if (ranga[v] == ranga[u]) 
        ranga[v]++;
}

---

Działanie procedury `find` można przyspieszyć jeszcze bardziej jedną, bardzo prostą optymalizacją. Za każdym razem, kiedy wykonujemy operację `find(v)`, możemy aktualizować wartość `repr[v]` na faktycznego reprezentanta wierzchołka `v`:

int find(int v) {
    if (repr[v] == v) return v;
    return repr[v] = find(repr[v]);    
}

Tę optymalizację nazywamy **kompresją ścieżek**.

Połączenie obu tych optymalizacji sprawia, że wysokości drzew stają się jeszcze mniejsze. Dokładna analiza złożoności takiej wersji procedur jest trudna, ale warto wiedzieć, że dla danych z którymi kiedykolwiek się spotkacie (a nawet z którymi kiedykolwiek spotka się ludzkość), nie przekroczy $5$ ([dla ciekawskich](https://pl.wikipedia.org/wiki/Funkcja_Ackermanna#Odwrotna_funkcja_Ackermanna)).