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

редактировать

дерево

Изобретено

Временная сложность в нотации большого O

Алгоритм	Среднее значение	Худший случай
Пробел	O (n)	O (n)
Поиск	O (log n)	O (log n)
Вставить	O (log n)	с амортизированной O (log n)
Удалить	O ( log n)	амортизированный O (log n)

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

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

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

Содержание

1 Теория
2 Операции
- 2.1 Поиск
- 2.2 Вставка
  - 2.2.1 Эскиз доказательства стоимости вставки
- 2.3 Удаление
  - 2.3.1 Эскиз доказательство стоимости удаления
3 Этимология
4 См. также
5 Ссылки
6 Внешние ссылки

Теория

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

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

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

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

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

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

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

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

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

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

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

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

В отличие от большинства других самобалансирующихся деревьев поиска, деревья козлов отпущения полностью гибки в отношении их балансировки. Они поддерживают любое α, такое что 0,5 < α < 1. A high α value results in fewer balances, making insertion quicker but lookups and deletions slower, and vice versa for a low α. Therefore in practical applications, an α can be chosen depending on how frequently these actions should be performed.

Операции

Поиск

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

Вставка

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

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

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

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

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

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

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

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

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

size (parent) = size (node) + size (sibling) + 1

Но как:

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

Случай упрощается до:

size [x + 1] = size [x] + size (sibling) + 1

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

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

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

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

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

$I (v) = max ⁡ (| слева ⁡ (v) - справа ⁡ (v) | - 1, 0) {\ displaystyle I (v) = \ operatorname {max} (| \ operatorname {left} (v) - \ operatorname {right} (v) | -1,0)}$ ${\ displaystyle I (v) = \ operatorname {max} (| \ operatorname {left} (v) - \ operatorname {right} (v) | -1,0)}$

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

Лемма: Немедленно перед восстановлением поддерева с корнем v,. $I (v) ∈ Ω (| v |) {\ displaystyle I (v) \ in \ Omega (| v |)}$ ${\ displaystyle I (v) \ in \ Omega (| v |)}$ . ( $Ω {\ displaystyle \ Omega}$ $\ Omega$ is.)

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

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

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

$Ω (| v |) O ( журнал ⁡ N) + О (| v |) Ω (| v |) = O (журнал ⁡ N) {\ Displaystyle {\ Omega (| v |) O (\ log {n}) + O (| v |) \ over \ Omega (| v |)} = 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

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

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

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

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

$∑ 1 n 2 O (log ⁡ n) + O (N) N 2 знак равно N 2 О (журнал ⁡ N) + O (N) N 2 = O (журнал ⁡ N) {\ Displaystyle {\ sum _ {1} ^ {n \ более 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}) \}$ ${\ 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}) \$

Этимология

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

См. Также

Ссылки

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

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