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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Псевдокод)
Строка 57: Строка 57:
  
 
===Псевдокод===
 
===Псевдокод===
  Pair<Node, Node> split(Node node, '''int''' i):
+
  '''Pair'''<Node, Node> split(Node node, '''int''' i):
     Node t1, t2
+
     Node tree1, tree2
     t1.w = i
+
     tree1.w = i
     t2.w = node.w - i
+
     tree2.w = node.w - i
    '''Pair''' res
 
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
         '''if''' node.left.w >= i
 
         '''if''' node.left.w >= i
             res = split(node.left, i)
+
             '''Pair''' res = split(node.left, i)
             t1 = res.first
+
             tree1 = res.first
             t2.left = res.second
+
             tree2.left = res.second
             t2.right = node.right
+
             tree2.right = node.right
 
         '''else'''
 
         '''else'''
             res = split(node.right, i - node.left.w)     
+
             '''Pair''' res = split(node.right, i - node.left.w)     
             t1.left = node.left
+
             tree1.left = node.left
             t1.right = res.first
+
             tree1.right = res.first
             t2 = res.second
+
             tree2 = res.second
 
     '''else'''
 
     '''else'''
         t1.s = node.s.substr(0, i)
+
         tree1.s = node.s.substr(0, i)
         t2.s = node.s.substr(i, s.len)
+
         tree2.s = node.s.substr(i, s.len)
     '''return''' pair(t1, t2)
+
     '''return''' '''Pair'''(tree1, tree2)
  
 
===Время работы===
 
===Время работы===

Версия 13:24, 6 июня 2014

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

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

Merge

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

Результат конкатенации двух строк.

Псевдокод

Node merge(Node n1, Node n2):
    return Node(n1, n2, n1.w + n2.w)

Время работы

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

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

Чтобы получить символ по некоторому индексу [math]i[/math], будем спускаться по дереву из корня, используя веса записанные вершинах чтобы определить в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:

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

Псевдокод

char get(int i,Node node):
    if node.left [math]\ne \varnothing[/math]
        if node.left.w >= 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]\mathrm{get}[/math]), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

Пускай дано дерево:

Перед операцией split.

Тогда результатом выполнения операции [math]\mathrm{split}[/math] по индексу 16 будет:

Результат выполнения операции split.

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции [math]\mathrm{split}[/math] будет:

Результат выполнения операции split.

Псевдокод

Pair<Node, Node> split(Node node, int i):
    Node tree1, tree2
    tree1.w = i
    tree2.w = node.w - i
    if node.left [math]\ne \varnothing[/math]
        if node.left.w >= i
            Pair res = split(node.left, i)
            tree1 = res.first
            tree2.left = res.second
            tree2.right = node.right
        else
            Pair res = split(node.right, i - node.left.w)     
            tree1.left = node.left
            tree1.right = res.first
            tree2 = res.second
    else
        tree1.s = node.s.substr(0, i)
        tree2.s = node.s.substr(i, s.len)
    return Pair(tree1, tree2)

Время работы

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

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

Нетрудно понять, что имея операция [math]\mathrm{merge}[/math] и [math]\mathrm{split}[/math], можно легко через них выразить операции [math]\mathrm{delete}[/math] и [math]\mathrm{insert}[/math] по аналогии с другими деревьями поиска.

Операция [math]\mathrm{delete}[/math] удаляет из строки подстроку начиная с индекса [math]beginIndex[/math] и заканчивая (не включая) индексом [math]endIndex[/math].

Псевдокод

Node delete(Node node, int beginIndex, int endIndex):
    Node t1, t2, t3
    (t1, t2) = split(node, beginIndex)
    t3 = split(t2, endIndex - beginIndex).second
    return merge(t1, t3)

Операция [math]\mathrm{insert}[/math] вставляет данную строку [math]s[/math] в исходную начиная с позиции [math]insertIndex[/math].

Псевдокод

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)

Время работы

Так как данные операции используют только [math]\mathrm{split}[/math] и [math]\mathrm{merge}[/math] то асимптотика времени их работы [math]O(h)[/math], где [math]h[/math] - высота дерева.

Балансировка

Для того чтобы дерево не превращалось в бамбук:

Пример вырождения дерева в бамбук.

Предлагается хранить его как АВЛ-дерево и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева [math]h = \log{n}[/math], то асимптотика операций [math] \mathrm{get, split, delete, insert, merge}[/math] будет равна [math]O(\log{n})[/math], где [math]n[/math] — количество сконкатенированных строк.

Оптимизации

  • Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
  • Кэширование. Так как зачастую нужен последовательный доступ к индексам (например [math]i[/math] и [math]i + 1[/math]), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса [math]get[/math] и на следующем запросе сначала искать в сохраненном листе.

См. также

Источники информации