Реализовать неизменяемую деку как сбалансированное бинарное дерево?

Question

Реализовать неизменяемую деку как сбалансированное бинарное дерево?

Некоторое время я думал о том, как реализовать deque (то есть двустороннюю очередь) как неизменную структуру данных.

Кажется, есть разные способы сделать это. AFAIK, неизменяемые структуры данных, как правило, являются иерархическими, так что основные их части можно использовать повторно после изменения таких операций, как вставка или удаление элемента.

Эрик Липперт имеет две статьи в своем блоге на эту тему, а также примеры реализации на C#.

Обе его реализации кажутся мне более сложными, чем на самом деле необходимо. Разве запросы не могут быть просто реализованы как двоичные деревья, где элементы могут быть вставлены или удалены только в самом "левом" (переднем) и в самом "правом" (заднем) дереве?

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

Кроме того, дерево будет сбалансировано с помощью поворотов:

правое вращение при вставке спереди или при удалении сзади, и
левые повороты при удалении спереди или вставке сзади.

Эрик Липперт, на мой взгляд, очень умный человек, которого я глубоко уважаю, но он явно не рассматривал этот подход. Таким образом, я задаюсь вопросом, это было по уважительной причине? Является ли мой предложенный способ реализации deques наивным?

30

data-structures functional-programming immutability deque

Источник

user240733 17 июл '10 в 11:17

4 ответа

Решение

Все остальные ответы потрясающие. Я добавлю к ним, что я выбрал реализацию дерева пальца для deque, потому что он необычно и интересно использует систему родовых типов. Большинство структур данных являются рекурсивными по своей структуре, но этот метод помещает рекурсию также в систему типов, которую я раньше не видел; Я думал, что это может быть общего интереса.

5

Источник

user88656 18 июл '10 в 15:38

Если вы используете сбалансированное двоичное дерево, вставки и удаления на обоих концах равны O(lg N) (как в среднем, так и в худшем случае). Подход, использованный в реализациях Эрика Липперта, более эффективен и выполняется в среднем за постоянное время (наихудший случай все еще равен O(lg N)).

Помните, что изменение неизменяемого дерева включает в себя переписывание всех родителей изменяемого вами узла. Поэтому для deque вы не хотите, чтобы дерево было сбалансировано; вместо этого вы хотите, чтобы узлы L и R были как можно ближе к корню, тогда как узлы в середине дерева могут быть дальше.

5

Источник

user141502 17 июл '10 в 12:27

Разве запросы не могут быть просто реализованы как двоичные деревья, где элементы могут быть вставлены или удалены только в самом "левом" (переднем) и в самом "правом" (заднем) дереве?

Абсолютно. Модифицированную версию сбалансированного по высоте дерева, в частности деревьев AVL, было бы очень легко реализовать. Однако это означает заполнение основанной на дереве очереди n элементы требует O(n lg n) время - вы должны стрелять по деку, который имеет такие же характеристики производительности, что и изменяемый аналог.

Вы можете создать прямую неизменяемую деку с амортизированными операциями с постоянным временем для всех основных операций, используя два стека, левый и правый стеки. PushLeft и PushRight соответствуют push-значениям в левом и правом стеке соответственно. Вы можете получить Deque.Hd и Deque.Tl из LeftStack.Hd и LeftStack.Tl; если ваш LeftStack пуст, установите LeftStack = RightStack.Reverse и RightStack = пустой стек.

type 'a deque = Node of 'a list * 'a list    // '

let peekFront = function
    | Node([], []) -> failwith "Empty queue"
    | Node(x::xs, ys) -> x
    | Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
    | Node([], []) -> failwith "Empty queue"
    | Node(xs, y::ys) -> y
    | Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
    | Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
    | Node(xs, ys) -> Node(xs, v::ys)
let tl = function
    | Node([], []) -> failwith "Empty queue"
    | Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
    | Node(x::xs, ys) -> Node(xs, ys)

Это очень распространенная реализация, и ее очень легко оптимизировать для повышения производительности.

2

Источник

user40516 18 июл '10 в 22:33

Другие вопросы по тегам data-structures functional-programming immutability deque

user388716 18 июл '10 в 04:48 2010-07-18 04:48 · Accepted Answer · 2010-07-18 04:48

Как отметил Даниэль, реализация неизменяемых запросов с хорошо известными сбалансированными деревьями поиска, такими как AVL или красно-черные деревья, дает Θ(lg n) сложности в худшем случае. На первый взгляд некоторые из реализаций, которые обсуждает Липперт, могут показаться сложными, но есть много неизменяемых запросов с o(lg n) наихудшей, средней или амортизированной сложностью, которые строятся из сбалансированных деревьев вместе с двумя простыми идеями:

