2014 dxdy logo

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

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




 
 Поиск путей максимальной длины в бинарных деревьях
Сообщение18.02.2011, 23:05 
Аватара пользователя
Вот возник вопрос. Как можно оптимальным образом найти путь максимальной длины в бинарном дереве. Пытался решить эту задачу так: искал максимальный путь, проходящий через корень дерева, а потом по доказанной мной теореме получалось, что корень пути максимальной длины дерева будет одной из вершин, принадлежащих тому максимальному пути, проходящему через корень дерева. Есть ли более лучший вариант решения этой задачи, и правильны ли мои рассуждения? Подскажите

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

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group