Estructura de senyes per a conjunts disjuntos

En computació, una estructura de senyes per a conjunts disjuntos, és una estructura de senyes que manté un conjunt d'elements particionados en un número de conjunts disjuntos(no es solapan els conjunts).Un algoritme Unió-Buscar és un algoritme que realisa dos importants operacions en esta estructura de senyes:

• Buscar: Determina a cual subconjunt pertany un element. Esta operació pot usar-se per a verificar si dos elements estan en el mateix conjunt.
• Union: Unix dos subconjunts en un solament.

L'atra operació important CrearConjunto és generalment trivial, esta crea un conjunt en un element donat. En estes tres operacions, molts problemes pràctics de particionamiento poden ser resolts(vore la secció de Aplicacions).

En la finalitat de definir estes operacions més precisament , és necessari representar els conjunts d'alguna manera. Una aproximació comuna és seleccionar un element fix de cada conjunt , cridat el representatiu, per a representar el conjunt com un tot. Llavors Buscar(x) retorna l'element representatiu del conjunt al com x pertany , i Unió pren com a argument dos elements representatius de dos conjunts respectivament.

Llistes Enllaçades de Conjunts Disjuntos

Un simple acostament per a crear una estructura de senyes per a conjunts disjuntos és crear una llista enllaçada per a cada conjunt. L'element en el cap de cada llista enllaçada es tria com a element representatiu.

CrearConjunto crea una llista en un sol element. Unió concatena dos llistes , una operació en temps constant. El problema d'esta implementació és que Buscar(x) requerix Ω(n) o orde llineal per a recórrer d'arrere cap a avant, des de l'element donat fins al cap de la llista.

Açò pot ser evitat afegint a cada nodo de la llista enllaçada una busca al cap de la llista; per tant Buscar pren temps constant. Pero ara Unió ara té que actualisar a cada element de la llista que està sent concatenada una referència al cap de la nova llista combinada, requerint Ω(n) temps.

Quan sabem la llongitut de cada llista, el temps requerit pot ser millorat concatenant sempre la llista de menor llongitut a la de major llongitut. Usant esta heurística cridada weighted-union, una seqüència de m operacions de CrearConjunto, Unió i Buscar sobre n elements requerix O(m + nlog n) temps. Per a operacions asintóticamente més ràpides una atra estructura de senyes és necessària.

Anàlisis d'este acostament simple

Ara explicarem el temps $O(n\log (n))$ de dalt. Supongam que tenim una colecció de llistes, cada nodo de la llista conté un objecte, el nom de la llista a la qual pertany, i el número d'elements d'eixa llista. També assumim que la suma de la cantitat dels elements de totes les llistes és $n$ (per tant existixen $n$ elements). Volguérem poder mesclar qualsevol dos d'estes llistes, i actualisar tots els seus nodos per a que seguixquen tenint el nom de la llista a la que pertanyen. La regla per a mesclar les llistes $A$ i $B$ és que, si $A$ és major que $B$ llavors s'afigen els de $B$ en $A$ i s'actualisen els elements que pertanyen a $B$, i viceversa.

Triar un element arbitrari de la llista $L$, digam $x$. Volguérem contar en el pijor cas quantes voltes l'element $x$ va a necessitar actualisar el nom de la llista a la qual pertany. L'element $x$ solament va a actualisar el seu nom quan la llista a la qual pertany és mesclada en una llista del mateix o major tamany. Cada moment que passe açò , el tamany de la llista de $x$ a lo manco es dobla. Llavors finalment, la pregunta és ¿Quantes voltes pot un número doblar el seu tamany ans que aplegue a $n$? (llavors la llista de $x$ té tamany $n$). La resposta exacta és ${\log }_2(n)$. Llavors per a qualsevol element en qualsevol llista en l'estructura descrita, serà necessari actualisar ${\log }_2(n)$ voltes en el pijor dels casos. Per tant actualisar una llista de $n$ elements almagasenats d'esta manera prendria $O(n\log (n))$ temps en el pijor cas. Una operació de busca es pot realisar en $O(1)$ en esta estructura puix tots els nodos contenen el nom de la llista a la qual pertanyen.

