Operazioni Unione e Trova

Consideriamo l’algebra “partizioni di A” così costituita:
Partizioni di A = ([A, Part(A)], [Unione, Trova, ID, a_1, a_2, \dots , a_n])

Dove:

  • A è un insieme di elementi (A = \{ a_1, a_2, \dots , a_n \} )
  • Part(A) è la famiglia delle partizioni di A , ad esempio la partizione ID rappresenta la partizione identità, in un insieme di n elementi essa sarà composta da n classi di equivalenza. ID = \{ \{ a_1 \} , \{ a_2 \} , \dots , \{ a_n \} \}

Le operazioni definite sono:

  • Unione : Part(A) \times A \times A \to Part(A)
    Unione(P, x, y) , partizione ottenuta da P eseguendo l’unione delle classi di eq. contenenti x e y . Part(a) rappresenta una delle partizioni di A , mentre A e A due elementi di due distinte classi di equivalenza da unire. La funzione restituisce la partizione risultante dall’unione.
  • Trova : Part(A) \times A \to A
    Trova(P, x) , elemento rappresentativo della classe di equivalenza in P contenente x . Part(a) rappresenta una delle partizioni di A , mentre A rappresenta un elemento di una classe di equivalenza. La funzione restituisce l’elemento di A rappresentativo per la classe di equivalenza.

Una partizione di un generico insieme A è una famiglia \{ A_1, A_2, \dots , A_n \} di sottoinsiemi di A , a due a due disgiunti ( \{A_i \bigcap A_j = 0 \forall i \neq j \} ) , che coprono A ( \{ A = A_1 \bigcup A_2 \bigcup \dots \bigcup A_n \} ) .

Il concetto di partizione è strettamente legato a quello di relazione di equivalenza. Ricordiamo che una relazione di equivalenza su A è una relazione R \subseteq A \times A che verifica le proprietà riflessiva, simmetrica e transitiva. Per ogni a \in A , la classe di equivalenza di a modulo R è l’insieme [a]_r = \{ x \in A \mid xRa \} . Si può verificare che per ogni relazione di equivalenza R su un insieme A , l’insieme di equivalenza modulo R forma una partizione di A . Viceversa, ogni partizione \{ A_1, A_2, \dots , A_n \} di A definisce automaticamente una relazione di equivalenza R su A .

Di conseguenza ogni partizione può essere rappresentata da una n -pla di elementi a_1, a_2, \dots , a_n \in A , dove ogni a_i \in A_i . In questo modo [a_i] = A_i \forall i = 1, 2, \dots , n e a_i viene chiamato elemento rappresentati delle classe di equivalenza.

Implementazione delle operazioni Unione e Trova

Consideriamo ad esempio la famiglia delle partizioni dell’insieme A , formato dagli elementi A = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \} . Stabiliamo di usare la convenzione che impone di sottolineare gli elementi rappresentativi, definiamo P la partizione formata da P = \{ \{ 1, 3, \underline{7} \} , \{ \underline{2} \} , \{ 4, 5, 6, \underline{8} , 9 \} \} .

algo_datibis8

L’algebra “Partizioni di A” può essere implementata in maniera piuttosto semplice sfruttando le “Foreste su A”. La partizione \{ A_1 , A_2 , \dots , A_n \} sarà rappresentata da una foresta di n alberi con radice T_1 , T_2 , \dots , T_n tali che, ogni A_i rappresenta l’insieme dei nodi di T_i e la radice di T_i è l’elemento rappresentativo di A_i .

La struttura “Foresta su A” può a sua volta essere implementata mediante una tabella padre:

Nodo Padre
1 7
2 0
3 7
4 8
5 9
6 8
7 0
8 0
9 8

Procedura Trova

La procedura Trova consente di risalire al nodo rappresentativo della classe di equivalenza contenente il nodo specificato. La procedura esegue la scelta ripetuta del nodo padre del nodo in questione, fino a non trovarne più uno.

Procedura Trova(v)
begin
  x := v
  while padre(x) != 0 do
    x := padre(x)
  end while
  return x
end

Il costo della procedura è proporzionale alla profondità del nodo considerato, nel caso peggiore è quindi uguale all’altezza dell’albero.

Procedura Unione

La procedura Unione può invece essere implementata risalendo agli elementi radice dei due elementi e rendendo il secondo figlio del primo.

Procedura Unione(u, v)
begin
  x := Trova(u)
  y := Trova(v)

  if x != y then
    padre(y) := x
end

Anche in questo caso il tempo di esecuzione dipende dalla profondità dei nodi. L’operazione appena descritta non è comunque molto efficiente, è possibile infatti che l’esecuzione di n operazioni Unione e Trova portino alla formazione di un albero totalmente sbilanciato, sui cui future operazioni Trova avranno costo \Theta(n^2) .

Foreste con bilanciamento

Per rimediare alla situazione appena descritta si può procedere con una nuova implementazione dell’algebra “Partizioni di A”, facendo nuovamente uso delle foreste e introducendo un nuovo dato, la cardinalità (dimensione) degli insiemi coinvolti. La cardinalità di un insieme non è altro che il numero di elementi dello stesso. Aggiungiamo una nuova tabella contenente l’informazione num(r) e introduciamo la convezione num(v)=0 per ogni nodo non radice, otteniamo:

algo_datibis9

Nodo Padre
1 7
2 0
3 7
4 8
5 9
6 8
7 0
8 0
9 8
Nodo Num
1 0
2 1
3 0
4 0
5 0
6 0
7 3
8 5
9 0

 

Procedura Unione

In questo modo la procedura Unione può essere eseguita inserendo la radice dell’albero più piccolo tra i figli della radice dell’albero più grosso.

Procedura Unione(u, v)
begin
  x := Trova(u)
  y := Trova(v)

  if x != y then
    if num(x) < num(y) then      // 'x' è l'albero con cardinalità inferiore
      padre(x) := y              // inserisco 'x' tra i figli di 'y'
      num(y) := num(y) + num(x)  // aggiorna la cardinalità di 'y'
      num(x) := 0                // azzero la cardinalità di 'x'
    else                         // altrimenti, replico i passaggi usando 'x' come padre
      padre(y) := x
      num(x) := num(x) + num(y)
      num(y) := 0
end

Utilizzando questa nuova implementazione possiamo stabilire che: durante l’esecuzione di n-1 operazioni di Unione, eseguite dalla partizione identità e su una foresta con bilanciamento, implementata per rappresentare le partizioni di un insieme di n elementi, l’altezza di ogni albero con k nodi non è mai superiore a log_{2}{k} .

Da qui segue che il costo dell’esecuzione di n operazioni di Unione e Trova, su un insieme di n elementi, a partire dalla partizione identità, è uguale O(n log_{2}{n}) .

Compressione di cammino

La complessità appena ottenuta può essere migliorata ulteriormente eseguendo le operazioni Trova mediante “compressione di cammino”. Questa operazione consiste nell’eseguire l’operazione Trova(u) memorizzando in una lista tutti i nodi che si trovano sul cammino da u a r , rendendoli poi figli di r . Di conseguenza l’esecuzione di ulteriori operazioni Trova sullo stesso albero potrebbe richiedere un tempo minore.

algo_datibis10

Procedura Trova

La procedura Trova può essere così riscritta:

Procedura Trova(v)
begin
  x := v                  // valore di output
  L := Λ                  // lista di elementi

  while padre(x) != 0 do  // inserisco l'elemento nella lista
    L := ADD(L, 1, x)
    x := padre(x)
  end while

  for u ∈ L do            // assegno padre(k) = x a tutti i k elementi della lista
    padre(u) := x
  end for

  return x
end

In seguito all’esecuzione di questa funzione sarà possibile ottenere la radice di ogni nodo k semplicemente eseguendo Trova(k) in un tempo uniforme.