91
правка
Изменения
Rope
,Нет описания правки
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Иногда, при использовании строк нам нужны следующие свойства:
*Операции которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.
*Также эти операции должны так же эффективно работать и с длинными строками. Не должно быть прямой зависимости от длинны строк.
*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо.
В данном случае Rope удовлетворяет всем этим свойствам.
Заведем [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка.
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины его предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
==См. также==
