Rope — различия между версиями
Korektur (обсуждение | вклад) |
|||
| Строка 28: | Строка 28: | ||
===Псевдокод=== | ===Псевдокод=== | ||
'''char''' get('''int''' i,Node node): | '''char''' get('''int''' i,Node node): | ||
| − | '''if''' | + | '''if''' '''not''' isNil(node) |
| − | '''if''' | + | '''if''' node.left >= i |
'''return''' get(i, node.left) | '''return''' get(i, node.left) | ||
| − | '''else''' | + | '''else''' |
'''return''' get(i - node.left.w, node.right) | '''return''' get(i - node.left.w, node.right) | ||
| − | '''else''' | + | '''else''' |
'''return''' node.s[i] | '''return''' node.s[i] | ||
| Строка 62: | Строка 62: | ||
t2.w = node.w - i | t2.w = node.w - i | ||
'''Pair''' res | '''Pair''' res | ||
| − | '''if''' | + | '''if''' '''not''' isNil(node) |
| − | '''if''' | + | '''if''' node.left.w >= i |
res = split(node.left, i) | res = split(node.left, i) | ||
t1 = res.first | t1 = res.first | ||
t2.left = res.second | t2.left = res.second | ||
t2.right = node.right | t2.right = node.right | ||
| − | '''else''' | + | '''else''' |
res = split(node.right, i - node.left.w) | res = split(node.right, i - node.left.w) | ||
t1.left = node.left | t1.left = node.left | ||
t1.right = res.first | t1.right = res.first | ||
t2 = res.second | t2 = res.second | ||
| − | '''else''' | + | '''else''' |
t1.s = node.s.substr(0, i) | t1.s = node.s.substr(0, i) | ||
t2.s = node.s.substr(i, s.len) | t2.s = node.s.substr(i, s.len) | ||
Версия 23:04, 5 июня 2014
Rope (рус. веревка) — структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Заведем двоичное дерево поиска. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины — сама строка.
Содержание
Merge
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки. Пример результата конкатенации двух строк:
Псевдокод
Node merge(Node T1, Node T2):
return Node(T1, T2, T1.w + T2.w)
Время работы
Асимптотика выполнения операции конкатенации двух строк очевидно .
Получение символа по индексу
Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос — получить символ с индексом , то будем спускаться по дереву из корня следующим образом:
- Текущая вершина — не лист, тогда возможно два варианта:
- Вес левого поддерева больше либо равен , тогда идем в левое поддерево.
- Иначе идем в правое поддерево и ищем там символ, где вес левого поддерева.
- Текущая вершина — лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
Псевдокод
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]
Время работы
Асимптотика выполнения одного такого запроса очевидно , где — высота дерева.
Split
Чтобы разбить строку на две по некоторому индексу необходимо спускаясь по дереву (аналогично операции ), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
Пускай дано дерево:
Тогда результатом выполнения операции по индексу 16 будет:
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции будет:
Псевдокод
Pair<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)
Время работы
Нетрудно заметить что асимптотическая сложность выполнения данной операции , где — высота дерева.
Операции удаления и вставки
Нетрудно понять, что имея операция и , можно легко через них выразить операции и по аналогии с другими деревьями поиска.
Операция удаляет из строки подстроку начиная с индекса и заканчивая (не включая) индексом .
Псевдокод
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)
Операция вставляет данную строку в исходную начиная с позиции .
Псевдокод
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)
Время работы
Так как данные операции используют только и то асимптотика времени их работы , где - высота дерева.
Балансировка
Для того чтобы дерево не превращалось в бамбук:
Предлагается хранить его как АВЛ-дерево и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева , то асимптотика операций будет равна , где — количество сконкатенированных строк.
Оптимизации
- Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
- Кэширование. Так как зачастую нужен последовательный доступ к индексам (например и ), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса и на следующем запросе сначала искать в сохраненном листе.
