Изменения
Rope
,Нет описания правки
'''Rope''' (Веревка) {{Определение|definition=Rope - --}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.}}
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
==Получение символа по индексу==
Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос {{- --}} получить символ с индексом <tex>i</tex>, то будем спускаться по дереву из корня следующим образом:
* Текущая вершина {{- --}} не лист, тогда возможно два варианта:
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
* Текущая вершина {{- --}} лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
'''Псевдокод:'''
</pre>
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> {{- --}} высота дерева.
==Split==
</pre>
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> {{- --}} высота дерева.
==Операции удаления и вставки==
