Imagine a seguinte árvore:

    A
   / \
  B   C
 / \   \
D   E   F

Estou procurando uma maneira de consultar se, por exemplo, F é descendente de A (nota: F não precisa ser um direct descendente de F), o que, nesse caso em particular, seria verdadeiro. Apenas uma quantidade limitada de nós principais em potencial precisa ser testada em relação a um pool de nós em potencial descendentes maiore

UPDATE: ao testar se um nó é descendente de um nó no pool pai em potencial, ele precisa ser testado em TODOS os nós pai em potencia

Isto é o que surgiu:

Converta a árvore de múltiplas vias para uma árvore, ou seja, atribua os seguintes prefixos a todos os nós da árvore acima:

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

Em seguida, reserve uma matriz de bits para cada tamanho de prefixo possível e adicione os nós pai a serem testados, ou seja, se C for adicionado ao pool de nós pai em potencial, faça:

  1    2    3  <- Prefix length

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

Ao testar se um nó é descendente de um nó pai em potencial, use seu prefixo trie, procure o primeiro caractere na primeira "matriz de prefixos" (veja acima) e, se estiver presente, procure o segundo caractere de prefixo no segundo " matriz de prefixos "e assim por diante, ou seja, testar F leva a:

 F = 1    2    1

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

so sim F, é um descendente de C.

Este teste parece ser o pior caso O (n), em que n = comprimento máximo do prefixo = profundidade máxima da árvore, portanto o pior caso é exatamente igual à maneira óbvia de apenas subir na árvore e comparar nós. No entanto, isso terá um desempenho muito melhor se o nó testado estiver próximo à parte inferior da árvore e o nó pai em potencial estiver em algum lugar no topo. A combinação dos dois algoritmos reduziria os dois piores cenários. No entanto, a sobrecarga de memória é uma preocupaçã

Existe outra maneira de fazer isso? Qualquer ponteiro muito apreciado!