Самый эффективный алгоритм проверки, если лист c находится в том же поддереве, что и a и b

Question

В настоящее время я работаю над программой, одним из шагов которой является проверка того, что лист c находится в том же поддереве, что и два других листа a и b в двоичном дереве T. Мой текущий подход таков: сначала найдите LCA каждой пары листьев в T и сохраните ее в словаре. Затем для каждого узла в дереве найдите все листья, являющиеся потомками, и сохраните их в словаре. Затем, когда мне нужно определить, находится ли c в том же поддереве, что и a и b, я нахожу LCA a и b и проверяю, является ли c его потомком.

Мне нужно будет выполнить этот шаг для разных пар a и b и сделать это на двоичных деревьях, которые имеют до 600 листов, так что есть более быстрый алгоритм или, возможно, тот, который использует меньше памяти, что делает эта же задача? Благодарю.

Answer 1

одно полезное наблюдение, которое могло бы помочь вам здесь следующее: наименьшее поддерево, содержащий листья и б является поддерево с корнем в LCA (, б). Это означает, что вы можете проверить, является ли с в поддереве путем проверки с является потомком LCA (, б). Один из способов сделать это: вычислить LCA (LCA (a, b), c). Если с в этом поддереве, то ДМС (ДМС (, б), с) = LCA (, б). В противном случае это будет другой узел. Это дает хороший алгоритм:

Возврат ли = LCA (LCA (, б), с) LCA (, б).

Это может также помочь использовать быструю структуру данных LCA. Вы упомянули предварительную вычисление LCA всех пар узлов в дереве, но есть более быстрые опции. В частности, есть несколько хороших алгоритмов, которые с O (n) временем предварительной обработки могут возвращать LCA двух узлов в дереве во времени O (1) каждый. Если вы знаете пары заранее, проверьте Tarjan's offline LCA algorithm; если вы этого не сделаете, найдите Fischer-Heun LCA data structure.

Надеюсь, это поможет!