Изменения

Перейти к: навигация, поиск

Rope

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

Навигация