497
правок
Изменения
→Шаг 2: построение чётного дерева
Корректируются все развилки дерева (так как они могут совпадать в первых символах):
Lля всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие их любой вершины, лексикографически отсортированы по своим первым двум символам(так как мы сортировали пары номера пар на прошлом шаге). Для каждого ребра нам достоточно проверить, что его первыей символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может быть, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок теперь. Ну тогда удалим <tex>u</tex>.
Эта процедура требует требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.
[[Файл:Tree101232even.png|300px|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
