Rope

Определение:

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

Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.

Merge

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

Псевдокод:

merge(T1, T2):
    Node node
    node.left = T1
    node.right = T2
    return node

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

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

Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос - получить символ с индексом [math]i[/math], то будем спускаться по дереву из корня следующим образом:

• Текущая вершина - не лист, тогда возможно два варианта:
  • Вес левого поддерева больше либо равен [math]i[/math], тогда идем в левое поддерево.
  • Иначе идем в правое поддерево и ищем там [math]i - w[/math] символ, где [math]w[/math] вес левого поддерева.
• Текущая вершина - лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.

Псевдокод:

get(i, node):
    if (!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]

Асимптотика выполнения одного такого запроса очевидно [math]O(h)[/math], где [math]h[/math] - высота дерева.

Split

Чтобы разбить строку на две по некоторому индексу [math]i[/math] необходимо спускаясь по дереву(аналогично операции [math]get[/math]), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

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

Тогда результатом выполнения операции [math]split[/math] по индексу 16 будет:

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции [math]split[/math] будет:

Псевдокод:

split(node, i):
    Node t1, t2
    t1.w = i
    t2.w = node.w - i
    Pair res
    if (!isNil(node)):
        if (node.left >= 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)

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

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

Нетрудно понять, что имея операция [math]merge[/math] и [math]split[/math], можно легко через них выразить операции [math]delete[/math] и [math]insert[/math] по аналогии с другими деревьями поиска.

Операция [math]delete[/math] удаляет из строки подстроку начиная с индекса [math]beginIndex[/math] и заканчивая(не включая) индексом [math]endIndex[/math].

Псевдокод:

delete(node, beginIndex, endIndex):
    Node t1, t2, t3
    (t1, t2) = split(node, beginIndex)
    t3 = split(t2, endIndex).second
    return merge(t1, t3)

Операция [math]insert[/math] вставляет данную строку [math]s[/math] в исходную начиная с позиции [math]insertIndex[/math].

Псевдокод:

insert(node, insertIndex, s):
    Node t1, t2
    (t1, t2) = split(node, insertIndex)
    Node t3 = node(s)
    t1 = merge(t1, t3)
    return merge(t1, t2)

Так как данные операции используют только [math]split[/math] и [math]merge[/math] то асимптотика времени их работы [math]O(h)[/math], где [math]h[/math] - высота дерева.

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

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

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

Оптимизации

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

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

Литература

• Википедия - Rope
• Ropes — быстрые строки
• Ropes: an Alternative to Strings