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