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