Un argument similar es mantenen per a mesclar els arbres de les estructures de senyes discutides més avall, adicionalment ajuda a explicar l'anàlisis de temps d'algunes operacions sobre les estructures de senyes Heap Binomial i Montícul de Fibonacci.

Boscs de Conjunts-Disjuntos

Els Boscs de Conjunts-Disjuntos són estructures de senyes a on cada conjunt està representat per un arbre , en el qual cada nodo manté una referència al seu nodo pare (vore pila espagueti). Estos varen ser descrits primers per Bernard A. Galler i Michael J. Fisher en 1964, prenent anys per al seu precís anàlisis.

En els Boscs de Conjunts-Disjuntos, el representatiu de cada conjunt és la raïl de l'arbre el qual representa el conjunt. Buscar seguix pels pares nodos fins a trobar la raïl de l'arbre. Unió combina dos arbres en un afegint la raïl d'un en la raïl de l'atre. Una manera d'implementar açò pot ser:

 function CrearConjunto(x)
     x.pare := x

 function Buscar(x)
      if x.pare == x
         return x
      else
         return Buscar(x.pare)

 function Unió(x,i)
     xRaíz := Buscar(x)
     yRaíz := Buscar(i)
     xRaíz.pare := yRaíz

En esta simple forma, este implementació no és millor que l'implementació basada en llistes enllaçades, perque l'arbre que es creu pot ser molt desbalanceado; de totes maneres , açò pot ser millorat de dos formes.

La primera forma, es diu unió per rank, consistix en sempre afegir l'arbre més chicotet a la raïl de l'arbre més gran. Com la profunditat de l'arbre afecta el temps d'eixecució de l'algoritme, l'arbre en menor profunditat és afegit a la raïl de l'arbre en major profunditat, el qual aumenta la seua profunditat solament si les seues profunditats són iguals. En el context d'este algoritme, el terme rank s'usa en lloc de profunditat perque este deixa de ser igual a la profunditat si s'usa la compressió de camí (descrita més avall). Els arbres en un sol element tenen rank igual a zero, i qualsevol dos arbres del mateix rank r són combinats, el rank resultant és r+1. Solament aplicant esta tècnica obtenim en el pijor cas un temps d'eixecució de $O(\log n)$ per a les operacions CrearConjunto, Unió i Buscar. Pseudocódigo de el CrearConjunto i Unió millorat:

 function CrearConjunto(x)
     x.pare := x
     x.rank  := 0

 function Unió(x, i)
     xRaíz := Buscar(x)
     yRaíz := Buscar(i)
     if xRaíz == yRaíz
        return
     //Ya que no estan en el mateix conjunt, s'unixen.
     if xRaíz.rank < yRaíz.rank
        xRaíz.pare := yRaíz
     else if xRaíz.rank > yRaíz.rank
        yRaíz.pare := xRaíz
     else
        yRaíz.pare := xRaíz
        xRaíz.rank := xRaíz.rank + 1

La segona millora, cridada compressió de camí, és una forma de aplanar l'estructura de l'arbre quan s'aplique Buscar. L'idea és que cada nodo visitat en el camí cap a la raïl pot ser afegit directament a la raïl; tots ells compartixen el mateix representatiu. Per a conseguir este efecte, mentres Buscar recursivamente es mou cap a la raïl, est canvia la referència del pare del nodo a la raïl que trobe. L'arbre resultant és més aplanado, accelerant operacions futures no solament en estos elements sino també en aquells que referencian a estos. Ací va el Buscar millorat:

 function Buscar(x)
     if x.pare != x
        x.pare:= Buscar(x.pare)
     return x.pare

Estes dos tècniques es complementen una a una atra; aplicades juntes, el temps amortisat és sol $O(\alpha (n))$, a on $\alpha (n)$ és l'inversa de la funció $n=f(x)=A(x,x)$, i $A$ és la funció de Ackermann. Com $\alpha (n)$ és l'inversa d'esta funció, $\alpha (n)$ és menor que 5 per a tots els pràcticament remots valors de $n$. Per tant el temps d'eixecució amortisat és efectivament una chicoteta constant.