Изменения
Rope
,Нет описания правки
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
Заведем [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. В каждом листе будем хранить последовательную часть строкии ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка.В вершинах дерева будем хранить строку, если это лист, а также вес {{---}} суммарную длину всех строк в поддереве, или, если это лист, длину строки, которая в нем хранится.
==Merge==
===Псевдокод===
===Время работы===
===Псевдокод===
'''char''' get('''int''' i,'''Node''' node): '''if''' ('''not''' isNil(node)):
'''if''' (node.left >= i):
'''return''' get(i, node.left)
===Псевдокод===
t1.w = i
t2.w = node.w - i
===Псевдокод===
(t1, t2) = split(node, beginIndex)
t3 = split(t2, endIndex).second
===Псевдокод===
(t1, t2) = split(node, insertIndex)
t1 = merge(t1, t3)
'''return''' merge(t1, t2)
