Редактирование: Rope

{{Определение
|definition=
Rope - структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
}}

Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.

==Merge==
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
Пример результата конкатенации двух строк:

[[file:String_concat.png|800px|Результат конкатенации двух строк.]]

'''Псевдокод:'''
<pre>
merge(T1, T2):
    Node node
    node.left = T1
    node.right = T2
    return node
</pre>

Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.

==Получение символа по индексу==

Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос - получить символ с индексом <tex>i</tex>, то будем спускаться по дереву из корня следующим образом:

* Текущая вершина - не лист, тогда возможно два варианта:
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
* Текущая вершина - лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.

'''Псевдокод:'''
<pre>
get(i, node):
    if (!isNil(node):
        if (node.left >= i):
            return get(i, node.left)
        else:
            return get(i - node.left.w, node.right)
    else:
        return node.s[i]
</pre>

Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.

==Split==

Чтобы разбить строку на две по некоторому индексу <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):
    Node t1, t2
    t1.w = i
    t2.w = node.w - i
    Pair res
    if (!isNil(node)):
        if (node.left >= i):
            res = split(node.left, i)
            t1 = res.first
            t2.left = res.second
            t2.right = node.right
        else:
            res = split(node.right, i - node.left.w)     
            t1.left = node.left
            t1.right = res.first
            t2 = res.second
    else:
        t1.s = node.s.substr(0, i)
        t2.s = node.s.substr(i, s.len)
    return pair(t1, t2)
</pre>

Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.

==Операции удаления и вставки==

Нетрудно понять, что имея операция <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> - высота дерева.