Очень эффективно выбирать, но слишком медленно обновлять

тавьте себе следующее дерево:

    A
   / \
  B   C
 / \   \
D   E   F

Я ищу способ запроса, если, например, F является потомком A (примечание: F не должен бытьнепосредственный потомок F), что в данном конкретном случае будет правдой. Только ограниченное количество потенциальных родительских узлов должно быть протестировано с большим пулом потенциальных потомков.

ОБНОВЛЕНИЕ: при проверке того, является ли узел потомком узла в потенциальном родительском пуле, его необходимо проверить на ВСЕ потенциальные родительские узлы.

Вот что придумали:

Преобразовать многоканальное дерево в три, то есть назначить следующие префиксы каждому узлу в вышеприведенном дереве:

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

Затем зарезервируйте битовый массив для каждого возможного размера префикса и добавьте родительские узлы для проверки, то есть, если C добавлен в пул потенциальных родительских узлов, выполните:

  1    2    3  <- Prefix length

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

При проверке, является ли узел потомком потенциального родительского узла, возьмите его префикс trie, ищите первый символ в первом «массиве префиксов» (см. Выше) и, если он присутствует, ищите второй символ префикса во втором «префиксе». массив "и т. д., т. е. проверка F приводит к:

 F = 1    2    1

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

так что да, F, является потомком C.

Этот тест выглядит как наихудший случай O (n), где n = максимальная длина префикса = максимальная глубина дерева, поэтому его наихудший случай точно равен очевидному способу подняться вверх по дереву и сравнить узлы. Тем не менее, это работает намного лучше, если тестируемый узел находится в нижней части дерева, а потенциальный родительский узел находится где-то наверху. Объединение обоих алгоритмов уменьшит оба худших сценария. Однако нехватка памяти вызывает беспокойство.

Есть ли другой способ сделать это? Любые указатели очень ценятся!

Ответы на вопрос(1)

Ваш ответ на вопрос