Rope

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

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

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

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

Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос - получить символ с индексом [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]