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|Слитое дерево (условно)]]
