Изменения

Перейти к: навигация, поиск

Алгоритм Фараха

11 байт убрано, 16:31, 21 мая 2014
Шаг 4: слияние четного и нечетного дерева
Если начать эту процедуру для корней нечетного и четного деревьев, далее она рекурсивно выполняется для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования с любым ребром этих деревьев фиксированно, то общее время слияния деревьев составит <tex>O(N)</tex>.
[[Файл:Tree101232merged-pre.png|450px|thumb|Слитое дерево (условно)]]
 [[Файл:Tree101232merged-next.png|450px|thumb|Слитое дерево (в упрощённом виде)]]
В результате описанных действий получится дерево <tex>M_x</tex>,в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево <tex>M_x</tex> без изменений).
497
правок

Навигация