497
правок
Изменения
→Шаг 4: слияние четного и нечетного дерева
=== Шаг 4: слияние четного и нечетного дерева ===
Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>Т_sТ _s</tex>. Слияние будем производить начиная с корня.
Предположим, что для каждого узла деревьев <tex>Т_s^{odd}</tex> и <tex>Т_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они упорядочены в возрастающем лексикографическом порядке подстрок, которые представляют эти
ребра. Алгоритм слияния деревьев просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>Т_s^{odd}</tex> и <tex>Т_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:
