3622
правки
Изменения
Rope
,Нет описания правки
'''Rope''' (Веревкарус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Заведем [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины {{---}} сама строка.
