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

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

1. Reverse the Spines

   Для выполнения двухсторонних операций в традиционном сбалансированном дереве поиска нам нужен доступ к концам, но у нас есть доступ только к центру. Чтобы добраться до левого края, мы должны перемещаться по указателям левых дочерних элементов, пока, наконец, не зайдем в тупик. Было бы предпочтительнее иметь указатель на левый и правый концы без всех этих усилий с навигацией. На самом деле, нам действительно не очень часто нужен доступ к корневому узлу. Давайте сохраним сбалансированное дерево поиска так, чтобы доступ к концам был O (1).

   Вот пример на языке C того, как вы обычно можете хранить дерево AVL:

    struct AVLTree {
   const char * value;
   int height;
   struct AVLTree * leftChild;
   struct AVLTree * rightChild;
   };
   

   Чтобы настроить дерево так, чтобы мы могли начинать с краев и двигаться к корню, мы меняем дерево и сохраняем все указатели вдоль путей от корня к левому и крайнему правому дочерним элементам в reverse . (Эти пути называются левым и правым позвоночником соответственно). Так же, как и при изменении односвязного списка, последний элемент становится первым, поэтому теперь можно легко получить доступ к самому левому дочернему элементу.

   Это немного сложно понять. Чтобы объяснить это, представьте, что вы сделали это только для левой части позвоночника:

    struct LeftSpine {
   const char * value;
   int height;
   struct AVLTree * rightChild;
   struct LeftSpine * parent;
   };
   

   В некотором смысле крайний левый дочерний элемент теперь является «корнем» дерева. Если бы вы нарисовали дерево таким образом, это выглядело бы очень странно, но если вы просто возьмете свой обычный рисунок дерева и перевернете все стрелки на левом корешке, значение структуры LeftSpine станет более ясным. Доступ к левой части дерева теперь немедленный. То же самое можно сделать для правого корешка:

    struct RightSpine {
   двойное значение;
   int height;
   struct AVLTree * leftChild;
   struct RightSpine * parent;
   };
   

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

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

