91
правка
Изменения
Rope
,Нет описания правки
==Операции удаления и вставки==
Нетрудно понять, что имея операция <tex>merge</tex> и <tex>split</tex>, можно легко через них выразить операции <tex>delete</tex> и <tex>insert</tex> по аналогии с другими деревьями поиска.
Операция <tex>delete</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая(не включая) индексом <tex>endIndex</tex>.
<pre>
delete(node, beginIndex, endIndex):
Node t1, t2, t3
(t1, t2) = split(node, beginIndex)
t3 = split(t2, endIndex).second
return merge(t1, t3)
</pre>
Операция <tex>insert</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>
<pre>
insert(node, insertIndex, s):
Node t1, t2
(t1, t2) = split(node, insertIndex)
Node t3 = node(s)
t1 = merge(t1, t3)
return merge(t1, t2)
</pre>
Так как данные операции используют только <tex>split</tex> и <tex>merge</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
