Imagine 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 undirect descendiente de F), que, en este caso particular, sería cierto. Solo se necesita probar una cantidad limitada de nodos principales potenciales en un grupo de nodos descendientes potenciales más grande.

UPDATE: cuando se prueba si un nodo es un descendiente de un nodo en el grupo principal potencial, debe probarse contra TODOS los nodos principales potenciales.

Esto es lo que ocurrió:

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

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

A continuación, reserve una matriz de bits para cada tamaño de prefijo posible y agregue los nodos principales para ser probados, es decir, si C se agrega al grupo potencial de nodos principales, haga lo siguiente:

  1    2    3  <- Prefix length

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

Cuando pruebe si un nodo es un descendiente de un nodo padre potencial, tome su prefijo trie, busque el primer carácter en el primer "conjunto de prefijos" (ver arriba) y si está presente, busque el segundo carácter de prefijo en el segundo " matriz de prefijos "y así sucesivamente, es decir, probar F conduce a:

 F = 1    2    1

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

so sí F, es descendiente de C.

Esta prueba parece ser el peor caso 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 forma obvia de subir el árbol y comparar 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 dos peores escenarios. Sin embargo, la sobrecarga de memoria es una preocupación.

¿Hay otra forma de hacerlo? Cualquier puntero muy apreciado!