Посещение бинарного дерева: переход от одного листа к другому

Question

Проблема: у меня есть двоичное дерево, все листья пронумерованы (слева направо, начиная с 0), и между ними нет связи.

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

Внутренние узлы дерева не содержат никакой полезной информации.

Я должен выбрать путь, основываясь только на индексах листьев. Путь начинается с листа и заканчивается на листе, и, конечно, я могу получить доступ к листу, если знаю его индекс (через массив указателей)

Дерево статическое, вставка или удаление узлов не допускаются.

Я разработал алгоритм, чтобы сделать это, но он действительно отстой ... любые идеи?

Answer 1

Один из вариантов - найти наименее общего предка двух узлов, а также последовательность узлов, которую вы должны взять от каждого узла, чтобы добраться до этого предка. Вот эскиз алгоритма:

1. Начиная с каждого узла, возвращайтесь к родительскому узлу, пока не дойдете до корня. Подсчитайте количество узлов на пути от каждого узла к корню. Пусть высота первого узла будет h ₁ , а высота второго узла будет h ₂ .

2. Пусть h = min (h ₁ , h ₂ ). Это высота более высокого из двух узлов.

3. Начиная с каждого узла, следуйте указателю родителя узла, пока оба узла не окажутся на высоте h. Запишите узлы, которые вы использовали на этом шаге. В этот момент оба узла находятся на одной высоте.

4. Пока вы не найдете общий узел, продолжайте идти вверх от каждого узла к его родителю. В конце концов вы поразите их общего предка. На этом этапе следуйте по пути от первого узла до этого предка, затем по пути от предка до второго узла.

В худшем случае это занимает O (h) время и O (h) пространство, где h - высота дерева. Для сбалансированного бинарного дерева это O (LG N) время и пространство, что довольно хорошо.

Если вы заинтересованы в гораздо более хардкорной версии этого алгоритма, рассмотрите алгоритм Least Common Ancestors Тарьяна , который с линейным временем предварительной обработки может быть использован для поиска наименее общего предка гораздо больше быстрее, чем это.

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

Answer 2

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

 Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)

, где lca - самый низкий общий предок.

см. это для получения дополнительной информации об этом алгоритме и посмотрите видео , чтобы узнать, как вычислить lca.