En informática , union-find es una estructura de datos que representa una partición de un conjunto finito (o equivalentemente una relación de equivalencia ). Básicamente tiene dos operaciones find y unite y se llama union-find , siguiendo la terminología inglesa:
Otra operación importante, MakeSet , construye una clase de equivalencia que contiene un solo elemento, es decir, un singleton .
Para definir estas operaciones con mayor precisión, debemos elegir una forma de representar las clases. El enfoque tradicional consiste en seleccionar un elemento particular de cada clase, llamado representante , para identificar a toda la clase.
En una llamada, Find (x) devuelve el representante de la clase de x .
La solución más inmediata al problema de las clases disjuntas es crear una lista vinculada para cada clase.
El elemento en la parte superior de la lista se elige como representante.
MakeSet crea una lista que contiene un elemento. Union concatena las dos listas, una operación de tiempo constante. Desafortunadamente, la operación de búsqueda requiere un tiempo Ω ( n ) con este enfoque.
Esto se puede remediar agregando a cada elemento de una lista vinculada un puntero al encabezado de la lista; A continuación, la búsqueda se realiza en tiempo constante (el representante es el jefe de la lista). Sin embargo, hemos deteriorado la eficiencia de Union , que ahora debe iterar a través de todos los elementos de una de las dos listas para apuntar al encabezado de la otra lista, que requiere un tiempo Ω ( n ).
Podemos mejorar esto agregando siempre la más pequeña de las dos listas al final de la más larga, lo que se llama la heurística de la unión ponderada . Esto requiere mantener la longitud de las listas a medida que avanzan las operaciones. Con esta solución, una secuencia de m operaciones MakeSet , Union y Find en n elementos requiere O ( m + n log n ).
Para obtener mejores resultados, debemos considerar una estructura de datos diferente.
Ahora consideramos una estructura de datos en la que cada clase está representada por un árbol en el que cada nodo contiene una referencia a su nodo padre. Esta estructura forestal fue introducida por Bernard A. Galler y Michael J. Fisher en 1964, aunque su análisis detallado llevó varios años.
En tal bosque, el representante de cada clase es la raíz del árbol correspondiente. Find solo sigue los enlaces a los nodos principales hasta que llega a la raíz. Union une dos árboles atando la raíz de uno a la raíz del otro. Una forma de escribir estas operaciones es la siguiente:
fonction MakeSet(x) x.parent := null fonction Find(x) si x.parent == null retourner x retourner Find(x.parent) fonction Union(x, y) xRacine := Find(x) yRacine := Find(y) si xRacine yRacine xRacine.parent := yRacineEn esta forma ingenua, este enfoque no es mejor que el de las listas enlazadas, ya que los árboles creados pueden estar muy desequilibrados. Pero se puede mejorar de dos formas.
La primera es atar siempre el árbol más pequeño a la raíz del árbol más grande, y no al revés. Para evaluar qué árbol es el más grande, usamos una heurística llamada rango : los árboles que contienen un elemento son de rango cero, y cuando se unen dos árboles del mismo rango, el resultado tiene un rango mayor que una unidad. Solo con esta mejora, la complejidad amortizada de las operaciones MakeSet , Union y Find se convierte en el peor y el mejor de los casos. Aquí están los nuevos códigos para y : MakeSetUnion
fonction MakeSet(x) x.parent := x x.rang := 0 fonction Union(x, y) xRacine := Find(x) yRacine := Find(y) si xRacine yRacine si xRacine.rang < yRacine.rang xRacine.parent := yRacine sinon yRacine.parent := xRacine si xRacine.rang == yRacine.rang xRacine.rang := xRacine.rang + 1La segunda mejora, denominada compresión de ruta , consiste en aprovechar cada Find para aplanar la estructura del árbol, de hecho, cada nodo que se encuentre en la ruta que conduce a la raíz se puede conectar directamente a él; porque todos estos nodos tienen el mismo ancestro. Para lograrlo, tomamos una ruta hacia la raíz, para determinarla, luego otra ruta para hacer de esta raíz la madre de todos los nodos encontrados en el camino. El árbol aplanado resultante mejora el rendimiento de futuras búsquedas de antepasados, pero también beneficia a otros nodos que apuntan a ellos, ya sea directa o indirectamente. Aquí está la operación Findmejorada:
fonction Find(x) si x.parent x x.parent := Find(x.parent) retourner x.parentEstas dos mejoras (fusión de raíz optimizada y compresión de trayectoria) son complementarias. Juntos, hacen posible lograr una complejidad amortiguada en el tiempo , donde la función es recíproca y la función de Ackermann, que crece extremadamente rápido. es menor que 5 para cualquier valor práctico. En consecuencia, la complejidad amortizada por la operación es de hecho una constante.
No es posible obtener un mejor resultado: Fredman y Saks demostraron en 1989 que las palabras en promedio deben leerse por operación en cualquier estructura de datos para el problema de las clases disjuntas. Dasgupta et al., En su libro algorítmico, presentan un análisis de complejidad amortiguada utilizando el logaritmo iterado .
La figura de la derecha muestra un ejemplo del uso de una estructura de datos de búsqueda de unión con 6 elementos a, b, c, d, e, f. Al principio, el bosque contiene 6 árboles de raíz: representa la relación de equivalencia donde cada elemento está solo en su clase de equivalencia. La operación de unión (a, b) conecta (por ejemplo) el nodo b a la raíz a. La operación de unión (c, d) conecta (por ejemplo) el nodo c a la raíz d. La operación de unión (a, c) conecta (por ejemplo) el nodo c al nodo a. La operación find (d) devuelve la raíz a, pero por cierto, conecta d directamente a la raíz a (compresión de ruta). La operación de unión (b, e) comienza buscando las raíces respectivas ay e. Como el rango de a es 1 y el de e es 0, conectamos el árbol e con el árbol a.
Esta estructura se utiliza a menudo para identificar los componentes conectados de un gráfico (consulte el artículo sobre algoritmos de conectividad basados en punteros ). Con el mismo espíritu, se utiliza para estudiar la percolación, con el algoritmo de Hoshen-Kopelman .
Union-Find también se utiliza en el algoritmo de Kruskal para encontrar un árbol de expansión de peso mínimo de un gráfico. Finalmente, se utiliza en algoritmos de unificación .