2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск путей максимальной длины в бинарных деревьях
Сообщение18.02.2011, 23:05 
Аватара пользователя


24/11/10
163
Браслав/Минск, Беларусь
Вот возник вопрос. Как можно оптимальным образом найти путь максимальной длины в бинарном дереве. Пытался решить эту задачу так: искал максимальный путь, проходящий через корень дерева, а потом по доказанной мной теореме получалось, что корень пути максимальной длины дерева будет одной из вершин, принадлежащих тому максимальному пути, проходящему через корень дерева. Есть ли более лучший вариант решения этой задачи, и правильны ли мои рассуждения? Подскажите

 Профиль  
                  
 
 Re: Бинарные деревья
Сообщение19.02.2011, 01:38 


02/07/08
322
Искать динамическим программированием по дереву: снизу вверх решать задачу для поддерева с корнем в данной вершине. Для этого легко заметить, что такой путь либо не проходит через корень - тогда он ищется среди детей, - либо проходит - тогда нужно знать две наиболее удалённые вершины. Это тоже легко поддерживать. Сложность, разумеется, получится $O(N)$, где $N$ - число вершин в графе.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group