Bosque de conjuntos disjuntos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de noviembre de 2019; la verificación requiere 1 edición .

El bosque de conjuntos disjuntos es una estructura de datos en forma de árbol para conjuntos disjuntos . (a veces llamado Sistema de conjuntos disjuntos )

Establecer representaciones

Cada conjunto se representa como un árbol enraizado . En un bosque de conjuntos disjuntos, cada nodo contiene un elemento de conjunto y apunta solo a su nodo principal. La raíz de cada árbol contiene un representante y es el padre de sí mismo.

Las operaciones sobre el bosque de conjuntos disjuntos se realizan de la siguiente manera:

MAKE_SET: crea un árbol con un nodo.

FIND_SET: nos movemos a lo largo de los enlaces principales hasta la raíz del árbol.

UNIÓN: establece el puntero de la raíz de un árbol en la raíz de otro.

Heurísticas para la eficiencia

Asociación por rango. La idea de la heurística es que cuando se realiza la operación UNION, la altura del árbol resultante, si es posible, no aumenta. Para ello se utiliza el rango característico de cada raíz, que es el límite superior de la altura del nodo. La operación MAKE_SET crea una raíz con rango 0. La operación UNION, que en este caso se llama unión por rango, funciona de la siguiente manera:

Si los rangos de las raíces son diferentes, la raíz con el rango más bajo apunta a la raíz con el rango más alto. Los rangos raíz no cambian.
Si los rangos de las raíces son iguales, cualquiera de las raíces apunta a la otra. El rango de la raíz apuntada por otra raíz se incrementa en 1.

Compresión de ruta. La heurística durante la operación FIND_SET hace que cada nodo (que se encuentra al subir a la raíz) apunte directamente a la raíz. La compresión de rutas no cambia los rangos de los nodos.

Pseudocódigo

Considere un ejemplo de implementación de un bosque de conjuntos disjuntos. En el arreglo p almacenaremos un enlace al nodo padre, y en el arreglo r el rango del vértice.

operación MAKE_SET(x) p[x] = x r[x] = 0 operación FIND_SET(x) si x ≠ p[x] entonces p[x] = ENCONTRAR_CONJUNTO(p[x]) devolver p[x] operación UNION(x, y) si r[x] > r[y] entonces p[y] = x más p[x] = y si r[x] = r[y] entonces r[y] = r[y] + 1

Horario de apertura

Cuando se aplican por separado, la unión de rangos y la compresión de rutas conducen a un aumento en la eficiencia de las operaciones en un bosque de conjuntos disjuntos. La unión por rango en sí da el tiempo de ejecución , donde es el número total de operaciones y es el número de elementos en el sistema. La compresión de ruta en sí misma da como resultado el tiempo de ejecución en el peor de los casos , donde es el número de operaciones FIND_SET. La aplicación de ambas heurísticas da el tiempo de ejecución del peor de los casos , donde es la función inversa de Ackermann . Esta estimación es un límite inferior del tiempo de operación con conjuntos disjuntos, por lo que el bosque de conjuntos disjuntos es la estructura óptima para conjuntos disjuntos. $O(m~\lg{n})$ $metro$ $norte$ $O(n + f~\log_{2 + f/n}{n})$ $F$ $O(m\ \alpha(n, m))$ $\alfa(n, m)$

Enlaces

Visualizador de estructura de datos

Literatura

Thomas Kormen et al Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 2ª ed. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .