Как отмечено вышедля вставки в левый или правый конец дерева AVL может потребоваться время (lg n) для прохождения позвоночника.Вот пример дерева AVL, которое демонстрирует это:
При перемещении элемента слева от полного двоичного дерева обязательноувеличить максимальную высоту дерева.Поскольку вышеупомянутые деревья AVL хранят эту информацию в каждом узле, и поскольку каждое дерево вдоль левого корешка полного двоичного дерева также является полным двоичным деревом, элемент, помещаемый слева от декы AVL, который оказывается полным двоичным деревомпотребует увеличения значений высоты Ω (lg n) вдоль левого отдела позвоночника.
(Два замечания по этому поводу: (a) Вы можете хранить деревья AVL, не сохраняя высоту в узле; вместо этого вы сохраняете только информацию о балансе (слева выше, справа выше или даже). Это не меняет производительность приведенного выше примера. (b) В деревьях AVL может потребоваться не только обновление информации о балансе или высоте Omega; (lg n), но и операции перебалансировки Omega; (lg n). это, и это может быть только на удалениях, а не вставках.)
Чтобы выполнить o (lg n) deque операций, нам нужно ограничить эту работу. Неизменяемые запросы, представленные сбалансированными деревьями, обычно используют по крайней мере одну из следующих стратегий:
Предвидеть, где потребуется перебалансировка . Если вы используете дерево, которое требует o (lg n) перебалансировки, но вы знаете, где будет необходимо это перебалансирование и , вы можете добраться до него достаточно быстро, вы можете выполнять свои операции deque за o (lg n) время , В запросах, использующих это как стратегию, в деку будут помещены не только два указателя (концы левого и правого отростков, как обсуждалось выше), но и небольшое количество указателей прыжка в более высокие места вдоль отрубей , Операции Deque могут затем получить доступ к корням деревьев, на которые указывают указатели перехода в O (1) времени. Если o (lg n) указатели перехода поддерживаются для всех мест, где потребуется перебалансировка (или изменение информации об узле), операции удаления могут занять время o (lg n).
(Конечно, это делает дерево фактически дагом, поскольку на деревьях в шипах, на которые указывают указатели прыжков, их дети также указывают на позвоночник. Неизменяемые структуры данных обычно не уживаются с не-деревом графики, так как замена узла, на который указывает более одного узла, требует замены всех других узлов, которые указывают на него. Я видел это исправленным, просто удалив указатели без перехода, превратив даг обратно в дерево. Можно затем сохраните односвязный список с указателями перехода в виде списка списков. Каждый подчиненный список содержит все узлы между заголовком этого списка и указателем перехода. Это требует некоторой осторожности при работе с частично перекрывающимися указателями перехода и полным объяснение, вероятно, не подходит для этого в стороне.)
Это один из приемов, используемых Цакалидисом в своей статье "Деревья AVL для локализованного поиска" , чтобы разрешить O (1) операции deque на деревьях AVL с ослабленным условием баланса. Это также основная идея, использованная Капланом и Тарьяном в их работе «Чисто функциональные запросы в реальном времени с конкатенацией» и более позднее уточнение этой работы Михаэзау и Тарьяном . Munro et al. "Детерминированные списки пропусков" также заслуживает упоминания здесь, хотя перевод списков пропусков в неизменяемую настройку с использованием деревьев иногда изменяет свойства, которые позволяют такое эффективное изменение вблизи концов. Примеры перевода см. В Messeguer "Пропускать деревья, альтернативную структуру данных пропускающим спискам в параллельном подходе" , Дин и Джонс "Изучение двойственности между пропускающими списками и бинарными деревьями поиска" и Lamoureux and Nickerson "Об эквивалентности 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 вызывает себя Ω (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. "Строго регулярная система счисления и структуры данных" - неплохое место для начала чтения по этой теме. Может также пригодиться «Начальная загрузка односторонних гибких массивов» .
In «Обеспечение постоянства структур данных» , Driscoll et al.опишите ленивый перекрас , который они приписывают Цакалидису.Они применяют его к красно-черным деревьям, которые могут быть перебалансированы после вставки или удаления с помощью поворотов O (1) (но перекрашивания Ω (lg n)) (см. Тарьяна «Обновление сбалансированного дерева в поворота O (1)»).Суть идеи заключается в маркировке большого пути узлов, которые необходимо перекрасить, но не повернуть.Аналогичная идея используется на деревьях AVL в более старых версиях Brown & Tarjan «Алгоритм быстрого слияния» .(Более новые версии той же работы используют 2-3 дерева; я не читал более новые, и я не знаю, используют ли они какие-либо методы, такие как ленивая перекраска.)
Перемешайте .Treaps, упомянутые выше, могут быть реализованы в функциональной настройке так, чтобы они выполняли операции deque в среднем за O (1) времени.Поскольку запросам не нужно проверять свои элементы, это среднее значение не подвержено снижению производительности злонамеренного ввода, в отличие от простых (без перебалансировки) деревьев двоичного поиска, которые в среднем работают быстро.Трипы используют независимый источник случайных битов вместо того, чтобы полагаться на случайность данных.
В постоянных настройках трепы могут быть подвержены снижению производительности из-за злонамеренного ввода данных злоумышленником, который может (а) использовать старые версииструктуры данных и (б) измерить производительность операций.Поскольку у них нет никаких гарантий баланса в худшем случае, трепы могут стать совершенно несбалансированными, хотя это случается редко.Если злоумышленник ожидает операции deque, которая занимает много времени, он может многократно инициировать ту же самую операцию, чтобы измерить и использовать, возможно, несбалансированное дерево.
Если это не представляет проблемы, ошибки являютсяпривлекательная простая структура данных.Они очень близки к описанному выше дереву позвоночника AVL.
Упомянутые выше списки пропусков также могут быть применимы к функциональным реализациям с O (1) операциями блокировки среднего времени.
ПервыйДва метода ограничения работы по перебалансировке требуют сложных модификаций в структурах данных, обычно обеспечивая простой анализ сложности операций deque.Рандомизация, наряду со следующим методом, имеет более простые структуры данных, но более сложный анализ. Первоначальный анализ Зейделя и Арагона не является тривиальным , и существует некоторый комплексный анализ точных вероятностей с использованием более сложной математики, чем в приведенных выше работах - см. Flajolet et al.«Шаблоны в случайных бинарных деревьях поиска» .
амортизировать . Существует несколько сбалансированных деревьев, которые, если смотреть из корней вверх (как описано выше в разделе «Перевернуть шипы»), предлагают O (1) амортизированное время вставки и удаления. Отдельные операции могут занять & Omega; (LG N) время, но они помещают дерево в такое хорошее состояние, что большое количество операций после дорогой операции будет дешевым.
К сожалению, этот вид анализа не работает, когда старые версии дерева все еще существуют. Пользователь может выполнять операции со старым, почти несбалансированным деревом много раз, не вмешиваясь в дешевые операции.
Один из способов получения амортизированных границ в постоянных условиях был изобретен Крисом Окасаки . Не просто объяснить, как амортизация переживает способность использовать произвольные старые версии структуры данных, но если я правильно помню, Первая (насколько я знаю) статья Окасаки по теме имеет довольно четкое объяснение. Более подробные объяснения см. В его диссертации или в его книге .
Насколько я понимаю, есть два основных компонента. Во-первых, вместо того, чтобы просто гарантировать, что определенное количество дешевых операций происходит перед каждой дорогой операцией (обычный подход к амортизации), вы фактически назначаете и настраиваете эту специфическую дорогую операцию до выполнения дешевые операции, которые окупят это. В некоторых случаях операцию планируется начать (и завершить) только после множества дешевых шагов. В других случаях операция запланирована только на O (1) шагов в будущем, но дешевые операции могут сделать часть дорогостоящей операции, а затем перепланировать ее на более позднее время. Если злоумышленник, желающий повторять дорогостоящую операцию снова и снова, фактически каждый раз использует одну и ту же запланированную операцию. Это разделение, где появляется второй ингредиент.
Вычисление настроено с использованием laziness . Ленивое значение вычисляется не сразу, но после выполнения его результат сохраняется. В первый раз, когда клиент должен проверить ленивое значение, его значение вычисляется. Более поздние клиенты могут использовать это кэшированное значение напрямую, без необходимости пересчитывать его.
#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). Одна из реализаций, которая, кажется, использует лень, - это в функциональной сети dotnet . Этот проект также включает реализацию отложенных значений в C # , которая может помочь объяснить их, если мое объяснение выше отсутствует.