Algoritmos e Estruturas de Dados/Estruturas para classes de equivalência
Estruturas para classes de equivalência
Introdução
Definições
Uma relação binária $\equiv$ sobre um domínio ${\cal D}$ é uma relação de equivalência se satisfaz as seguintes propriedades \begin{eqnarray} \forall a, b \in {\cal D} \bullet a \equiv b \Leftrightarrow b \equiv a \mbox{ ($\equiv$ é simétrica)} \\ \forall a \in {\cal D} \bullet a \equiv a \mbox{ ($\equiv$ é reflexiva)} \\ \forall a, b, c \bullet a \equiv b \land b \equiv c \Rightarrow a \equiv c \mbox{ ($\equiv$ é transitiva)} \end{eqnarray}
Seja $a \in {\cal D}$ um elemento do domínio, a classe de equivalência de $a$ é o conjunto ${x \in {\cal D} \mid x \equiv a}$ dos elementos relacionados com $a$.
Objetivos
O objetivo é definir um tipo abstrato de dados que permita representar e manipular eficientemente classes de equivalência que evoluem dinamicamente, podendo tanto ser criada novas classes, quanto juntadas classes existentes. Também queremos ter uma operação que permite determinar a classe de equivalência de um elemento.
Para tanto, consideramos que o cliente do tipo abstrato de dados manipula valores de um determinado domínio que nomeamos domain.
O tipo abstrato de dados possuirá três operações: criação de uma nova classe, busca da classe de um valor, e união de duas classes.
- criação de uma nova classe de equivalência
- dado um elemento d de domain, cria uma nova classe comportando apenas como elemento d e retorna o handler associado a d. O cliente apenas poderá acessar a classe de d através desse handler. Portanto, é da responsabilidade do cliente manter uma associação entre valores e handlers dos valores.
- busca da classe de equivalência
- dado o handler de um elemento d de domain, retorna a classe de d.
- união de duas classes de equivalência
- dado os handlers de dois elementos d1 e d2 de domain, realiza a união das duas classes de equivalência de d1 e d2.
Apresentação das soluções
Os algoritmos e estruturas de dados que provêm implementação eficientes desse tipo abstrato de dados são conhecidos como algoritmos Union-Find (União-Busca), pelo tipo de operações que são providas. Outros nomes encontrados são disjoint sets (conjuntos disjuntos) e dynamic equivalence relations (relações de equivalência dinâmicas).
Existe basicamente duas estruturas de dados para implementar o tipo abstrato União-Busca: a baseada em listas, e a baseada em árvores. A estrutura de dados linear, baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a estrutura de dados ramificada, baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas.