Usuário(a):Gabrandao/Disjoint-set data structure

A operação de Construção cria um novo conjunto iniciando cada elemento com um id exclusivo, um rank 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 complexidade de tempoFalhou a verificação gramatical (SVG (MathML pode ser ativado através de uma extensão do ''browser''): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "http://localhost:6011/pt.wikipedia.org/v1/":): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|O(n)}} </mi><mo stretchy="false"> {{tmath|O(n)}} </mo><mi> {{tmath|O(n)}} </mi><mo stretchy="false"> {{tmath|O(n)}} </mo></mstyle></mrow> } $O(n)$ .

 função MakeSet ( x )
   se x ainda não estiver presente:
     adicione x à árvore do conjunto disjunto
     x.parent   : = x
     x.rank   : = 0
     x.size   : = 1

Busca

Busca (x) segue a cadeia de ponteiros pai de x aa á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 em si.

Compressã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 mais plana 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 Find 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. ^[1]

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

Compressão de caminho

Caminho, metade,

Divisão de caminho

 função Busca(x)
   se x.parent! = x
     x.parent   : = 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 proporcional a n. Para evitar esta união por classificação ou união por tamanho é usado.

Por classificação

União por classificação sempre atribui a árvore mais curta à raiz da árvore mais alta. Assim, a árvore resultante não é mais alta que os 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.

Por tamanho

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

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

Complexidade de tempo

Com nenhuma compactação de caminho (ou uma variante), união por classificação nem união por tamanho , a altura das árvores pode crescer proporcionalmente a n, o que implica que as operações de Busca e da União levarão tempo proporcional a n.

Usar a compactação de caminho sozinha dá um tempo de execução de pior caso para uma sequência de $n$ operações MakeSet (e, portanto, no máximo Falhou a verificação gramatical (erro de sintaxe): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>n-1} </mi><mo> $n-1$ </mo><mn> $n-1$ </mn></mstyle></mrow> </math> $n-1$ $n-1$ </img> Operações da União ) e $f$ Localizar operações.

Usando somente união por classificação dá um tempo de execução de (limite superior) para m operações de qualquer tipo. ^[2]

Usar a compactação de caminho, a divisão ou a redução pela metade e a união por classificação ou tamanho garante que o tempo amortizado por operação seja somente Falhou a verificação gramatical (SVG (MathML pode ser ativado através de uma extensão do ''browser''): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "http://localhost:6011/pt.wikipedia.org/v1/":): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O(\alpha(n))} </mi><mo stretchy="false"> $O(\alpha (n))$ </mo><mi> $O(\alpha (n))$ </mi><mo stretchy="false"> $O(\alpha (n))$ </mo><mi> $O(\alpha (n))$ </mi><mo stretchy="false"> $O(\alpha (n))$ </mo><mo stretchy="false"> $O(\alpha (n))$ </mo></mstyle></mrow> </math> $O(\alpha (n))$ $O(\alpha (n))$ </img> ^[1] ^[3] que é ideal, ^[4] onde Falhou a verificação gramatical (erro de sintaxe): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\alpha(n)} </mi><mo stretchy="false"> $\alpha (n)$ </mo><mi> $\alpha (n)$ </mi><mo stretchy="false"> $\alpha (n)$ </mo></mstyle></mrow> </math> $\alpha (n)$ $\alpha (n)$ </img> é a função inversa de Ackermann . Esta função tem um valor Falhou a verificação gramatical (erro de sintaxe): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\alpha(n)<5} </mi><mo stretchy="false"> $\alpha (n)<5$ </mo><mi> $\alpha (n)<5$ </mi><mo stretchy="false"> $\alpha (n)<5$ </mo><mo> $\alpha (n)<5$ </mo><mn> $\alpha (n)<5$ </mn></mstyle></mrow> </math> $\alpha (n)<5$ $\alpha (n)<5$ </img> para qualquer valor de $n$ que possa ser escrito nesse universo físico, as operações de conjunto disjunto ocorrem em um tempo essencialmente constante.

Uma demonstração para o Union-Find ao usar o algoritmo de Kruskal para encontrar a árvore de abrangência mínima.

[[Categoria:Artigos com pseudocódigo de exemplo]] [[Categoria:Algoritmos de busca]] [[Categoria:Estruturas de dados]] [[Categoria:!Páginas com traduções não revistas]]

↑ ^a ^b «Worst-case analysis of set union algorithms». Journal of the ACM. 31. doi:10.1145/62.2160
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «Chapter 21: Data structures for Disjoint Sets». Introduction to Algorithms. [S.l.: s.n.] ISBN 978-0-262-03384-8
↑ «A class of algorithms which require non-linear time to maintain disjoint sets». Journal of Computer and System Sciences. 18. doi:10.1016/0022-0000(79)90042-4
↑ «The cell probe complexity of dynamic data structures». Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing

[Tarjan1984-1] «Worst-case analysis of set union algorithms». Journal of the ACM. 31. doi:10.1145/62.2160

[Cormen2009-2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «Chapter 21: Data structures for Disjoint Sets». Introduction to Algorithms. [S.l.: s.n.] ISBN 978-0-262-03384-8

[Tarjan1979-3] «A class of algorithms which require non-linear time to maintain disjoint sets». Journal of Computer and System Sciences. 18. doi:10.1016/0022-0000(79)90042-4

[Fredman1989-4] «The cell probe complexity of dynamic data structures». Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing

[1]

[2]

[3]

[4]