Обратный шипы
Для выполнения операций deque в традиционном сбалансированном дереве поиска нам нужен доступ к концам, но у нас есть доступ только к центру. Чтобы добраться до левого конца, мы должны перемещаться по указателям левого ребенка, пока мы, наконец, не достигнем тупика. Было бы предпочтительно иметь указатель на левый и правый концы без всех этих усилий навигации. На самом деле, нам действительно не нужен доступ к корневому узлу очень часто. Давайте сохраним сбалансированное дерево поиска так, чтобы доступ к концам был O(1).
Вот пример на C того, как вы обычно можете хранить дерево AVL:
```
struct AVLTree {
  const char * value;
  int height;
  struct AVLTree * leftChild;
  struct AVLTree * rightChild;
};
```
Чтобы настроить дерево так, чтобы мы могли начинать с краев и двигаться к корню, мы меняем дерево и сохраняем все указатели вдоль путей от корня до левого и самого правого дочерних элементов в обратном порядке. (Эти пути называются левый и правый позвоночник соответственно). Точно так же, как переворачивание односвязного списка, последний элемент становится первым, так что самый левый дочерний элемент теперь легко доступен.
Это немного сложно понять. Чтобы объяснить это, представьте, что вы сделали это только для левого отдела позвоночника:
```
struct LeftSpine {
  const char * value;
  int height;
  struct AVLTree * rightChild;
  struct LeftSpine * parent;
};
```
В каком-то смысле самый левый потомок теперь является "корнем" дерева. Если бы вы нарисовали дерево таким образом, это выглядело бы очень странно, но если вы просто возьмете свой обычный рисунок дерева и перевернете все стрелки на левом отделе позвоночника, смысл структуры LeftSpine должен стать более понятным. Доступ к левой стороне дерева теперь мгновенный. То же самое можно сделать для правильного позвоночника:
```
struct RightSpine {
  double value;
  int height;
  struct AVLTree * leftChild;
  struct RightSpine * parent;
};
```
Если вы храните как левый и правый отдел позвоночника, так и центральный элемент, вы сразу получаете доступ к обоим концам. Вставка и удаление могут по-прежнему иметь значение Ω(lg n), поскольку для операций перебалансировки может потребоваться пересечь весь левый или правый отдел позвоночника, но просто просмотр левого и правого элементов теперь равен O(1).
Пример этой стратегии используется для создания чисто функциональных трэпов с реализациями на SML и Java ( дополнительная документация). Это также ключевая идея в нескольких других неизменяемых запросах с производительностью o(lg n).
Сковать работу равновесия
Как отмечено выше, для вставки в левый или правый конец дерева AVL может потребоваться время (lg n) для прохождения позвоночника. Вот пример дерева AVL, которое демонстрирует это:
Полное двоичное дерево определяется индукцией как:
- Полное двоичное дерево высотой 0 является пустым узлом.
- Полное двоичное дерево высотой n+1 имеет корневой узел с полными двоичными деревьями высотой n в качестве дочерних.
Выдвижение элемента слева от полного двоичного дерева обязательно увеличит максимальную высоту дерева. Поскольку вышеупомянутые деревья AVL хранят эту информацию в каждом узле, и поскольку каждое дерево вдоль левого корешка полного двоичного дерева также является полным двоичным деревом, элемент, помещаемый слева от декы AVL, который оказывается полным двоичным деревом потребует увеличения значений высоты Ω (lg n) вдоль левого отдела позвоночника.
(Два замечания по этому поводу: (a) Вы можете хранить деревья AVL, не сохраняя высоту в узле; вместо этого вы сохраняете только информацию о балансе (слева выше, справа выше или даже). Это не меняет производительность Приведенный выше пример. (b) В деревьях AVL может потребоваться не только обновление информации о балансе или высоте Ω(lg n), но и операции перебалансировки Ω (lg n). Я не помню подробности этого, и это может быть только на удалениях, а не на вставках.)
Чтобы выполнить o(lg n) deque операций, нам нужно ограничить эту работу. Неизменяемые требования, представленные сбалансированными деревьями, обычно используют по крайней мере одну из следующих стратегий:
- Предвидеть, где потребуется перебалансировка. Если вы используете дерево, которое требует o(lg n) перебалансировки, но вы знаете, где потребуется это перебалансирование, и вы можете добраться до него достаточно быстро, вы можете выполнить свои операции deque за o(lg n) время. Deques, которые используют это как стратегию, сохранит не только два указателя в deque (концы левого и правого шипов, как обсуждалось выше), но и небольшое количество указателей прыжка в более высокие места вдоль шипов. Операции Deque могут затем получить доступ к корням деревьев, на которые указывают указатели перехода в O (1) времени. Если o(lg n) указатели перехода поддерживаются для всех мест, где потребуется перебалансировка (или изменение информации об узле), операции удаления могут занять время o(lg n).
  (Конечно, это делает дерево на самом деле дагом, так как на деревьях в шипах, на которые указывают указатели прыжков, их дочерние элементы также указывают на позвоночник. Неизменяемые структуры данных обычно не ладят с графиками, не относящимися к дереву, поскольку замена узла, на который указывает более одного узла, требует замены всех других узлов, которые на него указывают. Я видел это исправленным, просто удалив указатели без перехода, превратив даг обратно в дерево. Затем можно сохранить односвязный список с указателями перехода в виде списка списков. Каждый подчиненный список содержит все узлы между заголовком этого списка и его указателем перехода. Это требует некоторой осторожности, чтобы иметь дело с частично перекрывающимися указателями перехода, и полное объяснение, вероятно, не подходит для этого в стороне.)
  Это один из приемов, использованных Цакалидисом в его статье "Деревья AVL для локализованного поиска", чтобы разрешить операции O(1) deque на деревьях AVL с ослабленным условием равновесия. Это также основная идея, использованная Капланом и Тарьяном в их работе "Чисто функциональные запросы в реальном времени с сцеплением" и последующее уточнение этой работы Михесау и Тарьяном. Здесь также заслуживают упоминания "Детерминированные списки пропусков" Манро и соавторов, хотя перевод списков пропусков в неизменяемый параметр с помощью деревьев иногда изменяет свойства, которые допускают такую эффективную модификацию вблизи концов. Примеры перевода см. В статье Мессегера "Пропускать деревья, альтернативную структуру данных для пропуска списков при параллельном подходе", Дина и Джоунса "Изучение двойственности между пропускающими списками и деревьями двоичного поиска", а также в "Об эквивалентности Ламуро и Никерсона" B-деревья и детерминированные списки пропусков ".
