Изменения

Иногда, при использовании строк нам нужны следующие свойства:*Операции , которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длинны длины строк.

Для хранения Rope создадим структуру, похожую на [[Декартово дерево по неявному ключу|декартово дерево по неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строкасамой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа необязательно не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} не ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.

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

Асимптотика выполнения операции конкатенации двух строк , очевидно , <tex>O(1)</tex>.

Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса , записанные в вершинах , чтобы определить , в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:

* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ, ; необходимо взять символ с соответствующим номером у строки , которая там хранится.

Асимптотика выполнения одного такого запроса , очевидно , <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

Чтобы разбить строку на две по некоторому индексу <tex>i</tex> , необходимо , спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно одной из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавитсяизбавиться, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</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>.

Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную , начиная с позиции <tex>insertIndex</tex>.

Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> , то асимптотика времени их работы {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

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

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

* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, (а также его границы), в который мы пришли после очередного запроса <tex>\mathrm{get}</tex> , и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины его ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.