Реализовать неизменяемый deque как сбалансированное двоичное дерево?

Ответ 1

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

• Обратить спины

  Для выполнения операций deque в традиционном сбалансированном дереве поиска нам нужен доступ к концам, но у нас есть только доступ к центру. Чтобы добраться до левого края, мы должны перемещаться по указателям слева, пока мы не достигнем тупика. Было бы предпочтительнее иметь указатель на левый и правый концы без всяких усилий по навигации. На самом деле, нам действительно не нужен доступ к корню node очень часто. Пусть хранится сбалансированное дерево поиска, так что доступ к концам 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;
  };
  

  Если вы храните как левый, так и правый, а также центральный элемент, у вас есть немедленный доступ к обоим концам. Вставка и удаление могут по-прежнему быть & Omega; (lg n), потому что операции по балансировке могут потребовать прохождения всего левого или правого позвоночника, но просто просмотр слева и справа элементов теперь равен O (1).

  Пример этой стратегии используется для создания чисто функциональных treaps с реализациями в SML и Java (дополнительная документация). Это также ключевая идея в нескольких других непреложных требованиях с производительностью o (lg n).

• Связано с работой по рабаланизму

  Как отмечалось выше, вставка на левом или правом конце дерева AVL может потребовать время & Omega; (lg n) для прохождения позвоночника. Вот пример дерева AVL, который демонстрирует это:

  Полное двоичное дерево определяется индукцией как:

  • Полное двоичное дерево с высотой 0 является пустой node.
  • Полное двоичное дерево с высотой n + 1 имеет корень node с полными бинарными деревьями с высотой n в качестве дочерних элементов.

  Нажатие элемента слева от полного двоичного дерева обязательно увеличит максимальную высоту дерева. Поскольку деревья AVL выше хранят эту информацию в каждом node, и поскольку каждое дерево вдоль левого позвоночника полного бинарного дерева также является полным двоичным деревом, то нажатие элемента слева от AVL-детекса, которое оказывается полным бинарное дерево потребует увеличения и Omega; (lg n) значения высоты вдоль левого отдела позвоночника.

  (Две заметки об этом: (a) Вы можете хранить деревья AVL, не сохраняя высоту в node, вместо этого вы сохраняете только информацию о балансе (слева-выше, справа или выше). измените производительность приведенного выше примера. (b) В деревьях AVL вам может потребоваться не только обновление информации о балансе или высоте, но и o Omega; (lg n), но & omega; (lg n). Я не помню, детали этого, и это может быть только при удалении, а не вставках.)

  Чтобы добиться выполнения операций deque (lg n), нам нужно ограничить эту работу. Неизменяемые знаки, представленные сбалансированными деревьями, обычно используют по крайней мере одну из следующих стратегий:

  • Предвидеть, когда потребуется перебалансировка, Если вы используете дерево, для которого требуется o (lg n) перебалансировка, но вы знаете, где будет нуждаться эта перебалансировка, и вы можете получить ее достаточно быстро, вы можете выполнять операции deque в o (lg n). Deques, которые используют это как стратегию, будут хранить не только два указателя в deque (концы левого и правого шипов, как обсуждалось выше), но некоторое небольшое количество указателей перехода к местам выше по шипам. Затем операции Deque могут получить доступ к корням деревьев, на которые указывают указатели перехода в O (1) раз. Если o (lg n) указатели перехода поддерживаются для всех мест, где потребуется перебалансировка (или изменение информации node), операции deque могут занимать время o (lg n).

    (Конечно, это делает дерево фактически даг, так как деревья на шипах, на которые указывают указатели прыжка, также указывают их дети на позвоночник. Непрерывные структуры данных обычно не сочетаются с недревесными графики, так как замена node, на которую указывает более чем один другой node, требует замены всех остальных узлов, которые указывают на него. Я видел это исправление, просто устраняя указатели без прыжка, превращая dag обратно в Дерево. Затем можно сохранить односвязный список с указателями переходов в виде списка списков. Каждый подчиненный список содержит все узлы между заголовком этого списка и указателем перехода. Это требует некоторой осторожности, чтобы иметь дело с частично перекрывающимися указателями перехода, и полное объяснение, вероятно, не подходит для этого в стороне.)

    Это один из трюков, используемых Цакалидис в своей статье "Деревья AVL для локализованного поиска" , чтобы разрешить операции Oque (1) AVL деревья с расслабленным состоянием равновесия. Это также основная идея, используемая Каплан и Тарьян в своей статье "Чисто функциональные, в режиме реального времени" с привязкой и позднее уточнение этого Михаэсау и Тарьяна. Munro et al. "Детерминированные списки пропусков" также заслуживают упоминания здесь, хотя перевод списков пропусков в неизменяемый параметр с помощью деревьев иногда изменяет свойства, позволяющие такую ​​эффективную модификацию вблизи концов. Примеры переводов см. В Messeguer "Пропустить деревья, альтернативную структуру данных для пропуска списка в параллельном подходе" , Дин и Джонс "Изучение двойственности между списками пропуска и деревьями двоичного поиска" и Lamoureux and Nickerson "On Эквивалентность B-деревьев и детерминированные списки пропусков" .

  • Выполняйте большую работу. В приведенном выше примере полного двоичного дерева не требуется перебалансировка на узлах push, но & Omega; (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 вызывает себя & Omega; (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 et al. "Строго-регулярная система номеров и структуры данных" не является плохим местом для начала чтения этой темы. Также может быть полезно Hinze "Bootstrapping one-sided flexible arrays" .

    В "Создание структур данных стойким" , Driscoll et al. описывают ленивое перекрашивание, которое они приписывают Цакалидису. Они применяют его к красно-черным деревьям, которые можно перебалансировать после вставки или удаления с помощью O (1) вращений (но & Omega; (lg n) перекрашивания) (см. Тарьян "Обновление сбалансированного дерева в поворотах O (1)" ). Ядро идеи состоит в том, чтобы отметить большой путь узлов, которые необходимо перекрасить, но не повернуть. Аналогичная идея используется для деревьев AVL в более старых версиях Браун и Тарьян "Быстрый алгоритм слияния" . (В более новых версиях одной и той же работы используются 2-3 дерева, я не читал более новые, и я не знаю, используют ли они какие-либо методы, такие как ленивое перекрашивание.)

  • Randomize. Treaps, упомянутые выше, могут быть реализованы в функциональной настройке, чтобы они выполняли операции deque в течение O (1) в среднем. Поскольку в deques нет необходимости проверять свои элементы, это среднее значение не подвержено вредной работе, ухудшающей производительность, в отличие от простых (без перебалансировки) двоичных деревьев поиска, которые бывают быстрыми на среднем входе. Treaps использует независимый источник случайных бит вместо того, чтобы полагаться на случайность из данных.

    В постоянных настройках treaps могут быть подвержены ухудшенной производительности от вредоносного ввода с противником, который может (a) использовать старые версии структуры данных и (b) измерять производительность операций. Поскольку у них нет никаких гарантий наихудшего баланса, treaps могут стать довольно неуравновешенными, хотя это должно происходить редко. Если противник ждет операцию deque, которая занимает много времени, она может повторно инициировать эту же операцию несколько раз, чтобы измерить и использовать возможное несбалансированное дерево.

    Если это не проблема, treaps - это привлекательно простая структура данных. Они очень близки к описанному выше дереву позвоночника AVL.

    Пропущенные списки, упомянутые выше, также могут быть применимы к функциональным реализациям с O (1) усредненными операциями deque.

    Первые два метода для ограничения работы по перебалансировке требуют сложных модификаций структур данных, хотя обычно они дают простой анализ сложности операций deque. Рандомизация наряду со следующей методикой имеет более простые структуры данных, но более сложный анализ. Исходный анализ Seidel и Aragon не является тривиальным, и существует некоторый комплексный анализ точных вероятностей с использованием более продвинутой математики, чем присутствует в цитированных работах выше - см. Flajolet et al. "Шаблоны в случайных двоичных деревьях поиска" .

  • амортизировать. Существует несколько сбалансированных деревьев, которые при просмотре с корней (как описано в разделе "Обратные спины" выше) предлагают O (1) амортизированное время вставки и удаления. Отдельные операции могут занимать время & Omega; (lg n), но они ставят дерево в таком хорошем состоянии, что большое количество операций, следующих за дорогостоящей операцией, будет дешевым.

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

    Один из способов получить амортизированные оценки в постоянной настройке был изобретен Chris Okasaki. Не просто объяснить, как амортизация выдержала способность использовать произвольные старые версии структуры данных, но если я правильно помню, Окасаки сначала (насколько я знаете) документ по теме имеет довольно четкое объяснение. Более подробные объяснения см. В его тезис или Каплан, Окасаки и Тарьян, озаглавленный "Простые сдерживающие списки кастингов" .

    Рассмотрим снова противника сверху, который пытается многократно заставлять вычислять дорогостоящую операцию. После первой силы ленивого значения каждая оставшаяся сила дешева.

    В своей книге Окасаки объясняет, как строить отношения с O (1) амортизированным временем, необходимым для каждой операции. Это, по сути, B + -tree, который является деревом, где все элементы хранятся у листьев, узлы могут варьироваться в зависимости от того, сколько у них детей, и каждый лист находится на одной глубине. Окасаки использует метод разворота позвоночника, рассмотренный выше, и он приостанавливает (то есть сохраняет как ленивое значение) шипы над листовыми элементами.

    Структура Хинце и Патерсон назвали "деревья пальцев: простая структура данных общего назначения" на полпути между требованиями, разработанными Окасаки и "Чисто функциональные представления отсканированных отсортированных списков" Каплана и Тарьяна. Структура Хинце и Патерсона стала очень популярной.

    В качестве доказательства того, насколько сложно оценить амортизированный анализ, пальцы пальца Hinze и Paterson реализовано без лени, делая временные ограничения не O (1), но все же O (lg n), Одна из реализаций, которая, кажется, использует лень, - это реализацию ленивых значений в С#, которые могут помочь объяснить их, если мое объяснение выше отсутствует.

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

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

• Почти все упомянутые выше требования относятся к деревьям поиска пальцев. В функциональной настройке это означает, что они могут быть разбиты на i-й элемент в O (lg (min (i, ni))), а два дерева размером n и m могут быть объединены в O (lg (min (n, m) )).

• Я знаю два способа реализации требований, которые не используют деревья. Окасаки представляет одну в своей книге и тезисе и документ, который я связал выше. Другой использует технику под названием "глобальная перестройка" и представлен в Chuang and Goldberg "В режиме реального времени, многозадачные машины Тьюринга и чисто функциональное программирование" .

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Вы можете создать простой неизменяемый deque с амортизированными операциями постоянного времени для всех основных операций с использованием двух стеков, левого и правого стека. PushLeft и PushRight соответствуют нажатиям значений в левом и правом стеках соответственно. Вы можете получить 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)

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