31 Jan 2026

Unija z rangom

A test post from my old notes. The content is not very well written or well-organised, but it has both a code block and \(\LaTeX\), so serves as a good test for the site's features.

Operations:

  • singleton(x) . ustvari singleton \(\{x\}\)
  • find(x) . poišči predstavnika komponente, ki vsebuje \(x\)
  • merge(x, y) . združi komponenti/množici, v katerih sta \(x\) in \(y\)

Unija z rangom

Množice prestavimo z DAG, kjer gre iz vsakega elementa natanko ena povezava Potem ima vsaka komponenta natanko en ponor.

To shranimo z dvema tabelama, v eni imamo predhodnik od vsakega elementa (če je v enojcu je sam svoj prednik), v drugi pa rang elementa.

Lastnosti ranga za union-find

  1. rang(x) < rang(π(x)), če x≠π(x).
  2. Če je \(x\) ranga \(k\), ima \(x\) pod sabo vsaj \(2^k\) vozlišč (vključno s seboj).
  3. Če imamo \(n\) elementov, imamo lahko največ \(\frac{n}{2^k}\) vozlišč ranga \(k\).
  4. Sledi, da je maksimalen rang lahko \(\log n\)

Primer:

Vzemimo \(\{A,C,D,F,G,H\}\) in \(\{B,E\}\).

Tabela:

x A B C D E F G H  
π(x) F E H H E H D H <- Predhodnik
rang(x) 0 0 0 1 1 1 0 2 <- Globina drevesa pod x

Operacije:

from functools import reduce

π = {}
rang = {}

def singleton(x):
      π[x] = x
      rang[x] = 0
      return x

def find(x):
      while x != π[x]:
          x = π[x]
      return x

def find_amortized(x):
      "Na vsakem koraku malo flattenaj"
      if x != π[x]:
          π[x] = find_amortized(π[x])
      return π[x]

def merge(x, y):
      p_x = find(x)
      p_y = find(y)
      if p_x == p_y:
            return p_x
      else:
            if rang[p_x] > rang[p_y]:
                  π[p_y] = p_x
                  return p_x
            else:
                  π[p_x] = p_y
                  if rang[p_x] == rang[p_y]:
                        rang[p_y] += 1
                        return p_y


  # Primer od prej:

  #for el in ["A", "B", "C", "D", "E", "F", "G", "H"]:
  #    singleton(el)
  #reduce(merge, ["A", "C", "D", "F", "G", "H"])
  #reduce(merge, ["B", "E"])

π = [0,0,1,3,3,4]
rang = [2,1,0,2,1,0]

print(π) 
print(rang)

find_amortized(2)

print(π)
print(rang)


[0, 0, 1, 3, 3, 4]
[2, 1, 0, 2, 1, 0]
[0, 0, 0, 3, 3, 4]
[2, 1, 0, 2, 1, 0]

Načeloma singleton in merge ne rabita vračati, to je le zavoljo primera, saj lahko s tem uporabimo reduce za konstrukcijo množice. Rezultat se razlikuje od zgornje postavitve, ker več DAG-ov predstavlja isto množico. Če se drevo nariše, se jasno vidi, da množici predstavljata isto particijo.

Zahtevnosti:

  • Singleton: \(O(1)\)
  • Poišči: \(O(\log n)\)
  • Amortiziran poišči: \(O(\log^*|V|)\)
  • Združi \(O(\log n)\)

Z izboljšavo dobimo amortizirano časovno zahtevnost.

Opomba:

Z uporabo amortiziranega poišči je tudi združi amortizirane časovne zahtevnosti (saj je le dva poišči in nekaj konstantnih operacij).

Union-find with path compression

Back

Koliko nas stane paket \(m\) operacij poišči na \(n\) vozliščih?

  • \(\log^*n\) - kolikokrat moramo zaporedoma narediti logaritem, da pridemo na 1 ali manj.
  • \(\log\log\log\log 1000 \leq 1 \implies \log^{*}1000 = 4\)
  • Poišči nas stane v povprečju \(O(\log^{*}n)\)
  • V resnici bi zaporedje \(m\) operacij stalo \(O(m\log^{*}n) + O(n\log^{*}n)\).

Rang se ohranja, a ne predstavlja več globine drevesa. Range razdelimo na intervale: \[ [1], [2], [3, 4], [5, 16], [17, 2^{16}], [2^{16} + 1, 2^{2^{16}}], \dots \] Ko vozlišče ranga iz \([k + 1, 2^k]\) neha biti koren, mu damo žepnino \(2^k\) žetonov. En žeton porabi en skok po povezavi. Vozlišč iz tega intervala je največ \[ \frac{n}{2^{k+1}} + \frac{n}{2^{k+2}} + \cdots + \frac{n}{2^{2^k}} \leq \frac{n}{2^k} \] Vsak interval dobi največ \(n\) žepnin. Intervalov je največ \(\log^{*}n\). Operacija poišči(x) porabi toliko, kot je dolga veriga: \[ x = y_0 \rightarrow y_1 \rightarrow \cdots \rightarrow y_r \] Vrednosti \(\rang(y_i)\) in \(\rang(\pi(y_i))\) sta lahko ali v različnih intervalih, kar se lahko zgodi le \(\log^{*}n\)-krat, ali pa v istem intervalu. V tem primeru \(y_{i}\) prispeva en žeton, s čimer smo povečali \(\rang(\pi(y_i))\). V kombinaciji z večimi združi se to lahko zgodi kvečjemu \(2^k\)-krat, saj je vozlišč največ \(\frac{n}{2^k}\). Torej imamo dovolj žepnine.