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