- Делай работу навалом. В приведенном выше примере с полным бинарным деревом перебалансировка не требуется для толчка, но узлам Ω (lg n) необходимо обновить информацию о своей высоте или балансе. Вместо того, чтобы фактически делать приращение, вы могли бы просто отметить позвоночник на концах как нуждающийся в приращении.
  Один из способов понять этот процесс - по аналогии с двоичными числами. (2^n)-1 представлен в двоичном виде строкой из n 1. При добавлении 1 к этому номеру вам нужно изменить все 1 на 0, а затем добавить 1 в конце. Следующий Haskell кодирует двоичные числа как непустые строки битов, сначала наименее значимые.
```
data Bit = Zero | One

type Binary = (Bit,[Bit])

incr :: Binary -> Binary
incr (Zero,x) = (One,x)
incr (One,[]) = (Zero,[One])
incr (One,(x:xs)) = 
    let (y,ys) = incr (x,xs)
    in (Zero,y:ys)
```
  incr - рекурсивная функция, а для чисел вида (One,replicate k One), incr называет себя Ω(k) раз.
  Вместо этого мы могли бы представлять группы равных битов только количеством битов в группе. Соседние биты или группы битов объединяются в одну группу, если они равны (по значению, а не по числу). Мы можем увеличить время O (1):
