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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Март 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Дерево козлов отпущения»  -  новости  · газеты  · книги  · ученый  · JSTOR ( март 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

Теория [ править ]

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

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

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

размер функции (узел) равен,  если node = nil, затем  вернуть 0, иначе  вернуть размер (node-> left) + size (node-> right) + 1 end if end function

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

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

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

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

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

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

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

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

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

Операции [ править ]

Поиск [ править ]

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

Вставка [ править ]

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

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

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

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

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

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

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

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

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

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

Но, как:

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

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

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

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

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

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

Эскиз доказательства стоимости вставки [ править ]

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

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

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

Лемма: Непосредственно перед восстановлением поддерева с корнем в V , ( это Big Omega Notation ) .
${\ Displaystyle I (v) \ in \ Omega (| v |)}$
${\ displaystyle \ Omega}$

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

Позвольте быть корнем поддерева сразу после восстановления. . Если есть вырожденные вставки (то есть, где каждый узел вставляется увеличивает высоту на 1), а затем , и .${\ displaystyle v_ {0}}$${\ displaystyle h (v_ {0}) = \ log (| v_ {0} | +1)}$${\ displaystyle \ Omega (| v_ {0} |)}$
${\ 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 ( n ); однако оно амортизируется до среднего времени O (log n ).

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

Предположим, что дерево козлов отпущения имеет элементы и только что было перестроено (другими словами, это полное двоичное дерево). В большинстве случаев удаление может быть выполнено перед восстановлением дерева. Каждое из этих удалений требует времени (время, необходимое для поиска элемента и отметки его как удаленного). Удаление приводит к тому , дерево будет восстановлен и принимает (или только ) время. Используя агрегированный анализ, становится ясно, что амортизированная стоимость удаления составляет :${\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-дерево
• Т-образное дерево
• Список структур данных

Ссылки [ править ]

Внешние ссылки [ править ]

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