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