# União-busca

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 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. Em 1973, a complexidade do algoritmo foi definida como $O(\log ^{*}(n))$, a função Logaritmo iterado de $n$. Mas em 1975, Robert Tarjan foi o primeiro a provar $O(\alpha (n))$(Função Inversa de Ackermann) como novo limitante superior para o algoritmo, e, em 1979, mostrou que a mesma função era limitante inferior para um caso específico.
Em 1989, Fredman e Saks mostraram que $\Omega (\alpha (n))$elementos são acessados por qualquer estrutura de dados união-busca para cada operação executada (custo amortizado).

## 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.
Os ponteiros para pai são arranjados de forma a constituir uma ou mais á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$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.
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.

#### 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

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 |

### 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

Pseudo-código :
| União por classificação | União por tamanho |
| função União (x, y) xRoot : = Busca (x) yRoot : = Busca (y) // x e y já estão no mesmo conjunto se xRoot == yRoot Retorna // x e y não estão no mesmo conjunto, então nós mesclamos if xRoot.rank <yRoot.rank xRoot, yRoot : = yRoot, xRoot // troca xRoot e yRoot // fundir o yRoot no xRoot 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) // x e y já estão no mesmo conjunto se xRoot == yRoot Retorna // x e y não estão no mesmo conjunto, então nós mesclamos if xRoot.size <yRoot.size xRoot, yRoot : = yRoot, xRoot // troca xRoot e yRoot // fundir o yRoot no xRoot yRoot.pai : = xRoot xRoot.size : = xRoot.size + yRoot.size |