1632
правки
Изменения
Rope
,rollbackEdits.php mass rollback
'''Rope''' (рус. ''веревка'') {{Определение|definition=Rope - --}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.}}
==Получение символа по индексу==
* Текущая вершина {{- --}} не лист, тогда возможно два варианта:
** Вес левого поддерева больше либо равен <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> по индексу <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 tree1, tree2 '''if''' node.left <tex>\ne \varnothing</tex> '''if''' node.left.w >= i res = split(node.left, i) tree1 = res.first tree2.left = res.second tree2.right = node.right tree2.w = tree2.left.w + tree2.right.w '''else''' res = split(node.right, i - node.left.w) tree1.left = node.left tree1.right = res.first tree1.w = tree1.left.w + tree1.right.w tree2 = res.second '''else''' tree1.s = node.s.substr(0, i) tree2.s = node.s.substr(i, node.s.len) tree1.w = i tree2.w = node.s.len - i '''return''' <tex> \langle </tex>tree1, tree2<tex> \rangle </tex> ===Время работы=== Нетрудно заметить, что асимптотическая сложность выполнения данной операции {{---}} <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): (tree1, tree2) = split(node, beginIndex) tree3 = split(tree2, endIndex - beginIndex).second '''return''' merge(tree1, tree3) Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную, начиная с позиции <tex>insertIndex</tex>. ===Псевдокод=== Node insert(Node node, '''int''' insertIndex, '''string''' s): (tree1, tree3) = split(node, insertIndex) tree2 = Node(s) '''return''' merge(merge(tree1, tree2), tree3) ===Время работы=== Так как данные операции используют только <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>\mathrm{get}</tex>, и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</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]