91
правка
Изменения
Rope
,Нет описания правки
Так как данные операции используют только <tex>split</tex> и <tex>merge</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
==Балансировка==
Для того чтобы дерево не превращалось в бамбук:
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда так как высота АВЛ-дерева <tex>h = \log{n}</tex> то асимптотика операций <tex> get, split, delete, insert</tex> будет равна <tex>O(\log{n})</tex>
==Оптимизации==
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
* Кэширование. Так как зачастую нужна последовательный доступ к индексам(например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.
==Литература==