2. Ограничение работы по выравниванию баланса

   Как отмечалось выше, вставка в левый или крайний правый конец дерева 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 могут получить доступ к корням деревьев, на которые указывают указатели перехода, за время O (1). Если указатели перехода o (lg n) поддерживаются для всех мест, где потребуется перебалансировка (или изменение информации узла), операции deque могут занять время o (lg n).

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

     Это одна из уловок, использованных Цакалидисом в его статье «Деревья AVL для локализованного поиска» , чтобы разрешить O (1) операций двухсторонней очереди на деревьях AVL с состояние расслабленного равновесия. Это также основная идея, использованная Капланом и Тарьяном в их статье «Чисто функциональные дека в реальном времени с цепочкой» и более поздняя доработка этой идеи Михэсау и Тарьяном . Munro et al.«Детерминированные списки пропусков» также заслуживают упоминания здесь, хотя преобразование списков пропуска в неизменяемую настройку с помощью деревьев иногда изменяет свойства, которые позволяют такую ​​эффективную модификацию ближе к концам. Примеры перевода см. В «Деревья пропуска, альтернативная структура данных для списков пропуска в параллельном подходе» Мессегера, , Дин и Джонс «Исследование двойственности между списками пропуска и деревьями двоичного поиска» и Ламурё и Никерсон «Об эквивалентности B-деревьев и детерминированных списков пропусков» .

   • Выполняйте работу оптом . В приведенном выше примере полного двоичного дерева перебалансировка не требуется, но узлам Ω (lg n) необходимо обновить информацию об их высоте или балансе. Вместо того, чтобы на самом деле делать приращение, вы можете просто пометить корешки на концах как требующие увеличения.

     Один из способов понять этот процесс - провести аналогию с двоичными числами. (2 ^ n) -1 представляется в двоичном виде строкой из n единиц. При добавлении 1 к этому числу вам нужно заменить все 1 на 0, а затем добавить 1 в конце. Следующий Haskell кодирует двоичные числа как непустые строки битов, начиная с наименее значимых.

      бит данных = ноль | Один
     тип Binary = (Bit, [Bit])
     incr :: двоичный -> двоичный
     incr (ноль, х) = (один, х)
     incr (Один, []) = (Ноль, [Один])
     incr (Один, (x: xs)) =
     пусть (y, ys) = incr (x, xs)
     in (ноль, y: ys)
     

     incr - рекурсивная функция, и для чисел вида (One, replicate k One) incr вызывает себя Ω (k) раз.

     Вместо этого мы могли бы представлять группы равных битов только количеством битов в группе. Соседние биты или группы битов объединяются в одну группу, если они равны (по значению, а не по количеству). Мы можем увеличить время O (1):

      data Bits = Zeros Int | Ones Int
     type SegmentedBinary = (биты, [биты])
     segIncr :: SegmentedBinary -> SegmentedBinary
     segIncr (нули 1, []) = (единицы 1, [])
     segIncr (нули 1, (Единицы n: отдых)) = (Единицы (n + 1), отдых)
     segIncr (нули n, остаток) = (единицы 1, нули (n-1): остаток)
     segIncr (Единицы n, []) = (Нули n, [Единицы 1])
     segIncr (единицы n, (нули 1: единицы m: остаток)) = (нули n, единицы (m + 1): остаток)
     segIncr (единицы n, (нули p: остаток)) = (нули n, единицы 1: нули (p-1): остаток)
     

     Поскольку segIncr не рекурсивен и не вызывает никаких функций, кроме плюсов и минусов для Ints, вы можете видеть, что это занимает время O (1).

     Некоторые из двухсторонних дек, упомянутых в разделе выше, озаглавленном «Предвидеть, где потребуется перебалансировка», на самом деле используют другую основанную на числовых обозначениях технику, называемую «избыточные системы счисления», чтобы ограничить работу по перебалансировке до O (1) и быстро определить ее местонахождение. Избыточные числовые представления увлекательны, но, возможно, слишком далеки от этого обсуждения. "Строго регулярная система счисления и структуры данных" Элмасри и др. - неплохое место для начала чтения на эту тему. «Самостоятельная настройка гибких односторонних массивов» Хинце также может быть полезной.

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

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

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

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

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

     Первые два метода ограничения работы по перебалансировке требуют сложных модификаций структур данных, в то же время обычно предоставляя простой анализ сложности операций удаления очереди.Рандомизация, как и следующий метод, позволяет получить более простые структуры данных, но более сложный анализ. Первоначальный анализ Зайделя и Арагона не является тривиальным , и существует некоторый комплексный анализ точных вероятностей с использованием более продвинутой математики, чем представлен в упомянутых выше статьях - см. Flajolet et al. «Паттерны в случайных деревьях двоичного поиска» .

   • Амортизировать . Есть несколько сбалансированных деревьев, которые, если смотреть от корней вверх (как объяснено в разделе «Перевернуть шипы» выше), предлагают O (1) амортизированное время вставки и удаления . Отдельные операции могут занимать время Ω (lg n), но они переводят дерево в такое хорошее состояние, что большое количество операций, следующих за дорогостоящей операцией, будет дешевым.

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

     Один из способов получить амортизированные границы в постоянной настройке был изобретен Крисом Окасаки . Непросто объяснить, как амортизация выживает благодаря возможности использовать произвольные старые версии структуры данных, но, если я правильно помню, первая (насколько мне известно) статья Окасаки по этому вопросу имеет довольно приятный вид. четкое объяснение. Для более полных объяснений см. его диссертацию или его книгу .

     Насколько я понимаю, есть два основных ингредиента.Во-первых, вместо того, чтобы просто гарантировать выполнение определенного количества дешевых операций перед каждой дорогостоящей операцией (обычный подход к амортизации)вы фактически назначаете и настраиваете эту конкретную дорогостоящую операцию перед выполнением дешевых операций, которые будут за нее платить. В некоторых случаях планируется запуск (и завершение) операции только после множества промежуточных дешевых шагов. В других случаях операция фактически запланирована только на O (1) шагов в будущем, но дешевые операции могут выполнять часть дорогостоящей операции, а затем перенести ее на более позднее время. Если злоумышленник пытается повторять дорогостоящую операцию снова и снова, фактически каждый раз повторно использует одну и ту же запланированную операцию. В этом совместном использовании появляется второй ингредиент.

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

      #include 
     struct lazy {
     int (* опер) (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) {
     если (0 == susp) возврат;
     если (0! = susp-> ans) возврат;
     susp-> ans = (int *) malloc (sizeof (int));
      * susp-> ans = susp-> oper (susp-> arg);
     }
     int get (lazyop susp) {
     сила (сусп);
     return * susp-> ans;
     }
     

     Конструкции Laziness включены в некоторые ML, и Haskell по умолчанию является ленивым.Под капотом лень - это мутация, из-за которой некоторые авторы называют ее «побочным эффектом». Это может считаться плохим, если такой побочный эффект не сочетается с какими бы то ни было причинами для выбора неизменной структуры данных в первую очередь, но, с другой стороны, представление о лени как о побочном эффекте позволяет применять традиционные методы амортизированного анализа устойчивых структур данных, как упоминалось в статье Каплана, Окасаки и Тарджана, озаглавленной «Простые непрерывно постоянные списки с возможностью последовательной привязки» .

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

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

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

     В качестве доказательства того, насколько сложен для понимания амортизированный анализ, деревья пальцев Хинце и Патерсона часто реализуются без лени, делая временные рамки не O (1), но все же О (LG N). Одна реализация, которая, кажется, использует лень, - это реализация в financial-dotnet . Этот проект также включает реализацию ленивых значений в C # , которая может помочь объяснить их, если мое объяснение выше отсутствует.

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

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

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

2. Я знаю два способа реализации двухсторонней очереди, не использующей деревья. Окасаки представляет один в своей книге и диссертации, а также в статье, на которую я ссылался выше. Другой использует технику, называемую «глобальное перестроение», и она представлена ​​в Чуанге и Голдберге «Deques реального времени, многоголовые машины Тьюринга и чисто функциональное программирование» .