Очень эффективно выбирать, но слишком медленно обновлять
тавьте себе следующее дерево:
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 = максимальная длина префикса = максимальная глубина дерева, поэтому его наихудший случай точно равен очевидному способу подняться вверх по дереву и сравнить узлы. Тем не менее, это работает намного лучше, если тестируемый узел находится в нижней части дерева, а потенциальный родительский узел находится где-то наверху. Объединение обоих алгоритмов уменьшит оба худших сценария. Однако нехватка памяти вызывает беспокойство.
Есть ли другой способ сделать это? Любые указатели очень ценятся!