En computación, una estructura de datos para conjuntos disjuntos, es una estructura de datos que mantiene un conjunto de elementos particionados en un número de conjuntos disjuntos(no se solapan los conjuntos).Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en esta estructura de datos: La otra operación importante CrearConjunto es generalmente trivial, esta crea un conjunto con un elemento dado.
Entonces Buscar(x) retorna el elemento representativo del conjunto al cual x pertenece , y Unión toma como argumento dos elementos representativos de dos conjuntos respectivamente.
El problema de esta implementación es que Buscar(x) requiere Ω(n) u orden lineal para recorrer de atrás hacia adelante, desde el elemento dado hasta la cabeza de la lista.
Esto puede ser evitado añadiendo a cada nodo de la lista enlazada un puntero a la cabeza de la lista; por tanto Buscar toma tiempo constante.
Pero ahora Unión ahora tiene que actualizar a cada elemento de la lista que está siendo concatenada una referencia a la cabeza de la nueva lista combinada, requiriendo Ω(n) tiempo.
Usando esta heurística llamada weighted-union, una secuencia de m operaciones de CrearConjunto, Unión y Buscar sobre n elementos requiere O(m + nlog n) tiempo.
[1] Para operaciones asintóticamente más rápidas otra estructura de datos es necesaria.
Quisiéramos poder mezclar cualquiera dos de estas listas, y actualizar todos sus nodos para que sigan teniendo el nombre de la lista a la que pertenecen.
y se actualizan los elementos que pertenecen a
Quisiéramos contar en el peor caso cuántas veces el elemento
Entonces finalmente, la pregunta es ¿Cuántas veces puede un número doblar su tamaño antes de que llegue a
en esta estructura pues todos los nodos contienen el nombre de la lista a la cual pertenecen.
Los Bosques de Conjuntos-Disjuntos son estructuras de datos donde cada conjunto está representado por un árbol , en el cual cada nodo mantiene una referencia a su nodo padre (ver pila espagueti).
Estos fueron descritos primeros por Bernard A. Galler y Michael J. Fisher en 1964,[2] tomando años para su preciso análisis.
Buscar sigue por los padres nodos hasta encontrar la raíz del árbol.
Una manera de implementar esto puede ser: En esta simple forma, este implementación no es mejor que la implementación basada en listas enlazadas, porque el árbol que se crea puede ser muy desbalanceado; de todas maneras , esto puede ser mejorado de dos formas.
La primera forma, se llama unión por rank, consiste en siempre añadir el árbol más pequeño a la raíz del árbol más grande.
Pseudocódigo del CrearConjunto y Unión mejorado: La segunda mejora, llamada compresión de camino, es una forma de aplanar la estructura del árbol cuando se aplique Buscar.
La idea es que cada nodo visitado en el camino hacia la raíz puede ser añadido directamente a la raíz; todos ellos comparten el mismo representativo.
Para lograr este efecto, mientras Buscar recursivamente se mueve hacia la raíz, este cambia la referencia del padre del nodo a la raíz que encuentre.
El árbol resultante es más aplanado, acelerando operaciones futuras no solo en estos elementos sino también en aquellos que referencian a estos.
Aquí va el Buscar mejorado: Estas dos técnicas se complementan una a otra; aplicadas juntas, el tiempo amortizado es solo
es menor que 5 para todos los prácticamente remotos valores de
Por tanto el tiempo de ejecución amortizado es efectivamente una pequeña constante.
Este modelo también puede utilizarse para verificar si dos vértices pertenecen a una misma componente conexa, o para comprobar si al añadir una arista entre dos vértices se forma un ciclo.
El algoritmo Unión-Buscar es usado en implementaciones muy eficientes de Unificación.
[3] Esta estructura de datos es usada por la librería Boost Graph Library para implementar su funcionalidad de Componentes Conexas Incrementales.
Mientras que las ideas usadas en conjuntos disjuntos son bien familiar, Robert Tarjan fue el primero en demostrar la cota superior (y la versión restricta de la cota inferior) en términos de la función de Ackermann en 1975.
[4] Hasta este momento la mejor cota lograda por operación demostrada por Hopcroft y Ullman,[5] era
Tarjan y Van Leeuwen implementaron también algoritmos de Buscar en una sola pasada manteniendo la misma complejidad computacional en el peor de los casos.