Дерево козла отпущения

Дерево козла отпущения
Тип	дерево
Изобретенный	1989
Изобретён	Арне Андерссон , Игаль Гальперин , Рональд Л. Ривест
Сложности в обозначении большого О
Пространственная сложность Космос $O(n)$ Временная сложность Функция Амортизированный Худший случай Поиск $O(\log n)$ $O(\log n)$ Вставлять $O(\log n)$ $O(n)$ Удалить $O(\log n)$ $O(n)$

В информатике — дерево козла отпущения это самобалансирующееся двоичное дерево поиска , изобретенное Арне Андерссоном. в 1989 году и снова Игалом Гальперином и Рональдом Л. Ривестом в 1993 году. Это обеспечивает наихудший случай ${\color {Blue}O(\log n)}$ время поиска (с $n$ как количество записей) и $O(\log n)$ амортизированное время вставки и удаления.

В отличие от большинства других самобалансирующихся двоичных деревьев поиска, которые также обеспечивают худший случай $O(\log n)$ Во время поиска деревья козла отпущения не требуют дополнительных затрат памяти на каждый узел по сравнению с обычным двоичным деревом поиска : помимо ключа и значения узел хранит только два указателя на дочерние узлы. Это упрощает реализацию деревьев козла отпущения и, благодаря выравниванию структуры данных , может снизить накладные расходы узлов до одной трети.

Вместо небольших дополнительных операций ребалансировки, используемых большинством алгоритмов сбалансированного дерева, деревья козла отпущения редко, но дорого выбирают «козла отпущения» и полностью перестраивают поддерево, корнем которого является «козл отпущения», в полное двоичное дерево. Таким образом, деревья козлов отпущения $O(n)$ производительность обновления в худшем случае.

Теория

Бинарное дерево поиска называется сбалансированным по весу, если половина узлов находится слева от корня, а половина — справа.Узел со сбалансированным по весу определяется как отвечающий критерию смягченного баланса веса:

размер (слева) ≤ α*размер (узел)размер(справа) ≤ α*размер(узел) 

Где размер можно определить рекурсивно как:

размер функции  (узел)  :      если  узел = ноль  , то          возвращается  0     иначе          вернуть  размер (узел-> влево) + размер (узел-> вправо) + 1     конец, если  функция завершения 

Даже вырожденное дерево (связный список) удовлетворяет этому условию, если α=1, тогда как α=0,5 будет соответствовать только почти полным двоичным деревьям .

Бинарное дерево поиска, сбалансированное по α-весу, также должно быть сбалансированным по α-высоте , то есть

высота(дерево) ≤ пол(log  1/α  (размер(дерево))) 

В противоположность этому , дерево, которое не сбалансировано по α-высоте, не является сбалансированным по α-весу.

Деревья козлов отпущения не гарантируют постоянное сохранение α-баланса веса, но всегда слабо сбалансированы по α-высоте.

высота(дерево козла отпущения) ≤ пол(log  1/α  (размер(дерево))) + 1. 

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

Это делает деревья козлов отпущения похожими на красно-черные деревья , поскольку у них обоих есть ограничения по высоте. Однако они сильно различаются в своей реализации определения того, где происходят вращения (или, в случае с деревьями козлов отпущения, перебалансировка). В то время как красно-черные деревья хранят дополнительную «цветовую» информацию в каждом узле для определения местоположения, деревья козла отпущения находят козла отпущения , который не сбалансирован по α-весу, для выполнения операции перебалансировки. Это во многом похоже на деревья AVL , поскольку фактическое вращение зависит от «баланса» узлов, но способы определения баланса сильно различаются. Поскольку деревья AVL проверяют значение баланса при каждой вставке/удалении, оно обычно сохраняется в каждом узле; Деревья козлов отпущения способны вычислить его только по мере необходимости, то есть только тогда, когда нужно найти козла отпущения.

В отличие от большинства других самобалансирующихся деревьев поиска, деревья козлов отпущения совершенно гибки в плане балансировки. Они поддерживают любое значение α, такое, что 0,5 < α < 1. Высокое значение α приводит к меньшему количеству балансов, что делает вставку более быстрой, но поиск и удаление медленнее, и наоборот для низкого α. Поэтому в практических приложениях α можно выбирать в зависимости от того, как часто следует выполнять эти действия.

Операции

Поиск

Поиск не отличается от стандартного двоичного дерева поиска и имеет время наихудшего случая $O(\log n)$. В этом отличие от раскидистых деревьев , у которых наихудшее время $O(n)$. Сокращение накладных расходов на память узла по сравнению с другими самобалансирующимися двоичными деревьями поиска может еще больше улучшить локальность ссылок и кэширование.

Вставка

Вставка реализована на основе тех же основных идей, что и несбалансированное двоичное дерево поиска , однако с некоторыми существенными изменениями.

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

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

Один из способов найти козла отпущения — подняться от нового узла обратно к корню и выбрать первый узел, который не сбалансирован по α-весу.

Чтобы подняться обратно к корню, необходимо $O(\log n)$ пространство хранения, обычно выделяемое в стеке или родительских указателях. На самом деле этого можно избежать, направляя каждого дочернего элемента на его родителя, когда вы спускаетесь, и восстанавливая его на обратном пути.

