91
правка
Изменения
Rope
,Нет описания правки
'''Rope''' (Веревка) {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Заведем [[Дерево поиска, наивная реализация|двоичное сбалансированное дерево поиска]]. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
В вершинах дерева будем хранить строку, если это лист, а также вес {{---}} суммарную длину все строк в поддереве, или, если это лист, длину строки, которая в нем хранится.
[[file:String_concat.png|800px|Результат конкатенации двух строк.]]
===Псевдокод=== merge('''Псевдокод:Node'''<pre>merge(T1, '''Node''' T2) = '''Node'''(T1, T2, T1.w + T2.w)</pre>
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
===Псевдокод=== '''Псевдокод:char'''<pre>char get('''int''' i, '''Node''' node): '''if ''' (!'''not''' 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> {{---}} высота дерева.
[[file:Split3.png|800px|Результат выполнения операции split.]]
===Псевдокод=== ('''Псевдокод:Node'''<pre>(node, node'''Node''') split('''Node''' node, '''int''' i): '''Node ''' t1, t2 t1.w = i t2.w = node.w - i '''Pair ''' res '''if ''' (!'''not''' isNil(node)): '''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)</pre>
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
Операция <tex>delete</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
===Псевдокод=== '''Псевдокод:Node'''<pre>node delete('''Node''' node, '''int''' beginIndex, '''int''' 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>.
===Псевдокод=== '''Псевдокод:Node'''<pre>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)</pre>
Так как данные операции используют только <tex>split</tex> и <tex>merge</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева <tex>h = \log{n}</tex>, то асимптотика операций <tex> get, split, delete, insert, merge</tex> будет равна <tex>O(\log{n})</tex>, где tex>n</tex> - количество сконкатенированных строк.
==Оптимизации==
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.
==ЛитератураИсточники информации==
*[[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]
==См. также==
*[[АВЛ-дерево]]
*[[Splay-дерево]]
*[[Декартово дерево по неявному ключу]]
