91
правка
Изменения
Rope
,Нет описания правки
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
В вершинах дерева будем хранить строку, если это лист, а также вес {{---}} суммарную длину все строк в поддереве, или, если это лист, длину строки, которая в нем хранится.
==Merge==
'''Псевдокод:'''
<pre>
char get(i, node):
if (!isNil(node):
if (node.left >= i):
==Split==
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву(аналогично операции <tex>get</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
Пускай дано дерево:
'''Псевдокод:'''
<pre>
(node, node) split(node, i):
Node t1, t2
t1.w = i
Нетрудно понять, что имея операция <tex>merge</tex> и <tex>split</tex>, можно легко через них выразить операции <tex>delete</tex> и <tex>insert</tex> по аналогии с другими деревьями поиска.
Операция <tex>delete</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая(не включая) индексом <tex>endIndex</tex>.
'''Псевдокод:'''
<pre>
node delete(node, beginIndex, endIndex):
Node t1, t2, t3
(t1, t2) = split(node, beginIndex)
'''Псевдокод:'''
<pre>
node insert(node, insertIndex, s):
Node t1, t2
(t1, t2) = split(node, insertIndex)
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
* Кэширование. Так как зачастую нужен последовательный доступ к индексам(например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.
==Литература==
