#binary-tree #graph-theory
#двоичное дерево #теория графов
Вопрос:
Вот проблема и мое предпринятое решение. 
Мое решение: 1. Запустите топологическую сортировку дерева, которая выполняется за линейное время BigTheta (E V), где E — количество ребер, а V — количество вершин. Это помещает его в связанный список, который также занимает постоянное время. 2. Вершина u будет предком, если у нее более высокое время завершения, чем у вершины v. 3. Посмотрите на 2 вершины в связанном списке и сравните их время завершения и верните true или false в зависимости от результата шага 2.
Правильно ли это звучит или я что-то упускаю?
Комментарии:
1. почему вы спрашиваете, работает ли ваше решение? вы говорите нам.
2. StackOverflow — это не сайт «сделай мою работу за меня»; для этого вам следует поискать где-нибудь вроде Rentacoder . Если вам нужна помощь здесь, вы должны опубликовать приложенные вами усилия и объяснить, почему это сработало не так, как вы ожидали, и кто-нибудь, вероятно, сможет вам помочь. Если вы не пишете код для решения этой проблемы, ваш вопрос не по теме; если да, опубликуйте написанный вами код и сообщите нам, что работает неправильно. Спасибо. 🙂
3. Вопрос задает только псевдокод, мне не нужно ничего писать, просто объясните, как это будет работать. Это работает для меня, но я чувствую, что мне не хватает чего-то маленького, для чего stackoverflow всегда хорош
Ответ №1:
Я не думаю, что ваше понимание того, что означает «постоянное время», является вполне правильным. «… time BigTheta(E V) где E — количество ребер, а V — количество вершин» — это линейное время, а не постоянное время.
Конечно, вам разрешено использовать линейное время для предварительной обработки, так что все в порядке, но как вы собираетесь выполнить свой шаг 3 («Посмотрите на 2 вершины в связанном списке») за постоянное время?
Комментарии:
1. Он может сделать это нормально, потому что он все равно сравнивает позиции (и позиции могут быть сохранены в вершинах. Это печально, это не имеет значения, потому что алгоритм в любом случае неверен (он может давать ложные срабатывания)
2. упс, мозговой пердеж я знаю разницу между линейным и постоянным временем. Ах, я обновлю свой вопрос, чтобы включить, как я буду ссылаться на вершины на шаге 2, чтобы выполнить это за постоянное время
Ответ №2:
Вот подход, который будет работать для любого дерева (не только двоичного). Этап предварительной обработки заключается в выполнении обхода дерева Эйлера (это просто обход DFS) и создании списка на основе этого обхода. Когда вы посещаете узел в первый раз, вы добавляете его в список, и когда вы посещаете его в последний раз, вы добавляете его в список.
Пример:
x
/
y z
Список будет выглядеть следующим образом: [b(x), b(y), e(y), b(z), e(z), e(x)] . Здесь b(x) означает enter x и e(x) означает leave x . Теперь, когда у вас есть этот список, вы можете ответить на запрос is x an ancestor of y , выполнив тест b(x) is before b(y) and e(y) is before e(x) в списке.
Вопрос в том, как вы можете сделать это за постоянное время?
Для статических деревьев (что и в вашем случае) вы можете использовать таблицу поиска (она же массив) для хранения b/e , теперь тест занимает постоянное время. Итак, это решает вашу проблему.