Изменения

== Шаг 5: удаление двойных дуг ==

Разбираемся с двойными дугами (на этом примере из три). Для этого мы должны выяснить сколько начальных символов таких дуг совпадает. Совпадать может от одного до нескольких символов, или даже все. Проверять их все по очереди нельзя (это даст квадратичное время).

Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки которые на концах снова развести по разным деревъям (для этого можно во время снияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).

Для примера как это сделать возмём строку 10010010101000:

Для того чтобы узнать общее начало двойной дуги, мы должны взять одну чётную и одну нечётную на дереве, для которых родителем является конец нашей двойной дуги. Например на рисунке выше двойная дуга (1), конец помечен зелёным - является общим родителем для вершин 3 и 6. Чтобы узнать на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на еденицу и найти их родителя, он будет находится на еденицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родителя вершин 4, 7 я пометил жёлтым, он находится на расстоянии 1 от корня, следовательно дуга (1) должна расслаиваться в двух символах от корня, т.е. обе дуги совпадают и их просто надо слить.

Дерево после обработки:

= Ссылки =