Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
2 Дек '11 4:03
показан
2255 раз
обновлен
2 Дек '11 12:38
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Небольшое гугление показывает, что этим интересовался Tarjan (R.E. Tarjan. Applications of path compression on balanced trees 1979) и в 84 году он научился делать это за O(1) (D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. 1984). А вообще у меня сложилось подозрение, что алгоритм поиска LCA есть в Искусстве программирования Кнута -- поищи.