» Поиск пути в двоичном (бинарном) дереве

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

Gregory Бинарный поиск

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

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

Gregory
Хм. Так мысль. В двоичном дереве всегда существует путь между двумя вершинами через корень...
Немного развив эту мысль - если выбросить все совпадающие элементы путей от вершины - получишь наикратчайший путь между вершинами.
ShIvADeSt
Рекурсия не гарантирует требуемое время достижения вершины.

Проблемма в том, что если идти от корня, это не гарантирует, что уложимся во время, пропорциональное расстоянию между вершинами. Допустим, если они соседи, но находятся на очень большой глубине

Gregory
Постановка задачи кривовата имхо. В первом посте написано время соизмеримое с расстоянием, теперь вы говорите пропорциональное... И какой должен быть коэффициент этой пропорции?
Кстати, не вижу нигде в постановке задачи слова "кратчайший". Почему бы не через вершину?

FuzzyLogic
Извиняюсь за кривую формулировку. Перевожу с иврита
Имеется в виду именно кратчайший.
Время (количество операций) равно О(d(U,V))
когда d(U,V) - это расстояние (кратчайшее) между ними.
то есть, существуют C=const так, что T<=C*d(U,V)
T - время. Другими словами - коэффициент пропорции - константа.

PS Алгоритм был найден Если кого-то интересует, опишу

напиши, если не сложно лично я кроме как через корень не придумал

Знач так.
Скажем, что расстояние между вершинами равно n=2^m.
Каждую итерацию начиная с обоих вершин поднимаемся вверх на 2^k шагов, когда k - это номер итерации. скажем, из вершины u поднялись на u1, а из v - на v1.
Повторяем до тех пор, пока из одной из вершин, до которых поднялись не получится за то же количество шагов добраться до второй.
Чтобы это проверить, по очереди из u1 и v1 поднимаемся 2^k шагов, и если встречаем вторую, закончили.
Другими словами, сравниваем разность между уровнями начальных вершин с 1,2,4,8,...
Таким способом находим разность уровней двух начальных вершин и узнаем, кто из них ниже.
Можно показать, что алгоритм завершится когда хотя бы один из итераторов пройдет общего родителя, то есть в худшем случае через k=log(n) итераций

Идем из нижнего количество шагов, равное числу вершин. Затем продвигаем каждую из вершин на один шаг, пока они не встретятся. Так находим общего родителя и длину пути.
Получается, что в худшем случае совершаем
3*(1+2+4+8+...+2^m)+n=3*(1+2*(2^m-1))+n=3*(1+4*n-2)+n=13n-3=O(n)
операций.
Да, оказалось, что найти путь подразумевало найти его длину. Если бы надо было найти возможность спуститься от родителя к одной из вершин, вряд ли бы что вышло.