algorithm - programacion - Unión/encontrar algoritmo sin unión por rango para la estructura de datos de bosques de conjuntos disjuntos

union find c++

Question

Aquí hay un desglose del algoritmo de unión / búsqueda para bosques de conjuntos desunidos en wikipedia :

• Barebone desunen bosques establecidos ... ( O(n) )
  • ... con unión por rango ... (ahora mejorado a O(log(n) )
    • ... con compresión de ruta (ahora mejorada a O(a(n)) , efectivamente O(1) )

La implementación de la unión por rango requiere que cada nodo mantenga un campo de rank para propósitos de comparación. Mi pregunta es, ¿vale la pena la unión por rango este espacio adicional? ¿Qué sucede si omito la unión por rango y simplemente hago compresión de ruta? ¿Es lo suficientemente bueno? ¿Cuál es la complejidad amortizada ahora?

Se hace un comentario que implica que la unión por rango sin compresión de ruta (amortizado O(log(n) complejidad) es suficiente para la aplicación más práctica. Esto es correcto. Lo que pregunto es al revés: ¿qué sucede si omite la unión?) por rango y SOLO hacer compresión de ruta en su lugar?

En cierto sentido, la compresión de ruta es un paso adicional para mejorar la unión por rango, y es por eso que ese paso adicional se puede omitir sin consecuencias desastrosas. Pero, ¿es la unión por rango un paso intermedio necesario para la compresión del camino? ¿Puedo omitirlo e ir directamente a la compresión de ruta, o será catastrófico?

También se señaló que sin unión por rango, los sindicatos repetidos podrían crear una estructura similar a una lista enlazada. Esto significa que una operación de compresión de ruta única podría tomar O(n) en el peor de los casos. Por supuesto, esto afectaría las operaciones futuras, por lo tanto, lo que más me interesa es cómo se juega esto cuando se amortiza en muchas operaciones.

Answer 1

Busqué en Google para "sin unión por rango" y el segundo enlace que surgió fue este :

... Cerramos esta sección con un análisis de unión-encontrar con compresión de ruta pero sin unión por rango ...

La estructura de datos union-find con compresión de ruta pero sin procesos de unión por rango m find y n-1 enlace operaciones en el tiempo O ((m + n) log n)

Answer 2

La compresión del camino aplana la estructura del árbol. Unión por rango ayuda a fusionarse. Supongamos que te saltas este último. Entonces, ahora tienes un bosque sin información de rango para elegir cómo fusionar. Potencialmente, ahora corre el riesgo de fusionar un árbol con una profundidad mayor a uno con una profundidad menor, lo que lleva a una estructura de árbol desequilibrada. En el peor de los casos, puede terminar con una lista vinculada. La complejidad del tiempo amortizado de su Unión aumenta incluso si para Find sigue igual.

En mi opinión, sería mejor omitir la compresión de ruta pero no la clasificación.