Редактирование: Rope

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
 
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
  
Иногда при использовании строк нам нужны следующие свойства:
+
Иногда, при использовании строк нам нужны следующие свойства:
*Операции, которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.
+
*Операции которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.
*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длины строк.
+
*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длинны строк.
 
*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо.
 
*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо.
  
Строка 9: Строка 9:
  
 
==Описание структуры==
 
==Описание структуры==
Для хранения Rope создадим структуру, похожую на [[Декартово дерево по неявному ключу|декартово дерево по неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} самой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.
+
Для хранения Rope создадим структуру, похожую на [[Декартово дерево по неявному ключу|декартово дерево по неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа необязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} не одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.
  
 
==Merge==
 
==Merge==
Когда приходит запрос на конкатенацию с другой строкой, мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
+
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
 
Пример результата конкатенации двух строк:
 
Пример результата конкатенации двух строк:
  
Строка 23: Строка 23:
 
===Время работы===
 
===Время работы===
  
Асимптотика выполнения операции конкатенации двух строк, очевидно, <tex>O(1)</tex>.
+
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
  
 
==Получение символа по индексу==
 
==Получение символа по индексу==
  
Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса, записанные в вершинах, чтобы определить, в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:
+
Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса записанные вершинах чтобы определить в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:
  
 
* Текущая вершина {{---}} не лист, тогда возможно два варианта:
 
* Текущая вершина {{---}} не лист, тогда возможно два варианта:
 
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
 
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
 
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
 
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ; необходимо взять символ с соответствующим номером у строки, которая там хранится.
+
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 46: Строка 46:
 
===Время работы===
 
===Время работы===
  
Асимптотика выполнения одного такого запроса, очевидно, <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Split==
 
==Split==
  
Чтобы разбить строку на две по некоторому индексу <tex>i</tex>, необходимо, спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одной из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
+
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
  
 
Пускай дано дерево:
 
Пускай дано дерево:
Строка 60: Строка 60:
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
  
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавиться, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
+
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
  
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
Строка 89: Строка 89:
 
===Время работы===
 
===Время работы===
  
Нетрудно заметить, что асимптотическая сложность выполнения данной операции {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Операции удаления и вставки==
 
==Операции удаления и вставки==
  
Нетрудно понять, что имея операции <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.
+
Нетрудно понять, что имея операция <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.
  
Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку, начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
+
Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 103: Строка 103:
 
     '''return''' merge(tree1, tree3)
 
     '''return''' merge(tree1, tree3)
  
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную, начиная с позиции <tex>insertIndex</tex>.
+
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 113: Строка 113:
 
===Время работы===
 
===Время работы===
  
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex>, то асимптотика времени их работы {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Балансировка==
 
==Балансировка==
  
Для того, чтобы дерево не превращалось в бамбук:
+
Для того чтобы дерево не превращалось в бамбук:
  
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
Строка 125: Строка 125:
 
==Оптимизации==
 
==Оптимизации==
  
* Для уменьшения объема памяти, занимаемой деревом, и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
+
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
  
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист (а также его границы), в который мы пришли после очередного запроса <tex>\mathrm{get}</tex>, и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
+
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>\mathrm{get}</tex> и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины его предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: