¿Cuál es una buena estructura de datos para crear clases de equivalencia en los nodos de un árbol?

Question

Estoy buscando una buena estructura de datos para crear clases de equivalencia en los nodos de un árbol. En una estructura ideal, las siguientes operaciones deben ser rápido (O (1)/O (n) según el caso) y fácil (no hay párrafos de código misterio):

• (A) recorrer el árbol de la raíz; en cada nodo -> transición niño enumerar todas las versiones equivalentes del nodo hijo
• (B) Combinar dos clases de equivalencia
• (C) Crear nuevos nodos de una lista de nodos existentes (los niños) y otros datos de
• (D) Busca nodos estructuralmente equivalentes a nodo (es decir, tienen el mismo número de hijos, los hijos correspondientes pertenecen a la misma clase de equivalencia y sus "otros datos" son iguales) para que los nodos nuevos (o modificados) colocarse en la clase de equivalencia correcta (a través de una fusión)

Hasta ahora he considerado (algunos de estos podrían usarse en combinación):

• Un parfait, donde los niños son referencias a colecciones de nodos en lugar de a nodos. (A) es rápido, (B) requiere caminar por el árbol y actualizar nodos para apuntar a la colección fusionada, (C) requiere encontrar la colección que contiene cada hijo del nuevo nodo, (D) requiere caminar por el árbol
• Mantenimiento de un árbol hash de nodos por sus características. Esto hace que (D) sea mucho más rápido pero (B) más lento (ya que el hash debería actualizarse cuando se fusionaron las clases de equivalencia)
• Enlaza los nodos en una lista circular vinculada. (A) es rápido, (B) sería rápido, pero por el hecho de que esa parte de "fusión" de una lista circular con ella misma realmente divide la lista (C) sería rápida, (D) requeriría caminar por el árbol
• Al igual que arriba, pero con un puntero "arriba" adicional en cada nodo, que podría usarse para encontrar un miembro canónico de la lista circular.

¿Estoy perdiendo una dulce alternativa?

Answer 1

Parece que tiene que lidiar con dos formas de equivalencia. Equivalencia simple (A), rastreada como clases de equivalencia que se mantienen actualizadas y equivalencia estructural (D), para la cual ocasionalmente se construye una única clase de equivalencia y luego se descarta.

Me parece que el problema sería conceptualmente más simple si mantiene las clases de equivalencia tanto para la equivalencia simple como estructural. Si eso introduce demasiado abandono para la equivalencia estructural, podría mantener clases de equivalencia para algunos aspectos de la equivalencia estructural. Luego, podría encontrar un equilibrio donde pueda pagar el mantenimiento de esas clases de equivalencias, pero aún así reducir en gran medida la cantidad de nodos que se examinarán al construir una lista de nodos estructuralmente equivalentes.

Answer 2

No creo que ninguna estructura vaya a resolver sus problemas, pero podría echarle un vistazo al Disjoint-set data structure. Una clase de equivalencia, después de todo, es lo mismo que una partición de un conjunto. Debería ser capaz de manejar algunas de esas operaciones rápidamente.

Answer 3

Dando un paso atrás por un momento, sugeriría no usar ningún árbol. La última vez que tuve que enfrentar un problema similar, comencé con un árbol, pero luego pasé a una matriz.

Razones que son múltiples pero la razón número uno es el rendimiento, mis clases con hasta 100 o más niños funcionarían mejor manipulándolas como matriz que a través de los nodos de un árbol, principalmente por ubicación de hardware y recuperación previa de CPU lógica y canalización de CPU.

Entonces, aunque algorítmicamente una estructura de matriz requiere un N mayor de operaciones que un árbol, realizar estas docenas de operaciones es probablemente más rápido que perseguir punteros en la memoria.