Козел отпущения - Scapegoat tree

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

В Информатика, а козел отпущения это самобалансирующееся двоичное дерево поиска, изобретенный Арне Андерссон^[1] и снова Игал Гальперин и Рональд Л. Ривест.^[2] Это обеспечивает наихудший случай О (бревно п) время поиска и О(бревно п) амортизированный время вставки и удаления.

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

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

Теория

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

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

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

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

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

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

высота (дерево) ≤ log1 / α(размер (дерево)) ⌋

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

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

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

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

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

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

Операции

Искать

Поиск не изменяется по сравнению со стандартным двоичным деревом поиска и имеет время наихудшего случая O (log п). Это в отличие от растопыренные деревья которые имеют время наихудшего случая O (п). Уменьшение накладных расходов на память узла по сравнению с другими самобалансирующимися деревьями двоичного поиска может еще больше улучшить местонахождение ссылки и кеширование.

Вставка

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

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

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

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

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

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

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

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

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

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

Но, как:

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

Дело упрощено до:

размер [x + 1] = размер [x] + размер (родственник) + 1

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

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

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

Эскиз доказательства стоимости вставки

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

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

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

Лемма: Непосредственно перед восстановлением поддерева с корнем v,
${\displaystyle I(v)\in \Omega (|v|)}$
(${\displaystyle \Omega }$ является Обозначение Big Omega.)

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

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

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

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

Удаление

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

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

NodeCount ≤ α * MaxNodeCount

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

Это дает удалению его наихудшую производительность O (п) время; однако он амортизируется до O (log п) среднее время.

Эскиз доказательства стоимости удаления

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

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

Этимология

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

Смотрите также

• Splay tree
• Деревья
• Вращение дерева
• AVL дерево
• B-дерево
• Т-образное дерево
• Список структур данных

Рекомендации

1. Андерссон, Арне (1989). Улучшение частичного восстановления за счет использования простых критериев баланса. Proc. Практикум по алгоритмам и структурам данных. Журнал алгоритмов. Springer-Verlag. С. 393–402. CiteSeerX  10.1.1.138.4859. Дои:10.1007/3-540-51542-9_33.
2. Гальперин, Игал; Ривест, Рональд Л. (1993). Деревья козлов отпущения (PDF). Материалы четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Филадельфия: Общество промышленной и прикладной математики. С. 165–174. CiteSeerX  10.1.1.309.9376. ISBN  0-89871-313-7.
3. Морен, Пат. «Глава 8 - Деревья-козлы отпущения». Структуры открытых данных (в псевдокоде) (0.1G β ред.). Получено 2017-09-16.

внешняя ссылка

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