Изменения

Перейти к: навигация, поиск

Rope

2172 байта добавлено, 01:07, 10 февраля 2018
м
Отсыпал запятых, пофиксил немного орфографии
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Заведем Иногда при использовании строк нам нужны следующие свойства:*Операции, которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длины строк.*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо. В данном случае Rope удовлетворяет всем этим свойствам. ==Описание структуры==Для хранения Rope создадим структуру, похожую на [[Дерево поиска, наивная реализацияДекартово дерево по неявному ключу|двоичное декартово дерево поискапо неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строкасамой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.
==Merge==
Когда приходит запрос на конкатенацию с другой строкой , мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
Пример результата конкатенации двух строк:
===Псевдокод===
Node merge(Node T1n1, Node T2n2): '''return ''' Node(T1n1, T2n2, T1n1.w + T2n2.w)
===Время работы===
Асимптотика выполнения операции конкатенации двух строк , очевидно , <tex>\mathrm{O(1)}</tex>.
==Получение символа по индексу==
Для того что реализовать операцию получения символа Чтобы получить символ по некоторому индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос {{---}} получить символ с индексом <tex>i</tex>, то будем спускаться по дереву из корня , используя веса, записанные в вершинах, чтобы определить, в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:
* Текущая вершина {{---}} не лист, тогда возможно два варианта:
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ, ; необходимо взять символ с соответствующим номером у строки , которая там хранится.
===Псевдокод===
'''char''' get('''int''' i,Node node): '''if''' ('''not''' isNil(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>\mathrm{O(h)}</tex>, где <tex>h</tex> {{---}} высота дерева.
==Split==
Чтобы разбить строку на две по некоторому индексу <tex>\mathrm{i}</tex> , необходимо , спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно одной из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
Пускай дано дерево:
[[file:Split1.png|800px|Перед операцией split.]]
Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу <tex> 16 </tex> будет:
[[file:Split2.png|800px|Результат выполнения операции split.]]
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавитсяизбавиться, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
[[file:Split3.png|800px|Результат выполнения операции split.]]
===Псевдокод===
'''Pair'''<Node, Node> split(Node node, '''int''' i): Node t1tree1, t2 t1.w = i t2.w = node.w - i '''Pair''' restree2 '''if''' ('''not''' isNil(node)):.left <tex>\ne \varnothing</tex> '''if''' (node.left.w >= i):
res = split(node.left, i)
t1 tree1 = res.first t2tree2.left = res.second t2tree2.right = node.right tree2.w = tree2.left.w + tree2.right.w '''else''':
res = split(node.right, i - node.left.w)
t1tree1.left = node.left t1tree1.right = res.first t2 tree1.w = tree1.left.w + tree1.right.w tree2 = res.second '''else''': t1tree1.s = node.s.substr(0, i) t2tree2.s = node.s.substr(i, node.s.len) tree1.w = i tree2.w = node.s.len - i '''return''' pair(t1<tex> \langle </tex>tree1, t2)tree2<tex> \rangle </tex>
===Время работы===
Нетрудно заметить , что асимптотическая сложность выполнения данной операции {{---}} <tex>\mathrm{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 (t1tree1, t2tree2) = split(node, beginIndex) t3 tree3 = split(t2tree2, endIndex- beginIndex).second '''return''' merge(t1tree1, t3tree3)
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную , начиная с позиции <tex>insertIndex</tex>.
===Псевдокод===
Node insert(Node node, '''int''' insertIndex, '''string''' s):
Node t1, t2 (t1tree1, t2tree3) = split(node, insertIndex) tree2 = Node t3 = node(s) t1 = merge(t1, t3) '''return''' merge(t1merge(tree1, tree2), t2tree3)
===Время работы===
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> , то асимптотика времени их работы {{---}} <tex>\mathrm{O(h)}</tex>, где <tex>h</tex> {{--- }} высота дерева.
==Балансировка==
Для того , чтобы дерево не превращалось в бамбук:
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева <tex>h = \log{n}</tex>, то асимптотика операций <tex> \mathrm{get, split, delete, insert, merge}</tex> будет равна <tex>\mathrm{O(\log{n})}</tex>, где <tex>n</tex> {{---}} количество сконкатенированных строк.
==Оптимизации==
* Для уменьшения объема памяти , занимаемой деревом , и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом. * Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист (а также его границы), в который мы пришли после очередного запроса <tex>\mathrm{get}</tex>, и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
* Кэширование==См. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.==
*[[АВЛ-дерево]]
*[[Splay-дерево]]
*[[Декартово дерево по неявному ключу]]
==Источники информации==
*[[wikipedia:en:Rope_(data_structure)|Википедия Wikipedia {{---}} 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-деревоКатегория:Дискретная математика и алгоритмы]]*[[Декартово дерево по неявному ключуКатегория:Деревья поиска]]
74
правки

Навигация