Наиболее эффективный алгоритм проверки того, находится ли лист c в том же поддереве, что и листья a и b
В настоящее время я работаю над программой, одним из шагов которой является проверка того, находится ли лист c в том же поддереве, что и два других листа a и b, в двоичном дереве T. Мой текущий подход заключается в следующем: сначала найдите LCA каждой пары листьев в T, и сохранить его в словаре. Затем для каждого узла в дереве найдите все листья, которые являются его потомками, и сохраните его также в словаре. Затем, когда мне нужно определить, находится ли c в том же поддереве, что и a и b, я нахожу LCA a и b и проверяю, является ли c его потомком.
Мне нужно будет выполнить этот шаг для многих различных пар a и b и сделать это на бинарных деревьях, которые имеют до 600 листов, так есть ли более быстрый алгоритм или, возможно, тот, который использует меньше памяти, который выполняет эту же задачу? Благодарю.
1 ответ
Здесь вам может помочь следующее полезное наблюдение: наименьшее поддерево, содержащее листья a и b, является поддеревом с корнем в LCA (a, b). Это означает, что вы можете проверить, находится ли c в поддереве, проверив, является ли c потомком LCA (a, b). Один из способов сделать это заключается в следующем: вычислить LCA (LCA (a, b), c). Если c находится в этом поддереве, то LCA (LCA (a, b), c) = LCA (a, b). В противном случае это будет какой-то другой узел. Это дает хороший алгоритм:
Вернуть, будет ли LCA (LCA (a, b), c) = LCA (a, b).
Это также может помочь в использовании быстрой структуры данных LCA. Вы упомянули предварительный расчет LCA всех пар узлов в дереве, но есть более быстрые варианты. В частности, есть несколько хороших алгоритмов, которые при O(n) времени предварительной обработки могут возвращать LCA двух узлов в дереве за время O(1) каждый. Если вы знаете пары заранее, проверьте алгоритм LCA в автономном режиме Тарьяна; если вы этого не сделаете, посмотрите на структуру данных Fischer-Heun LCA.
Надеюсь это поможет!