```
data Bits = Zeros Int | Ones Int

type SegmentedBinary = (Bits,[Bits])

segIncr :: SegmentedBinary -> SegmentedBinary
segIncr (Zeros 1,[]) = (Ones 1,[])
segIncr (Zeros 1,(Ones n:rest)) = (Ones (n+1),rest)
segIncr (Zeros n,rest) = (Ones 1,Zeros (n-1):rest)
segIncr (Ones n,[]) = (Zeros n,[Ones 1])
segIncr (Ones n,(Zeros 1:Ones m:rest)) = (Zeros n,Ones (m+1):rest)
segIncr (Ones n,(Zeros p:rest)) = (Zeros n,Ones 1:Zeros (p-1):rest)
```
  Поскольку segIncr не является рекурсивным и не вызывает никаких функций, кроме плюса и минуса для Ints, вы можете видеть, что это занимает O (1) времени.
  Некоторые из требований, упомянутых в вышеприведенном разделе, озаглавленном "Предвидеть, где потребуется перебалансировка", на самом деле используют другую численно вдохновленную технику, называемую "избыточные системы счисления", чтобы ограничить работу перебалансировки O (1) и быстро ее найти. Избыточные числовые представления увлекательны, но, возможно, слишком далеки от этого обсуждения. Elmasry и др. "Строго регулярная система счисления и структуры данных" - неплохое место для начала чтения по этой теме. "Самозагрузка односторонних гибких массивов" Хинзе также может быть полезна.
  В статье "Создание постоянных структур данных" Driscoll et al. описать ленивое перекрашивание, которое они приписывают Цакалидису. Они применяют его к красно-черным деревьям, которые могут быть перебалансированы после вставки или удаления с помощью поворотов O (1) (но с перекрашиванием Ω (lg n)) (см . "Обновление сбалансированного дерева в поворота O (1)" Тарьяна ". Суть идеи заключается в маркировке большого пути узлов, которые необходимо перекрасить, но не повернуть. Аналогичная идея используется на деревьях AVL в более старых версиях алгоритма быстрого слияния Брауна и Тарьяна. (Более новые версии той же работы используют 2-3 дерева; я не читал более новые, и я не знаю, используют ли они какие-либо методы, такие как ленивая перекраска.)
- Перемешать Treaps, упомянутые выше, могут быть реализованы в функциональной настройке так, чтобы они выполняли операции deque в среднем за O (1) времени. Поскольку запросам не нужно проверять свои элементы, это среднее значение не подвержено снижению производительности злонамеренного ввода, в отличие от простых (без перебалансировки) деревьев двоичного поиска, которые в среднем работают быстро. Треапы используют независимый источник случайных битов вместо того, чтобы полагаться на случайность данных.
  В постоянных настройках уязвимости могут быть подвержены снижению производительности из-за злонамеренного ввода со стороны злоумышленника, который может (а) использовать старые версии структуры данных и (б) измерить производительность операций. Поскольку у них нет никаких гарантий баланса в худшем случае, трепы могут стать совершенно несбалансированными, хотя это случается редко. Если злоумышленник ожидает операции блокировки, которая занимает много времени, он может многократно инициировать эту же операцию, чтобы измерить и использовать, возможно, несбалансированное дерево.
  Если это не проблема, трепы - это привлекательная простая структура данных. Они очень близки к описанному выше дереву позвоночника AVL.
  Упущенные списки, упомянутые выше, также могут быть применимы к функциональным реализациям с O (1) операциями deque среднего времени.
  Первые два метода ограничения работ по перебалансировке требуют сложных модификаций в структурах данных, обычно обеспечивая простой анализ сложности операций deque. Рандомизация, наряду со следующим методом, имеет более простые структуры данных, но более сложный анализ. Первоначальный анализ Зейделя и Арагона не является тривиальным, и существует некоторый сложный анализ точных вероятностей с использованием более продвинутой математики, чем тот, что представлен в цитированных выше работах - см. Flajolet et al. "Паттерны в случайных бинарных деревьях поиска".
- Амортизация Есть несколько сбалансированных деревьев, которые, если смотреть из корней вверх (как объяснено в "Перевернуть шипы" выше), предлагают O (1) амортизированное время вставки и удаления. Отдельные операции могут занимать Ω (lg n) времени, но они приводят дерево в такое приятное состояние, что большое количество операций после дорогой операции будет дешевым.
  К сожалению, этот вид анализа не работает, когда старые версии дерева все еще существуют. Пользователь может выполнять операции со старым, почти несбалансированным деревом много раз, не вмешиваясь в дешевые операции.
  Крис Окасаки изобрел один из способов получения амортизированных границ в постоянной обстановке. Не просто объяснить, как амортизация переживает способность использовать произвольные старые версии структуры данных, но если я правильно помню, первая (насколько мне известно) статья Окасаки по этому вопросу имеет довольно четкое объяснение. Более подробные объяснения см. В его диссертации или его книге.
  Насколько я понимаю, есть два основных ингредиента. Во-первых, вместо того, чтобы просто гарантировать, что определенное количество дешевых операций происходит перед каждой дорогой операцией (обычный подход к амортизации), вы фактически назначаете и настраиваете эту конкретную дорогую операцию перед выполнением дешевых операций, которые за нее будут платить. В некоторых случаях операцию планируется начать (и завершить) только после множества дешевых шагов. В других случаях операция запланирована только на O (1) шагов в будущем, но дешевые операции могут сделать часть дорогостоящей операции, а затем перепланировать ее на более позднее время. Если злоумышленник, желающий повторять дорогостоящую операцию снова и снова, фактически каждый раз использует одну и ту же запланированную операцию. Это разделение, где приходит второй ингредиент.
  Вычисление настроено, используя лень. Ленивое значение вычисляется не сразу, но после выполнения его результат сохраняется. В первый раз, когда клиент должен проверить ленивое значение, его значение вычисляется. Более поздние клиенты могут использовать это кэшированное значение напрямую, без необходимости пересчитывать его.
```
#include <stdlib.h>

struct lazy {
  int (*oper)(const char *);
  char * arg;
  int* ans;
};

typedef struct lazy * lazyop;

lazyop suspend(int (*oper)(const char *), char * arg) {
  lazyop ans = (lazyop)malloc(sizeof(struct lazy));
  ans->oper = oper;
  ans->arg = arg;
  return ans;
}

void force(lazyop susp) {
  if (0 == susp) return;
  if (0 != susp->ans) return;
  susp->ans = (int*)malloc(sizeof(int));
  *susp->ans = susp->oper(susp->arg);
}

int get(lazyop susp) {
  force(susp);
  return *susp->ans;
}
```
  Конструкции лени включены в некоторые ML, и Haskell по умолчанию ленив. Под капотом лень - это мутация, которая заставляет некоторых авторов называть это "побочным эффектом". Это может считаться плохим, если подобный побочный эффект не очень хорошо сочетается с какими бы то ни было причинами выбора неизменной структуры данных, но, с другой стороны, если рассматривать лень как побочный эффект, это позволяет традиционные методы амортизированного анализа для постоянных структур данных, как упомянуто в статье Каплана, Окасаки и Тарьяна, озаглавленной "Простые надежно сохраняемые списки".
  Снова рассмотрим противника сверху, который пытается многократно форсировать вычисления дорогостоящей операции. После первой силы ленивого значения каждая оставшаяся сила дешева.
  В своей книге Окасаки объясняет, как строить дебеки с амортизированным временем O (1), необходимым для каждой операции. По сути, это дерево B+, представляющее собой дерево, в котором все элементы хранятся на листьях, узлы могут различаться по количеству дочерних элементов, и каждый лист находится на одной и той же глубине. Окасаки использует метод реверсирования позвоночника, рассмотренный выше, и он приостанавливает (то есть сохраняет в качестве ленивого значения) шипы над элементами листа.
  Структура Хинце и Патерсона под названием "Пальцевые деревья: простая структура данных общего назначения" находится на полпути между запросами, разработанными Окасаки, и "Чисто функциональными представлениями каталитических отсортированных списков" Каплана и Тарьяна. Структура Хинзе и Патерсона стала очень популярной.
  В качестве доказательства того, насколько хитрым является амортизированный анализ, деревья пальца Хинце и Патерсона часто реализуются без лени, делая временные границы не O (1), а все же O(lg n). Одна из реализаций, которая, кажется, использует лень, - это функциональная точка-сеть. Этот проект также включает в себя реализацию отложенных значений в C#, которые могут помочь объяснить их, если мое объяснение выше отсутствует.

Могут ли запросы быть реализованы в виде бинарных деревьев? Да, и их сложность в худшем случае при постоянном использовании будет не хуже, чем у Эрика Липперта. Однако деревья Эрика на самом деле не достаточно сложны для того, чтобы получить O (1) -деквестные операции в постоянном режиме, хотя только с небольшим запасом сложности (делая центр ленивым), если вы готовы принять амортизированную производительность. Другое, но также простое представление о ловушках может получить O (1) ожидаемую производительность в функциональном окружении, если принять противника, который не слишком хитр. Получение O (1) операций deque в худшем случае с древовидной структурой в функциональном окружении требует чуть большей сложности, чем реализации Эрика.

Два заключительных замечания (хотя это очень интересная тема, и я оставляю за собой право добавить больше позже):-)

Почти все упомянутые выше требования также являются деревьями поиска пальцев. В функциональной настройке это означает, что они могут быть разбиты по i-му элементу за O(lg(min(i,ni))), а два дерева размером n и m могут быть объединены в O(lg(min(n,m)).)) время.
Я знаю два способа реализации запросов, которые не используют деревья. Окасаки представляет один в своей книге, тезисе и статье, на которую я ссылался выше. Другая использует технику, называемую "глобальное восстановление", и представлена в книге Чуанга и Голдберга "Запросы в реальном времени, многоголовочные машины Тьюринга и чисто функциональное программирование".