Чтобы определить, является ли потенциальный узел жизнеспособным козлом отпущения, нам нужно проверить его свойство сбалансированности α-веса. Для этого вернемся к определению:

размер (слева) ≤ α*размер (узел)размер(справа) ≤ α*размер(узел) 

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

Рассмотрим следующий пример, чтобы продемонстрировать это. Предполагая, что мы поднимаемся обратно к корню:

размер(родительский) = размер(узел) + размер(родственный) + 1 

Но как:

размер (вставленный узел) = 1. 

Дело упрощается до:

размер[x+1] = размер[x] + размер(одноуровневый) + 1 

Где x = этот узел, x + 1 = родительский элемент и size(sibling) — единственный фактически требуемый вызов функции.

Как только козел отпущения найден, поддерево, берущее начало в козле отпущения, полностью перестраивается и становится идеально сбалансированным. Это можно сделать в $O(n)$ время, проходя узлы поддерева, чтобы найти их значения в отсортированном порядке и рекурсивно выбирая медиану в качестве корня поддерева.

По мере выполнения операций ребалансировки $O(n)$ время (зависит от количества узлов поддерева), вставка имеет наихудшую производительность $O(n)$ время. Однако, поскольку эти наихудшие сценарии распределены, вставка занимает $O(\log n)$ амортизированное время.

Эскиз подтверждения стоимости внедрения

Определите дисбаланс узла v как абсолютное значение разницы в размерах между его левым и правым узлами минус 1 или 0, в зависимости от того, что больше. Другими словами:

$I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)$

Сразу после восстановления поддерева с корнем в v I( v ) = 0.

Лемма: Непосредственно перед перестроением поддерева с корнем в v ,
$I(v)\in \Omega (|v|)$
( $\Omega$ это обозначение Большой Омеги .)

Доказательство леммы:

Позволять $v_{0}$ быть корнем поддерева сразу после перестроения. $h(v_{0})=\log(|v_{0}|+1)$. Если есть $\Omega (|v_{0}|)$ вырожденные вставки (то есть когда каждый вставленный узел увеличивает высоту на 1), затем
$I(v)\in \Omega (|v_{0}|)$,
$h(v)=h(v_{0})+\Omega (|v_{0}|)$ и
$\log(|v|)\leq \log(|v_{0}|+1)+1$.

С $I(v)\in \Omega (|v|)$ до перестройки были $\Omega (|v|)$ вставки в поддерево с корнем в $v$ это не привело к восстановлению. Каждая из этих вставок может быть выполнена в $O(\log n)$ время. Последняя вставка, вызывающая затраты на восстановление. $O(|v|)$. Используя совокупный анализ, становится ясно, что амортизированная стоимость внедрения равна $O(\log n)$:

${\Omega (|v|)O(\log n)+O(|v|) \over \Omega (|v|)}=O(\log n)$

Удаление

Деревья козлов отпущения необычны тем, что удалить их проще, чем вставить. Чтобы обеспечить удаление, деревьям козла отпущения необходимо сохранить дополнительное значение в древовидной структуре данных. Это свойство, которое мы назовем MaxNodeCount, просто представляет собой наивысший достигнутый NodeCount. Для него устанавливается значение NodeCount при каждой перебалансировке всего дерева, а после вставки устанавливается значение max(MaxNodeCount, NodeCount).

Чтобы выполнить удаление, мы просто удаляем узел, как в простом двоичном дереве поиска, но если

NodeCount ≤ α*MaxNodeCount 

затем мы перебалансируем все дерево относительно корня, не забывая установить для MaxNodeCount значение NodeCount.

Это приводит к худшему результату удаления: $O(n)$ время, тогда как амортизированное время $O(\log n)$.

удаления

Предположим, что дерево козла отпущения имеет $n$ элементов и только что перестроено (другими словами, это полное двоичное дерево). Максимум $n/2-1$ удаление может быть выполнено до того, как дерево будет перестроено. Каждое из этих удалений занимает $O(\log n)$ время (количество времени для поиска элемента и пометки его как удаленного). $n/2$ удаление приводит к перестроению дерева и занимает $O(\log n)+O(n)$ (или просто $O(n)$) время. Используя совокупный анализ, становится ясно, что амортизированная стоимость удаления равна $O(\log n)$:

${\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\$

Этимология

Название «Дерево козла отпущения » «[...] основано на общепринятом понимании, что, когда что-то идет не так, первое, что люди склонны делать, это найти виноватого (козла отпущения)». В Библии козлом отпущения является животное, которое ритуально обременяют грехами других, а затем прогоняют.

См. также

• Распространение дерева
• Деревья
• Вращение дерева
• АВЛ-дерево
• B-дерево
• Т-образное дерево

Внешние ссылки

• Гальперн, Игал (сентябрь 1996 г.). О консультировании группы экспертов и поиске (PDF) (кандидатская диссертация). Массачусетский технологический институт .
• Морен, Пэт. «Глава 8 — Деревья козла отпущения» . Открытые структуры данных (в псевдокоде) (0.1G β-ред.) . Проверено 16 сентября 2017 г.