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

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

Заведем [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка.

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

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

===Псевдокод===
 Node merge(Node T1, Node T2):
     return Node(T1, T2, T1.w + T2.w)

===Время работы===

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

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

Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса записанные вершинах чтобы определить в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:

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

===Псевдокод===
 '''char''' get('''int''' i,Node node):
     '''if''' node.left <tex>\ne \varnothing</tex>
         '''if''' node.left.w >= i
             '''return''' get(i, node.left)
         '''else'''
             '''return''' get(i - node.left.w, node.right)
     '''else'''
         '''return''' node.s[i]

===Время работы===

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

==Split==

Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

Пускай дано дерево:

[[file:Split1.png|800px|Перед операцией split.]]

Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу 16 будет: 

[[file:Split2.png|800px|Результат выполнения операции split.]]

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:

[[file:Split3.png|800px|Результат выполнения операции split.]]

===Псевдокод===
 Pair<Node, Node> split(Node node, '''int''' i):
     Node t1, t2
     t1.w = i
     t2.w = node.w - i
     '''Pair''' res
     '''if''' node.left <tex>\ne \varnothing</tex>
         '''if''' node.left.w >= 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)

===Время работы===

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

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

Нетрудно понять, что имея операция <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.

Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.

===Псевдокод===
 Node delete(Node node, '''int''' beginIndex, '''int''' endIndex):
     Node t1, t2, t3
     (t1, t2) = split(node, beginIndex)
     t3 = split(t2, endIndex - beginIndex).second
     '''return''' merge(t1, t3)

Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>.

===Псевдокод===
 Node insert(Node node, '''int''' insertIndex, '''string''' s):
     Node t1, t2
     (t1, t2) = split(node, insertIndex)
     Node t3 = Node(s)
     t1 = merge(t1, t3)
     '''return''' merge(t1, t2)

===Время работы===

Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.

==Балансировка==

Для того чтобы дерево не превращалось в бамбук:

[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]

Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева <tex>h = \log{n}</tex>, то асимптотика операций <tex> \mathrm{get, split, delete, insert, merge}</tex> будет равна <tex>O(\log{n})</tex>, где <tex>n</tex> {{---}} количество сконкатенированных строк.

==Оптимизации==

* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.

* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.

==См. также==

*[[АВЛ-дерево]]
*[[Splay-дерево]]
*[[Декартово дерево по неявному ключу]]
==Источники информации==

*[[wikipedia:en:Rope_(data_structure)|Википедия {{---}} Rope]]
*[http://habrahabr.ru/post/144736/ Ropes {{---}} быстрые строки]
*[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf Ropes: an Alternative to Strings]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]