Unión / algoritmo de encontrar sin una unión por rango de estructura de datos bosques disjuntos-set

Question

He aquí un desglose de la unión / algoritmo para encontrar bosques conjunto disjuntos en Wikipedia :

• Barebone bosques disjuntos-set ... (O(n))
  • ... con la unión por rango ... (ahora mejorado para O(log(n))
    • ... con compresión de caminos (ahora mejorado para O(a(n)), efectivamente O(1))

La implementación de la unión por rango requiere que cada nodo mantiene un campo rank a efectos comparativos. Mi pregunta es, es la unión por valor de rango este espacio adicional? ¿Qué ocurre si me salto unión por rango y sólo hago compresión de caminos en su lugar? ¿Es lo suficientemente bueno? ¿Cuál es la complejidad amortizado ahora?

---

Se hace un comentario que implica que la unión por rango y sin compresión de caminos (O(log(n) complejidad amortizado) es suficiente para la mayoría de aplicaciones prácticas. Esto es correcto. Lo que estoy pidiendo es al revés: ¿qué si se salta la unión por rango y sólo lo hacen compresión de caminos en lugar

En un sentido, la compresión de ruta es un paso adicional para mejorar la unión por rango, y es por eso que el paso adicional puede ser omitida sin consecuencias desastrosas. Pero es la unión por el rango de un paso intermedio necesario para la compresión de ruta? Puedo evitarlo y vaya directamente a la compresión de caminos, o que voy a ser catastrófico?

---

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

Answer 1

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

  

... Cerramos esta sección con una   análisis de unión-con la ruta   compresión, pero sin una unión por   Ranking ...

     

La unión-estructura de datos con la ruta   compresión, pero sin una unión por rango   procesos de M encontrar y n-1 enlace   operaciones en tiempo O ((m + n) log n)

Answer 2

compresión de caminos aplana la estructura de árbol. Unión por el rango ayuda a la fusión. Suponga que se salta este último. Así que ahora, tiene un bosque sin información de rango para elegir cómo fusionar. Potencialmente, que ahora corre el riesgo de fusión de un árbol con una profundidad mayor a uno con una profundidad menor - que conduce a una estructura de árbol desequilibrado. En el peor de los casos, usted puede terminar con una lista enlazada. amortizado complejidad del tiempo de su Unión aumenta incluso si eso para Buscar sigue siendo el mismo.

OMI, sería mejor omitir compresión de caminos, pero no rango.