91
правка
Изменения
Rope
,Нет описания правки
==Merge==
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
Пример результата конкатенации двух строк:
[[file:String_concat.png|800px|Результат конкатенации двух строк.]]
'''Псевдокод:'''
<pre>
merge(T1, T2):
* Текущая вершина - лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
'''Псевдокод:'''
<pre>
get(i, node):
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву(аналогично операции <tex>get</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
Пускай дано дерево:
[[file:Split1.png|800px|Перед операцией split.]]
Тогда результатом выполнения операции <tex>split</tex> по индексу 16 будет:
[[file:Split2.png|800px|Результат выполнения операции split.]]
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>split</tex> будет:
[[file:Split3.png|800px|Результат выполнения операции split.]]
'''Псевдокод:'''
<pre>
split(node, i):
if (node.left >= i):
res = split(node.left, i)
t1.left = res.first
t2.left = res.second
t2.right = node.right
t1.left = node.left
t1.right = res.first
t2.left = res.second
else:
t1.s = node.s.substr(0, i)
Операция <tex>delete</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая(не включая) индексом <tex>endIndex</tex>.
'''Псевдокод:'''
<pre>
delete(node, beginIndex, endIndex):
Операция <tex>insert</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>
'''Псевдокод:'''
<pre>
insert(node, insertIndex, s):
