Rope — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Rope - структура данных для хранения строки, представляющая из себя дв...»)
 
Строка 5: Строка 5:
  
 
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
 
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
 +
 +
==Merge==
 
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
 
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
 +
 +
<pre>
 +
merge(T1, T2):
 +
    Node node
 +
    node.left = T1
 +
    node.right = T2
 +
    return node
 +
</pre>
 +
 +
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
  
 
==Получение символа по индексу==
 
==Получение символа по индексу==
Строка 26: Строка 38:
 
         return node.s[i]
 
         return node.s[i]
 
</pre>
 
</pre>
 +
 +
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
 +
 +
==Split==
 +
 +
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву(аналогично операции <tex>get</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
 +
 +
<pre>
 +
split(node, i):
 +
    Node t1, t2
 +
    t1.w = i
 +
    t2.w = node.w - i
 +
    Pair res
 +
    if (!isNil(node)):
 +
        if (node.left >= i):
 +
            res = split(node.left, i)
 +
            t1.left = res.first
 +
            t2.left = res.second
 +
            t2.right = node.right
 +
        else:
 +
            res = split(node.right, i - node.left.w)   
 +
            t1.left = node.left
 +
            t1.right = res.first
 +
            t2.left = res.second
 +
    else:
 +
        t1.s = node.s.substr(0, i)
 +
        t2.s = node.s.substr(i, s.len)
 +
    return pair(t1, t2)
 +
</pre>
 +
 +
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
 +
 +
==Операции удаления и вставки==

Версия 18:52, 3 июня 2014

Определение:
Rope - структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.


Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.

Merge

Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.

merge(T1, T2):
    Node node
    node.left = T1
    node.right = T2
    return node

Асимптотика выполнения операции конкатенации двух строк очевидно [math]O(1)[/math].

Получение символа по индексу

Для того что реализовать операцию получения символа по индексу будем в вершинах дерева хранить суммарную длину всех строк в его поддереве, или, если это лист, длину строки которая в нем хранится. Тогда, если нам пришел запрос - получить символ с индексом [math]i[/math], то будем спускаться по дереву из корня следующим образом:

  • Текущая вершина - не лист, тогда возможно два варианта:
    • Вес левого поддерева больше либо равен [math]i[/math], тогда идем в левое поддерево.
    • Иначе идем в правое поддерево и ищем там [math]i - w[/math] символ, где [math]w[/math] вес левого поддерева.
  • Текущая вершина - лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
get(i, node):
    if (!isNil(node):
        if (node.left >= i):
            return get(i, node.left)
        else:
            return get(i - node.left.w, node.right)
    else:
        return node.s[i]

Асимптотика выполнения одного такого запроса очевидно [math]O(h)[/math], где [math]h[/math] - высота дерева.

Split

Чтобы разбить строку на две по некоторому индексу [math]i[/math] необходимо спускаясь по дереву(аналогично операции [math]get[/math]), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

split(node, i):
    Node t1, t2
    t1.w = i
    t2.w = node.w - i
    Pair res
    if (!isNil(node)):
        if (node.left >= i):
            res = split(node.left, i)
            t1.left = res.first
            t2.left = res.second
            t2.right = node.right
        else:
            res = split(node.right, i - node.left.w)     
            t1.left = node.left
            t1.right = res.first
            t2.left = res.second
    else:
        t1.s = node.s.substr(0, i)
        t2.s = node.s.substr(i, s.len)
    return pair(t1, t2)

Нетрудно заметить что асимптотическая сложность выполнения данной операции [math]O(h)[/math], где [math]h[/math] - высота дерева.

Операции удаления и вставки