Mostrar código-fonte de União-busca

{{mais fontes|data=maio de 2014}}
{{Infocaixa estrutura de dados
| nome               = União-busca/Disjoint-set
| tipo               = Árvore
| inventado_por      = [[Bernard Galler]] e [[Michael John Fischer]]
| ano                = 1964
| espaco_med         = {{math|O(''n'')}}<ref name="tarjan1975">{{citar periódico|último1 =Tarjan |primeiro1 =Robert Endre |autorlink1 =Robert Tarjan |ano=1975 |título=Efficiency of a Good But Not Linear Set Union Algorithm |periódico=Journal of the ACM |volume=22 |número=2 |páginas=215&ndash;225 |url=http://portal.acm.org/citation.cfm?id=321884 |doi=10.1145/321879.321884 }}</ref>
| espaco_pior        ={{math|O(''n'')}}<ref name="tarjan1975"/>
| busca_med          ={{math|O(''&alpha;''(''n''))}}<ref name="tarjan1975"/>
| busca_pior         ={{math|O(''&alpha;''(''n''))}}<ref name="tarjan1975"/>
| merge_med         ={{math|O(''&alpha;''(''n''))}}<ref name="tarjan1975"/>
| merge_pior        ={{math|O(''&alpha;''(''n''))}}<ref name="tarjan1975"/>
}}

Em [[ciência da computação]], uma '''estrutura de dados união-busca''' também chamado de '''estrutura de dados disjoint-set''' é uma [[estrutura de dados]] que mantém o controle de um [[conjunto]] de elementos particionados em [[Conjuntos_disjuntos|subconjuntos disjuntos]] (não sobreposicionados). Ele fornece operações com tempo quase constante (delimitadas pela inversa [[função de Ackermann]]) para adicionar novos conjuntos, para mesclar conjuntos existentes e para determinar se os elementos estão no mesmo conjunto. Além de muitos outros usos, os disjoint-sets desempenham um papel fundamental no [[algoritmo de Kruskal]] para encontrar a [[árvore de extensão mínima]] em um grafo.


== História ==
As '''estruturas de dados união-busca''' foram descritos pela primeira vez por [[Bernard A. Galler]] e [[Michael J. Fischer]] no ano de 1964.<ref name="Galler1964">{{citar livro|primeiro =Bernard A.|último =Galler|autorlink1 =Bernard A. Galler|primeiro2 =Michael J.|último2 =Fischer|autorlink2 =Michael J. Fischer|título=An improved equivalence algorithm|periódico=[[Communications of the ACM]]|volume=7|número=5|data=maio de 1964|páginas=301–303|url=http://portal.acm.org/citation.cfm?doid=364099.364331|doi=10.1145/364099.364331}}. The paper originating disjoint-set forests.</ref> Em 1973, a complexidade do algoritmo foi definida como <math>O(\log^*(n))</math>, a  função [[Logaritmo iterado]] de <math>n</math>.<ref name="Hopcroft1973">{{citar periódico|último1 =Hopcroft|primeiro1 =J. E.|autorlink1 =John Hopcroft|último2 =Ullman|primeiro2 =J. D.|autorlink2 =Jeffrey Ullman|ano=1973|título=Set Merging Algorithms|periódico=SIAM Journal on Computing|volume=2|número=4|páginas=294&ndash;303|doi=10.1137/0202024}}</ref> Mas em 1975, [[Robert Tarjan]] foi o primeiro a provar <math>O(\alpha(n))</math>([[Função inversa|Função Inversa]] de Ackermann)<ref name="Tarjan1984">{{citar periódico|primeiro =Robert E.|último =Tarjan|autorlink1 =Robert E. Tarjan|primeiro2 =Jan|último2 =van Leeuwen|autorlink2 =Jan van Leeuwen|título=Worst-case analysis of set union algorithms|periódico=Journal of the ACM|volume=31|número=2|páginas=245–281|ano=1984|doi=10.1145/62.2160}}</ref> como novo limitante superior para o algoritmo, e, em 1979, mostrou que a mesma função era limitante inferior para um caso específico.<ref name="Tarjan1979">{{citar periódico|primeiro =Robert Endre|último =Tarjan|autorlink =Robert E. Tarjan|ano=1979|título=A class of algorithms which require non-linear time to maintain disjoint sets|periódico=Journal of Computer and System Sciences|volume=18|páginas=110&ndash;127|doi=10.1016/0022-0000(79)90042-4}}</ref>

Em 1989, [[Fredman]] e [[Sakskøbing|Saks]] mostraram que  <math>\Omega(\alpha(n))</math>elementos são acessados por qualquer '''estrutura de dados união-busca''' para cada operação executada (custo amortizado).<ref name="Fredman1989">{{citar periódico|primeiro =M.|último =Fredman|autorlink =Michael Fredman|primeiro2 =M.|último2 =Saks|título=The cell probe complexity of dynamic data structures|periódico=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing|páginas=345&ndash;354|data=maio de 1989|citação=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires &Omega;(''m'' &alpha;(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets.}}</ref>

== Implementação ==
Uma '''estrutura de dados união-busca''' consiste de uma lista de [[conjuntos disjuntos]] identificados por um elemento representante. Para implementar essa estrutura, cada elemento armazena um id (número de identificação), um ponteiro para o pai, e, em algoritmos eficientes, o tamanho do conjunto ou um valor de classificação. Inicialmente, cada elemento representa um subconjunto.

[[Imagem:Dsu disjoint sets init.svg|thumb|360px|Estado inicial da busca-união.]]

Os ponteiros para pai são arranjados de forma a constituir uma ou mais [[Árvore (estrutura de dados)|'''árvores''']], cada uma representando um conjunto. Se um elemento não possui um ponteiro para outro elemento, então ele é a '''raiz''' da árvore e, logo, o representante do conjunto. Caso contrário, se um elemento aponta para outro, então ele pertence ao conjunto representado pelo elemento que é a raiz da árvore.

== Operações ==

O '''algoritmo união-busca (Union-Find)''' executa três operações na estrutura de dados:

=== Construção ===
A operação de ''Construção'' cria um novo conjunto iniciando cada elemento com um id exclusivo, um ranque de 0 e um ponteiro para ele mesmo. O ponteiro pai para si mesmo indica que o elemento é o membro representativo de seu próprio conjunto.

A operação ''Construção'' tem complexidade de tempo{{tmath|O(n)}}.

=== Busca ===
A operação de busca determina em qual subconjunto um elemento em particular está. ''Busca (x)'' segue a cadeia de ponteiros pai de ''x'' da árvore até atingir um elemento raiz, cujo pai é ele mesmo.  Esse elemento raiz é o membro representativo do conjunto ao qual ''x'' pertence e pode ser ''x''.

Para melhorar a eficiência da busca geralmente são aplicados métodos que diminuem a profundidade das árvores formadas pelos subconjuntos:

==== Compactação de caminho ====
''A compactação de caminho'' nivela a estrutura da árvore fazendo com que cada nó aponte para a raiz sempre que ''Busca'' for usado nele.  Isso é válido, pois cada elemento visitado no caminho para uma raiz faz parte do mesmo conjunto.  A árvore resultante acelera as operações futuras não apenas nesses elementos, mas também naqueles que os referenciam.

[[Robert Tarjan|Tarjan]] e Van Leeuwen também desenvolveram algoritmos ''Busca'' de uma passagem que são mais eficientes na prática, mantendo a mesma [[complexidade de pior caso]]: divisão de caminho e redução de caminho.<ref name="Tarjan19842">{{Citar periódico|titulo=Worst-case analysis of set union algorithms|jornal=Journal of the ACM|volume=31|doi=10.1145/62.2160}}</ref>

==== Redução de caminho ====
A ''redução de caminho'' faz com que todos os demais nós no caminho apontem para seu avô.

==== Divisão de caminho ====
''A divisão do caminho'' faz com que cada nó no caminho aponte para seu avô.

==== Pseudo-código ====
{| class="wikitable"
|+Pseudo-código
!Compressão de caminho
!Caminho, metade,
!Divisão de caminho
|-
|
  '''função''' ''Busca''(x)
    se x.pai != x
      x.pai := ''Busca'' (x.pai)
    return x.pai
|
  '''função''' ''Busca''(x)
    enquanto x.pai != x
      x.pai := x.pai.pai
      x := x.pai
    return x
|
  '''função''' ''Busca''(x)
    enquanto x.pai != x
      x, x.pai := x.pai, x.pai.pai
    return x
|}
<br />

=== União ===
''União (x, y)'' usa ''Busca'' para determinar as raízes das árvores a que ''x e'' ''y'' pertencem.  Se as raízes são distintas, as árvores são combinadas ligando a raiz de uma à raiz da outra.  Se isso for feito ingenuamente, como fazendo ''x'' um filho de ''y'' toda vez que União for chamada, a altura das árvores pode crescer proporcionalmente a n.  Para evitar isto, as operações ''união por classificação'' ou ''união por tamanho'' são usadas.

==== União por classificação ====
''União por classificação'' sempre atribui a árvore mais compacta (com menor classificação) à raiz da árvore mais alta.  Assim, a árvore resultante não é mais alta que as originais, a menos que tenham a mesma altura, caso em que a árvore resultante é mais alta em um nó.

Para implementar ''união por classificação'' , cada elemento é associado a uma classificação.  Inicialmente, um conjunto tem um elemento e uma classificação de zero.  Se dois conjuntos forem unidos e tiverem a mesma classificação, a classificação do conjunto resultante será maior; caso contrário, se dois conjuntos forem unidos e tiverem classificações diferentes, a classificação do conjunto resultante será a maior dos dois.  As classificações são usadas em vez de altura ou profundidade, porque a compressão do caminho mudará a altura das árvores com o tempo.

==== União por tamanho ====
''União por tamanho'' sempre anexa a árvore com menos elementos à raiz da árvore que possui mais elementos.

==== Pseudo-código ====
{| class="wikitable"
|+Pseudo-código
!União por classificação
!União por tamanho
|-
|
  '''função''' ''União'' (x, y)
    xRoot   : = ''Busca'' (x)
    yRoot   : = ''Busca'' (y)

    <u>// x e y já estão no mesmo conjunto</u>
    se xRoot == yRoot
        Retorna

    <u>// x e y não estão no mesmo conjunto, então nós mesclamos</u>
    if xRoot.rank <yRoot.rank
      xRoot, yRoot   : = yRoot, xRoot // troca xRoot e yRoot

    <u>// fundir o yRoot no xRoot</u>
    yRoot.pai   : = xRoot
    if xRoot.rank == yRoot.rank:
      xRoot.rank   : = xRoot.rank + 1
|
  '''função''' ''União'' (x, y)
    xRoot   : = ''Busca'' (x)
    yRoot   : = ''Busca'' (y)

    <u>// x e y já estão no mesmo conjunto</u>
    se xRoot == yRoot
        Retorna

    <u>// x e y não estão no mesmo conjunto, então nós mesclamos</u>
    if xRoot.size <yRoot.size
      xRoot, yRoot   : = yRoot, xRoot // troca xRoot e yRoot

    <u>// fundir o yRoot no xRoot</u>
    yRoot.pai   : = xRoot
    xRoot.size   : = xRoot.size + yRoot.size
|}
<br />{{Referências}}

{{Esboço-estrutura de dados}}
{{Estrutura de dados}}

[[Categoria:Algoritmos]]
[[Categoria:Estruturas de dados]]