275
правок
Изменения
→Возможные исходы операции insert
== Возможные исходы операции insert ==
Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s_{s[i..j}]</tex> в дерево.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=70%
!style="background:#f2f2f2"|Случай
|-
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть подстрока <tex>s_{s[i..j-1}]</tex> кончается в листе. Добавим элемент <tex>s_js[j]</tex> в конец последнего ребра.
|style="background:#ffffff"|[[Файл:Case2.png]]
|-
|style="background:#ffffff"|''2. Создание листа''
|style="background:#ffffff"|Пусть подстрока <tex>s_{s[i..j-1}]</tex> кончается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_js[j]</tex>. Создадим новую дугу с началом в элементе <tex>s_{s[j-1}]</tex> и листом <tex>s_js[j]</tex>.
|style="background:#ffffff"|[[Файл:Case1.png]]
|-
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока <tex>s_{s[i..j-1}]</tex> кончается в вершине, из которой есть путь по <tex>s_js[j]</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:Case3.png]]
|}
