O (1) Algoritmo Para determinar si el nodo es descendiente de otro nodo en un árbol múltiple?

StackOverflow https://stackoverflow.com/questions/6020369

Pregunta

Imagina el siguiente árbol: 

    A
   / \
  B   C
 / \   \
D   E   F

Estoy buscando una forma de consultar si, por ejemplo, F es un descendiente de A (Nota: F no necesita ser un descendiente strong> de A), que, en este particular El caso sería cierto. Solo una cantidad limitada de los posibles nodos de los padres debe ser probada contra un grupo de nodo descendientes más grande.

Al probar si un nodo es un descendiente de un nodo en el grupo de padres potenciales, debe probarse contra todos los nodos posibles para padres.

Esto es lo que se le ocurrió:

  • Convertir árbol de múltiples vías a un trie, es decir, asignar los siguientes prefijos a cada nodo en el árbol anterior: 

     A = 1
 B = 11
 C = 12
 D = 111
 E = 112
 F = 121

  • Luego, reserve una matriz de bits para cada tamaño de prefijo posible y agregue los nodos primarios para ser probados, es decir, si C se agrega al grupo de nodos padre potencial, haz: 

      1    2    3  <- Prefix length

*[1]  [1]  ...
 [2] *[2]  ...
 [3]  [3]  ...
 [4]  [4]  ...
 ...  ...

  • Cuando se prueba si un nodo es un descendiente de un nodo padre potencial, tome su prefijo Trie, busque el primer carácter en la primera "matriz de prefijo" (ver arriba) y si está presente, busque el segundo prefijo carácter en la segunda "matriz de prefijo" y así sucesivamente, es decir, la prueba F conduce a: 

     F = 1    2    1

   *[1]  [1]  ...
    [2] *[2]  ...
    [3]  [3]  ...
    [4]  [4]  ...
    ...  ...

    SO SÍ F, es un descendiente de c.

    Esta prueba parece ser el peor de los casos O (n), donde n= longitud máxima del prefijo= profundidad máxima del árbol, por lo que su peor caso es exactamente igual a la manera obvia de subir al árbol y comparar los nodos. Sin embargo, esto funciona mucho mejor si el nodo probado está cerca de la parte inferior del árbol y el nodo padre potencial está en algún lugar en la parte superior. La combinación de ambos algoritmos mitigaría los peores escenarios de casos. Sin embargo, la sobrecarga de la memoria es una preocupación.

    ¿Hay otra forma de hacer eso? Cualquier puntero muy apreciado!

¿Fue útil?

Solución

¿Son tus árboles de entrada siempre estáticos?Si es así, puede usar un algoritmo de ancestro común más bajo para responder a la pregunta descendiente en O (1) tiempo con una construcción de tiempo / espacio de O (n).Se administra una consulta de LCA dos nodos y se le pregunta cuál es el nodo más bajo en el árbol cuyo subárbol contiene ambos nodos.Luego, puede responder a la consulta isdescendente con una sola consulta LCA, si LCA (A, B)== A o LCA (A, B)== B, entonces uno es el descendiente del otro.

esta Topcoder Algorithm Tuorial ofrece una discusión exhaustiva del problema yAlgunas soluciones en varios niveles de complejidad / eficiencia del código.

Otros consejos

No sé si esto se ajustaría a su problema, pero una forma de almacenar jerarquías en bases de datos, con las características rápidas "Dame todo desde este nodo y hacia abajo" es almacenar una "ruta".

Por ejemplo, para un árbol que se ve así: 

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

Albergaría las filas de la siguiente manera, suponiendo que la letra en el árbol de arriba es la "ID" de cada fila: 

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

Para encontrar todos los descendientes de un nodo en particular, usted haría una consulta "Startswith" en la columna Ruta, es decir.Todos los nodos con un camino que comienza con a*c*

Para averiguar si un nodo en particular es un descendiente de otro nodo, vería si la ruta más larga comenzó con la ruta más corta.

así, por ejemplo:

  • E es un descendiente de A, ya que a*c*e comienza con a
  • D es un descendiente de C, ya que a*c*d comienza con a*c

    ¿Sería útil en su instancia?

Atravesando cualquier árbol requerirá "Pasos de profundidad de árboles". Por lo tanto, si mantiene una estructura de árbol equilibrada, es demostrable que necesite O (log N) Operaciones para su operación strong>. De lo que entiendo, su árbol se ve especial y no puedes mantenerlo de forma equilibrada, ¿verdad? Por lo que O (n) será posible. Pero esto es malo durante la creación del árbol de todos modos, por lo que probablemente morirá antes de usar la lookup de todos modos ...

Dependiendo de la frecuencia con la que necesitará esa operación de búsqueda en comparación con inserto , podría decidir pagar durante insertar para mantener un datos adicionales estructura. Sugeriría un hashing si realmente lo necesitas> necesito amortizado O (1) . En cada operación de inserción, le pones todos los padres de un nodo en un hashtable. Por su descripción, esto podría ser O (N) artículos en un inserto . Si lo hace n inserciones esto suena mal (hacia o (n ^ 2) ), pero en realidad su árbol no puede degradarse que malo, por lo que es probable que obtenga un tamaño agradable general amortizado de O (n log n) . (En realidad, la parte log n depende del grado de la degración de su árbol. Si espera que sea el máximo degradado, no lo hagas).

Por lo tanto, usted pagará sobre O (log n) en cada inserto , y obtenga la eficiencia hashtable o (1) para un < strong> búsqueda .

Para un árbol m-way, en lugar de la matriz de bits, ¿por qué no solo almacenar el binario "trie id" (usando m bits por nivel) con cada nodo?Para su ejemplo (asumiendo m== 2) : A=0b01, B=0b0101, C=0b1001, ...

Luego, puede hacer la prueba en O (1): 

bool IsParent(node* child, node* parent)
{ 
   return ((child->id & parent->id) == parent->id)
}

Podría comprimir el almacenamiento en ceil (lg2 (m)) bits por nivel si tiene un rápido Findmsb () Función que devuelve la posición del conjunto de bits más significativo: 

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);

En un truco de pre-orden, cada conjunto de descendientes es contiguo.Por su ejemplo, 

A B D E C F
+---------+ A
  +---+ B
    + D
      + E
        +-+ C
          + F

Si puede preprocesar, entonces todo lo que necesita hacer es numerar cada nodo y calcular el intervalo descendiente.

Si no puede preprocesar, entonces un enlace / árbol de corte ofrece o (LOG N) Rendimiento para tanto actualizaciones como consultas.

Puede responder a la consulta del formulario "¿Es un nodo un descendiente de nodo B?"En constante tiempo, solo usando dos matrices auxiliares.

preprocesar el árbol, visitando en pong-pippor, y para cada nodo A almacenamiento su tiempo de inicio y finalización en la visita en las dos matrices comienzan [] y termine [].

Por lo tanto, digamos que el final [U] y comience [U], respectivamente, es el tiempo final y de inicio de la visita del nodo u.

Luego, el nodo U es un descendiente del nodo V si y solo si:

Iniciar [V] <= Iniciar [U] y terminar [U] <= Fin [v].

y usted ha terminado, verificar esta condición requiere solo dos búsqueda en las matrices iniciar y finalizar

Take a look at Nested set model It's very effective to select but too slow to update

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top