3.2. Relaciones de equivalencia.
Observaciones:
- Sólo es necesario conocer en qué clase de equivalencia está cada elemento, no el valor asociado a cada clase.
- El nombre del conjunto es arbitrario, lo que importa es que Encuentra(x)= Encuentra(y) si y sólo si x, y están en la misma clase de equivalencia.
Representaciones sencillas:
- Numerar los elementos de 1 a n. En un vector almacenar el nombre de la clase de equivalencia a la que pertenece cada elemento i.
- Encuentra(x, C): Devolver el valor del array, O(1).
- Unión(a, b, C): Cambiar el valor de uno de los grupos, O(n).
- Representar las clases de equivalencia con listas enlazadas. Enlazar los elementos de una misma clase de equivalencia mediante una lista.
- Encuentra(x, C): Buscar en qué lista está el elemento x, O(n).
- Unión(a, b, C): Unir dos listas, O(1).
Solución: Representación mediante árboles.
- Cada árbol representa una clase. El nombre de la raíz es el nombre de la clase.
- Sólo necesitamos saber el padre de cada nodo: representación de punteros al padre.