497
правок
Изменения
→Шаг 5: удаление двойных дуг
=== Шаг 5: удаление двойных дуг ===
Разбираемся с двойными дугами (на этом в примере их три). Для этого мы должны выяснить, сколько начальных символов таких у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя (это даст квадратичное время).
Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).
[[Файл:Tree101232merged.png|500px]]
'''откорректированное дерево'''
[[Файл:Treestep5_1.jpg|550px]]
'''пример'''
Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.
Дерево после обработки:
[[Файл:Treestep5_2.jpg|650px]]
'''итоговое дерево'''
Дерево строится рекурсивно, каждый раз длина строки уменьшается в два раза, а все фазы работают линейно.
