AVL дерево - AVL tree

AVL дерево
Тип	дерево
Изобрел	1962
Изобретенный	Георгий Адельсон-Вельский и Евгений Ландис
Сложность времени в нотация большой O
Алгоритм Средний Худший случай Космос ${displaystyle O(n)}$ ${displaystyle O(n)}$ Поиск ${displaystyle O(log n)}$[1] ${displaystyle O(log n)}$[1] Вставлять ${displaystyle O(log n)}$[1] ${displaystyle O(log n)}$[1] Удалить ${displaystyle O(log n)}$[1] ${displaystyle O(log n)}$[1]

Анимация, показывающая вставку нескольких элементов в дерево AVL. Он включает в себя вращение влево, вправо, влево-вправо и вправо-влево.

Рис.1: AVL-дерево с коэффициентами баланса (зеленый)

В Информатика, AVL дерево (назван в честь изобретателей АDelson-VЭльски и Landis) является самобалансирующееся двоичное дерево поиска. Это был первый такой структура данных быть изобретенным.^[2] В дереве AVL высоты из двух ребенок поддеревья любого узла отличаются не более чем на единицу; если в любой момент они отличаются более чем на единицу, выполняется повторная балансировка для восстановления этого свойства. Поиск, вставка и удаление - все это О (бревно п) время как в среднем, так и в худшем случае, когда ${displaystyle n}$ - количество узлов в дереве до операции. Вставки и удаления могут потребовать перебалансировки дерева одним или несколькими вращения деревьев.

Дерево AVL названо в честь двух Советский изобретатели, Георгий Адельсон-Вельский и Евгений Ландис, которые опубликовали его в своей статье 1962 года «Алгоритм организации информации».^[3]

Деревья AVL часто сравнивают с красно-черные деревья потому что оба поддерживают одинаковый набор операций и принимают ${displaystyle O(log n)}$ время на основные операции. Для приложений с интенсивным поиском деревья AVL быстрее, чем красно-черные деревья, потому что они более строго сбалансированы.^[4] Подобно красно-черным деревьям, деревья AVL сбалансированы по высоте. Оба, в общем, ни сбалансированный по весу ни ${displaystyle mu }$-балансированный для любых ${displaystyle mu leq { frac {1}{2}}}$;^[5] то есть одноуровневые узлы могут иметь сильно различающееся количество потомков.

Определение

Фактор баланса

В двоичное дерево то коэффициент баланса из ${displaystyle node}$ определяется как разница высот

${displaystyle { ext{BalanceFactor}}(node):={ ext{Height}}({ ext{RightSubtree}}(node))-{ ext{Height}}({ ext{LeftSubtree}}(node))}$^[6]

двух его дочерних поддеревьев. Бинарное дерево определяется как AVL дерево если инвариантный

${displaystyle { ext{BalanceFactor}}(node)in {{-1,0,1}}}$^[7]

справедливо для каждого ${displaystyle node}$ в дереве.

А ${displaystyle node}$ с ${displaystyle { ext{BalanceFactor}}(node)<0}$ называется "лево-тяжелый", один с ${displaystyle { ext{BalanceFactor}}(node)>0}$ называется "тяжелая правая", а одна с ${displaystyle { ext{BalanceFactor}}(node)=0}$ иногда просто называют «сбалансированным».

Замечание

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

Характеристики

Коэффициенты балансировки можно поддерживать в актуальном состоянии, зная предыдущие коэффициенты балансировки и изменение высоты - нет необходимости знать абсолютную высоту. Для хранения информации баланса AVL традиционным способом достаточно двух битов на узел. Однако более поздние исследования показали, что если дерево AVL реализовано как сбалансированное по рангам дерево с допускаемыми дельта-рангами 1 или 2 - со значением «при движении вверх происходит дополнительное увеличение высоты на один или два», это можно сделать с помощью одного кусочек.

Высота ${displaystyle h}$ (подсчитывается как количество ребер на самом длинном пути) дерева AVL с ${displaystyle n}$ узлов лежит в интервале:^[8]

${displaystyle log _{2}(n+1)-1leq h<log _{varphi }(n+2)+b}$

куда ${displaystyle varphi }$ это Золотое сечение и ${displaystyle bapprox -1.3277}$Это потому, что дерево AVL высота содержит как минимум F_{высота+2} – 1 узлы, где {F_п} это Последовательность Фибоначчи с начальными значениями F₁ = 1, F₂ = 1.

Операции

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

Поиск

Поиск определенного ключа в дереве AVL может выполняться так же, как и поиск любого сбалансированного или несбалансированного двоичное дерево поиска.^{[9]:гл. 8} Чтобы поиск работал эффективно, он должен использовать функцию сравнения, которая устанавливает общий заказ (или, по крайней мере, общий предварительный заказ ) на наборе ключей.^[10]:23 Количество сравнений, необходимых для успешного поиска, ограничено высотой час и за безуспешный поиск очень близок к час, так что оба находятся в O (журнал п).^[11]:216

Обход

После того, как узел был найден в дереве AVL, следующий или же предыдущий узел можно получить в амортизированный постоянное время. Некоторые экземпляры исследования этих «ближайших» узлов требуют прохождения до час ∝ журнал (п) ссылок (особенно при переходе от крайнего правого листа левого поддерева корня к корню или от корня к крайнему левому листу правого поддерева корня; в дереве AVL на рисунке 1 переход от узла P к следующий, но один узел Q занимает 3 шага). Однако исследуя все п узлы дерева таким образом будут посещать каждую ссылку ровно дважды: одно посещение вниз, чтобы войти в поддерево, укорененное этим узлом, другое посещение вверх, чтобы покинуть поддерево этого узла после его исследования. А поскольку есть п−1 ссылок в любом дереве, амортизированная стоимость 2×(п−1)/п, или примерно 2.

Вставлять

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

После этой вставки, если дерево становится несбалансированным, только предки вновь вставленного узла не сбалансированы. Это потому, что поддеревья изменены только у этих узлов.^[12] Таким образом, необходимо проверить каждого из предков узла на соответствие инвариантам деревьев AVL: это называется «повторным отслеживанием». Это достигается за счет учета коэффициент баланса каждого узла.^[13][14]

Поскольку при однократной вставке высота поддерева AVL не может увеличиваться более чем на единицу, временный коэффициент балансировки узла после вставки будет в диапазоне [–2,+2]. Для каждого проверенного узла, если временный коэффициент баланса остается в диапазоне от –1 до +1, то требуется только обновление коэффициента балансировки и никакого ротации не требуется. Однако, если временный коэффициент балансировки становится меньше -1 или больше +1, поддерево с корнем в этом узле является несбалансированным по AVL, и требуется ротация.^[10]:52 При вставке, как показано в приведенном ниже коде, адекватное вращение сразу идеально перебалансирует дерево.

На рисунке 1 при вставке нового узла Z в качестве дочернего узла X высота этого поддерева Z увеличивается с 0 до 1.

Инвариантный возвратной петли для вставки

Высота поддерева с корнем Z увеличилась на 1. Оно уже имеет форму AVL.

Пример кода для операции вставки

1 за (Икс = родитель(Z); Икс != ноль; Икс = родитель(Z)) { // Цикл (возможно, до корня) 2 // Необходимо обновить BalanceFactor (X): 3 если (Z == right_child(Икс)) { // Правое поддерево увеличивается 4 если (BalanceFactor(Икс) > 0) { // X тяжелый справа 5 // ===> временный BalanceFactor (X) == +2 6 // ===> требуется ребалансировка. 7 грамм = родитель(Икс); // Сохраняем родительский элемент X вокруг поворота 8 если (BalanceFactor(Z) < 0) // Правый левый регистр (см. Рисунок 5) 9 N = rotate_RightLeft(Икс, Z); // Двойное вращение: вправо (Z), затем влево (X)10 еще // Правый регистр справа (см. Рисунок 4)11 N = повернуть налево(Икс, Z); // Один поворот влево (X)12 // После поворота адаптируем родительскую ссылку13 } еще {14 если (BalanceFactor(Икс) < 0) {15 BalanceFactor(Икс) = 0; // Увеличение высоты Z поглощается в X.16 перемена; // Выходим из цикла17 }18 BalanceFactor(Икс) = +1;19 Z = Икс; // Высота (Z) увеличивается на 120 Продолжить;21 }22 } еще { // Z == left_child (X): левое поддерево увеличивается23 если (BalanceFactor(Икс) < 0) { // X тяжелее слева24 // ===> временный BalanceFactor (X) == –225 // ===> требуется ребалансировка.26 грамм = родитель(Икс); // Сохраняем родительский элемент X вокруг поворота27 если (BalanceFactor(Z) > 0) // Левый Правый Регистр28 N = rotate_LeftRight(Икс, Z); // Двойное вращение: влево (Z), затем вправо (X)29 еще // Левый регистр слева30 N = rotate_Right(Икс, Z); // Одиночный поворот вправо (X)31 // После поворота адаптируем родительскую ссылку32 } еще {33 если (BalanceFactor(Икс) > 0) {34 BalanceFactor(Икс) = 0; // Увеличение высоты Z поглощается в X.35 перемена; // Выходим из цикла36 }37 BalanceFactor(Икс) = –1;38 Z = Икс; // Высота (Z) увеличивается на 139 Продолжить;40 }41 }42 // После поворота адаптируем родительскую ссылку:43 // N - новый корень повернутого поддерева44 // Высота не меняется: Height (N) == old Height (X)45 родитель(N) = грамм;46 если (грамм != ноль) {47 если (Икс == left_child(грамм))48 left_child(грамм) = N;49 еще50 right_child(грамм) = N;51 } еще52 дерево->корень = N; // N - новый корень всего дерева53 перемена;54 // Нет провала, только перерыв; или продолжить;55 }56 // Если цикл не выходит через break, высота всего дерева увеличивается на 1.

Чтобы обновить коэффициенты баланса всех узлов, сначала обратите внимание, что все узлы, требующие исправления, лежат от дочернего к родительскому по пути вставленного листа. Если описанная выше процедура применяется к узлам на этом пути, начиная с листа, то каждый узел в дереве снова будет иметь коэффициент баланса -1, 0 или 1.

Восстановление может быть остановлено, если коэффициент баланса становится равным 0, что означает, что высота этого поддерева остается неизменной.

Если коэффициент балансировки становится равным ± 1, высота поддерева увеличивается на единицу, и восстановление необходимо продолжать.

Если коэффициент балансировки временно становится равным ± 2, это необходимо исправить путем соответствующего поворота, после которого поддерево будет иметь ту же высоту, что и раньше (и его корень - коэффициент балансировки 0).

Требуемое время O (журнал п) для поиска плюс максимум O (журнал п) восстановление уровней (О (1) в среднем) на обратном пути к корню, поэтому операцию можно завершить за O (журнал п) время.^[10]:53

Удалить

Предварительные шаги по удалению узла описаны в разделе Дерево двоичного поиска # Удаление Здесь эффективное удаление подчиненного узла или заменяющего узла уменьшает высоту соответствующего дочернего дерева либо с 1 до 0, либо с 2 до 1, если у этого узла был дочерний узел.

Начиная с этого поддерева, необходимо проверить каждого из предков на соответствие инвариантам деревьев AVL. Это называется «повторным отслеживанием».

Поскольку при однократном удалении высота поддерева AVL не может уменьшаться более чем на единицу, временный коэффициент баланса узла будет в диапазоне от -2 до +2. Если коэффициент баланса остается в диапазоне от -1 до + 1 его можно настроить в соответствии с правилами AVL. Если оно становится равным ± 2, то поддерево не сбалансировано и его необходимо повернуть. (В отличие от вставки, когда вращение всегда уравновешивает дерево, после удаления может быть BF (Z) 0 (см. Рис. 4 и 5), так что после соответствующего одинарного или двойного вращения высота повторно сбалансированного поддерева уменьшается на один означает, что дерево должно быть снова сбалансировано на следующем более высоком уровне.) Различные случаи вращения описаны в разделе Ребалансировка.

Инвариант цикла восстановления для удаления

Высота поддерева с корнем N уменьшилась на 1. Оно уже имеет форму AVL.

Пример кода для операции удаления

1 за (Икс = родитель(N); Икс != ноль; Икс = грамм) { // Цикл (возможно, до корня) 2 грамм = родитель(Икс); // Сохраняем родительский элемент X вокруг поворота 3 // BalanceFactor (X) еще не обновлен! 4 если (N == left_child(Икс)) { // левое поддерево уменьшается 5 если (BalanceFactor(Икс) > 0) { // X тяжелый справа 6 // ===> временный BalanceFactor (X) == +2 7 // ===> требуется ребалансировка. 8 Z = right_child(Икс); // Брат N (выше на 2) 9 б = BalanceFactor(Z);10 если (б < 0) // Правый левый регистр (см. Рисунок 5)11 N = rotate_RightLeft(Икс, Z); // Двойное вращение: вправо (Z), затем влево (X)12 еще // Правый регистр справа (см. Рисунок 4)13 N = повернуть налево(Икс, Z); // Один поворот влево (X)14 // После поворота адаптируем родительскую ссылку15 } еще {16 если (BalanceFactor(Икс) == 0) {17 BalanceFactor(Икс) = +1; // Уменьшение высоты N поглощается в X.18 перемена; // Выходим из цикла19 }20 N = Икс;21 BalanceFactor(N) = 0; // Высота (N) уменьшается на 122 Продолжить;23 }24 } еще { // (N == right_child (X)): правое поддерево уменьшается25 если (BalanceFactor(Икс) < 0) { // X тяжелее слева26 // ===> временный BalanceFactor (X) == –227 // ===> требуется ребалансировка.28 Z = left_child(Икс); // Брат N (выше на 2)29 б = BalanceFactor(Z);30 если (б > 0) // Левый Правый Регистр31 N = rotate_LeftRight(Икс, Z); // Двойное вращение: влево (Z), затем вправо (X)32 еще // Левый регистр слева33 N = rotate_Right(Икс, Z); // Одиночный поворот вправо (X)34 // После поворота адаптируем родительскую ссылку35 } еще {36 если (BalanceFactor(Икс) == 0) {37 BalanceFactor(Икс) = –1; // Уменьшение высоты N поглощается в X.38 перемена; // Выходим из цикла39 }40 N = Икс;41 BalanceFactor(N) = 0; // Высота (N) уменьшается на 142 Продолжить;43 }44 }45 // После поворота адаптируем родительскую ссылку:46 // N - новый корень повернутого поддерева47 родитель(N) = грамм;48 если (грамм != ноль) {49 если (Икс == left_child(грамм))50 left_child(грамм) = N;51 еще52 right_child(грамм) = N;53 } еще54 дерево->корень = N; // N - новый корень всего дерева55 56 если (б == 0)57 перемена; // Высота не меняется: выходим из цикла58 59 // Высота (N) уменьшается на 1 (== старая высота (X) -1)60 }61 // Если (b! = 0) высота всего дерева уменьшится на 1.

Восстановление может быть остановлено, если коэффициент баланса становится равным ± 1 (он должен был быть равен 0), что означает, что высота этого поддерева остается неизменной.

Если коэффициент балансировки становится равным 0 (он должен был быть ± 1), тогда высота поддерева уменьшается на единицу, и восстановление необходимо продолжить.

Если коэффициент балансировки временно становится равным ± 2, это необходимо исправить соответствующим вращением. Это зависит от коэффициента балансировки родственного элемента Z (более высокое дочернее дерево на рис. 4), будет ли высота поддерева уменьшаться на единицу - и восстановление необходимо продолжить - или не изменится (если Z имеет коэффициент балансировки 0) и все дерево имеет AVL-форму.

Требуемое время O (журнал п) для поиска плюс максимум O (журнал п) восстановление уровней (О (1) в среднем) на обратном пути к корню, поэтому операцию можно завершить за O (журнал п) время.

Установить операции и массовые операции

В дополнение к одноэлементным операциям вставки, удаления и поиска в деревьях AVL было определено несколько операций над наборами: союз, пересечение и установить разницу. Тогда быстро масса операции по вставке или удалению могут быть реализованы на основе этих установленных функций. Эти операции над наборами полагаются на две вспомогательные операции: Расколоть и Присоединиться. Благодаря новым операциям реализация деревьев AVL может быть более эффективной и легко распараллеливаемой.^[15]

• Присоединиться: Функция Присоединиться находится на двух деревьях AVL т₁ и т₂ и ключ k вернет дерево, содержащее все элементы в т₁, т₂ а также k. Это требует k быть больше, чем все ключи в т₁ и меньше, чем все ключи в т₂. Если два дерева отличаются высотой не более одного, Присоединиться просто создайте новый узел с левым поддеревом т₁, корень k и правое поддерево т₂. В противном случае предположим, что т₁ выше чем т₂ для более чем одного (другой случай симметричен). Присоединиться следует за правым позвоночником т₁ до узла c который сбалансирован с т₂. На этом этапе новый узел с левым дочерним элементом c, корень k и правильный ребенок т₂ создан для замены c. Новый узел удовлетворяет инварианту AVL, а его высота на единицу больше, чем c. Увеличение высоты может увеличить высоту его предков, возможно, аннулируя инвариант AVL этих узлов. Это может быть исправлено либо двойным вращением, если оно недопустимо для родительского узла, либо одинарным левым вращением, если оно недопустимо выше в дереве, в обоих случаях восстанавливая высоту для любых последующих узлов-предков. Присоединиться поэтому потребуется не более двух оборотов. Стоимость этой функции - разница высот между двумя входными деревьями.

Реализация псевдокода для алгоритма соединения

функция joinRightAVL (TL, k, Тр) (l, k ', c) = выставить (TL) если (h (c) <= h (Tр) +1) T '= Узел (c, k, Tр) если (h (T ') <= h (l) +1), то возвращаться Узел (l, k ', T') иначе возвращаться rotateLeft (Узел (l, k'rotateRight (T '))) еще T '= joinRightAVL (c, k, Tр) Т= Узел (l, k ', T') если (h (T ') <= h (l) +1) возвращаться Т еще возвращаться rotateLeft (T)функция joinLeftAVL (TL, k, Тр) / * симметрично joinRightAVL * /функция соединениеL, k, Тр) если (ч (тL)> h (Tр)+1) возвращаться joinRightAVL (TL, k, Тр) если (ч (тр)> h (TL)+1) возвращаться joinLeftAVL (TL, k, Тр) возвращаться Узел (TL, k, Тр) Здесь ${displaystyle h(v)}$ узла ${displaystyle v}$ высота ${displaystyle v}$. expose (v) = (l, k, r) означает извлечь узел дерева ${displaystyle v}$левый ребенок ${displaystyle l}$, ключ узла ${displaystyle k}$, и правильный ребенок ${displaystyle r}$. Узел (l, k, r) означает создание узла левого потомка ${displaystyle l}$, ключ ${displaystyle k}$, и правый ребенок ${displaystyle r}$.

• Расколоть: Чтобы разделить дерево AVL на два меньших дерева, меньшие, чем ключ Икс, и те, которые больше ключа Икс, сначала нарисуйте путь от корня, вставив Икс в АВЛ. После этой вставки все значения меньше, чем Икс будут найдены слева от пути, и все значения больше чем Икс будет находиться справа. Применяя Присоединиться, все поддеревья на левой стороне объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх, чтобы сформировать левое дерево, а правая часть асимметрична. Цена Расколоть является ${displaystyle O(log n)}$, порядок высоты дерева.

Реализация псевдокода для алгоритма разделения
функция разделить (T, k) если (T = nil) return (nil, false, nil) (L, m, R) = выставить (T) если (k = m) return (L, истина, R) если (k возвращаться (L ', b, присоединиться (R', m, R)) если (k> m) (L ', b, R') = разделить (R, k) возвращаться (присоединиться (L, m, L '), b, R'))

Объединение двух АВЛ т₁ и т₂ представляющие наборы А и B, является AVL т что представляет А ∪ B.

Реализация псевдокода для алгоритма объединения

функция союз (т1, т2): если т1 = ноль: возвращаться т2 если т2 = ноль: возвращаться т1 т<, т> ← разделить т2 на т1.корень возвращаться соединение1.root, union (left (t1), т<), union (right (t1), т>)) Здесь, Расколоть предполагается, что он возвращает два дерева: одно содержит ключи минус его ключ ввода, а другое - большие ключи. (Алгоритм неразрушающий, но существует и деструктивная версия на месте.)

Алгоритм пересечения или разницы аналогичен, но требует Присоединиться2 вспомогательная программа, аналогичная Присоединиться но без средней клавиши. На основе новых функций для объединения, пересечения или разницы, один или несколько ключей могут быть вставлены или удалены из дерева AVL. С Расколоть звонки Присоединиться но не имеет прямого отношения к критериям балансировки деревьев AVL, такая реализация обычно называется реализация на основе соединения.

Сложность каждого из объединения, пересечения и различия равна ${displaystyle Oleft(mlog left({n over m}+1ight)ight)}$ для АВЛ размеров ${displaystyle m}$ и ${displaystyle n(geq m)}$. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или различия не зависят друг от друга, они могут быть выполнены в параллели с параллельная глубина ${displaystyle O(log mlog n)}$.^[15] Когда ${displaystyle m=1}$реализация на основе соединения имеет тот же вычислительный DAG, что и вставка и удаление одиночных элементов.

Ребалансировка

Если во время операции изменения (например, вставки, удаления) между двумя дочерними поддеревьями возникает (временная) разница в высоте более чем на единицу, родительское поддерево должно быть «повторно сбалансировано». Данные ремонтные инструменты представляют собой так называемые вращения деревьев, потому что они перемещают ключи только «вертикально», так что («горизонтальная») упорядоченная последовательность ключей полностью сохраняется (что важно для дерева двоичного поиска).^[13][14]

Пусть X будет узлом, который имеет (временный) коэффициент баланса -2 или +2. Его левое или правое поддерево было изменено. Пусть Z будет старшим ребенком. Обратите внимание, что Z находится в форме AVL на гипотеза индукции.

В случае вставки эта вставка произошла с одним из дочерних элементов Z, так что высота Z увеличилась. В случае удаления это удаление произошло с одним из дочерних элементов t₁ Z так, чтобы t₁рост, уже будучи ниже, уменьшился. (В этом случае коэффициент баланса Z может быть равен 0.)

Могут возникнуть четыре ситуации. Мы будем описывать их как Dir1 Dir2, куда Dir1 исходит из набора { оставили, верно } и Dir2 поскольку коэффициент баланса исходит из набора { лево-тяжелый = −1, сбалансированный = 0, правый тяжелый = +1 }.^[16]

Ситуация Dir1 Dir2 обозначает:

Z является дочерним элементом Dir1 своего родителя и

Z является Dir2-тяжелым, если Dir2! = Dir1

Z не является (−Dir2) -тяжелым, если Dir2 == Dir1

т.е.

	Верно-верно	=> Z - это верно	дочерний элемент своего родителя X и Z не является лево-тяжелый	(т.е. BalanceFactor (Z) ≥ 0)	(см. рисунок 4)
	Слева слева	=> Z - это оставили	дочерний элемент своего родителя X и Z не является правый тяжелый	(т.е. BalanceFactor (Z) ≤ 0)
	Правый левый	=> Z - это верно	дочерний элемент своего родителя X и Z является лево-тяжелый	(т.е. BalanceFactor (Z) = −1)	(см. рисунок 5)
	Лево право	=> Z - это оставили	дочерний элемент своего родителя X и Z является правый тяжелый	(т.е. BalanceFactor (Z) = +1)

Нарушение баланса в случае Dir1 == Dir2 устраняется простым вращением rotate _ (- Dir1) (повернуть налево на рисунке 4 соотв. его зеркало rotate_Right).

Случай Dir1! = Dir2 исправляется двойным вращением rotate _ (- Dir2) (- Dir1) == rotate_Dir1Dir2 (rotate_RightLeft на рисунке 5 соотв. его зеркало rotate_LeftRight).

Стоимость ротации, как простой, так и двойной, постоянна.

Простое вращение

На рис. 4 показана ситуация справа справа. В своей верхней половине узел X имеет два дочерних дерева с коэффициентом баланса +2. Более того, внутренний ребенок t₂₃ от Z (т.е. левый дочерний элемент, когда Z является правым дочерним элементом, или правый дочерний элемент, когда Z является левым дочерним элементом) не выше, чем его брат t₄. Это может произойти при увеличении высоты поддерева t₄ или уменьшением высоты поддерева t₁. В последнем случае также бледная ситуация, когда t₂₃ имеет ту же высоту, что и t₄ может возникнуть.

Результат левого вращения показан в нижней половине рисунка. Необходимо обновить три звена (толстые края на рисунке 4) и два коэффициента баланса.

Как показано на рисунке, до вставки листовой слой находился на уровне h + 1, временно на уровне h + 2 и после поворота снова на уровне h + 1. В случае удаления листовой слой был на уровне h + 2, где он снова находится, когда t₂₃ и т₄ были одного роста. В противном случае слой листа достигает уровня h + 1, так что высота повернутого дерева уменьшается.

Рис.4: Простое вращение
повернуть налево(Икс,Z)

Фрагмент кода простого поворота влево

Вход:	X = корень поддерева, который нужно повернуть влево
	Z = правый потомок X, Z тяжелее справа
	с высотой == Высота (LeftSubtree (Икс))+2
Результат:	новый корень ребалансированного поддерева

 1 узел *повернуть налево(узел *Икс, узел *Z) { 2     // Z на 2 больше, чем его брат 3     t23 = left_child(Z); // Внутренний дочерний элемент Z 4     right_child(Икс) = t23; 5     если (t23 != ноль) 6         родитель(t23) = Икс; 7     left_child(Z) = Икс; 8     родитель(Икс) = Z; 9     // 1-й случай, BalanceFactor (Z) == 0, происходит только при удалении, а не при вставке:10     если (BalanceFactor(Z) == 0) { // t23 был той же высоты, что и t411         BalanceFactor(Икс) = +1;   // t23 теперь выше12         BalanceFactor(Z) = –1;   // t4 теперь ниже X13     } еще { // 2-й случай происходит при вставке или удалении:14         BalanceFactor(Икс) = 0;15         BalanceFactor(Z) = 0;16     }17     возвращаться Z; // возвращаем новый корень повернутого поддерева18 }

Двойное вращение

На рисунке 5 показана ситуация справа налево. В своей верхней трети узел X имеет два дочерних дерева с коэффициентом баланса +2. Но в отличие от рисунка 4, внутренний дочерний элемент Y элемента Z выше, чем его брат t.₄. Это может произойти путем вставки самого Y или увеличения высоты одного из его поддеревьев t₂ или т₃ (с тем, что они разной высоты) или уменьшением высоты поддерева t₁. В последнем случае также может оказаться, что t₂ и т₃ одинаковой высоты.

Результат первого, правого поворота показан в средней трети рисунка. (Что касается коэффициентов баланса, это вращение отличается от других одиночных вращений AVL, потому что разница в высоте между Y и t₄ всего 1.) Результат окончательного левого вращения показан в нижней трети рисунка. Необходимо обновить пять звеньев (толстые края на рисунке 5) и три коэффициента баланса.

Как показано на рисунке, до вставки листовой слой находился на уровне h + 1, временно на уровне h + 2 и после двойного вращения снова на уровне h + 1. В случае удаления листовой слой находился на уровне h + 2, а после двойного поворота он находится на уровне h + 1, так что высота повернутого дерева уменьшается.

Рис.5: Двойное вращение rotate_RightLeft(Икс,Z)
= rotate_Right вокруг Z с последующим
повернуть налево вокруг Икс

Фрагмент кода двойного вращения вправо-влево

Вход:	X = корень поддерева, который нужно повернуть
	Z = его правый ребенок, левый тяжелый
	с высотой == Высота (LeftSubtree (Икс))+2
Результат:	новый корень ребалансированного поддерева

 1 узел *rotate_RightLeft(узел *Икс, узел *Z) { 2     // Z на 2 больше, чем его брат 3     Y = left_child(Z); // Внутренний дочерний элемент Z 4     // Y на 1 больше, чем брат 5     t3 = right_child(Y); 6     left_child(Z) = t3; 7     если (t3 != ноль) 8         родитель(t3) = Z; 9     right_child(Y) = Z;10     родитель(Z) = Y;11     t2 = left_child(Y);12     right_child(Икс) = t2;13     если (t2 != ноль)14         родитель(t2) = Икс;15     left_child(Y) = Икс;16     родитель(Икс) = Y;17     если (BalanceFactor(Y) > 0) { // t3 было больше18         BalanceFactor(Икс) = –1;  // t1 теперь выше19         BalanceFactor(Z) = 0;20     } еще21         если (BalanceFactor(Y) == 0) {22             BalanceFactor(Икс) = 0;23             BalanceFactor(Z) = 0;24         } еще {25             // t2 было больше26             BalanceFactor(Икс) = 0;27             BalanceFactor(Z) = +1;  // t4 теперь выше28         }29     BalanceFactor(Y) = 0;30     возвращаться Y; // возвращаем новый корень повернутого поддерева31 }

Сравнение с другими конструкциями

Оба дерева AVL и красно-черные (RB) деревья являются самобалансирующимися деревьями двоичного поиска, и они связаны математически. В самом деле, любое дерево АВЛ можно раскрасить в красный – черный цвет,^[17] но есть деревья RB, которые не сбалансированы по AVL. Для поддержания АВЛ соотв. Инварианты дерева РБ, повороты играют важную роль. В худшем случае, даже без поворотов, вставки или удаления AVL или RB требуют O (журнал п) проверки и / или обновления коэффициентов баланса AVL соотв. Цвета РБ. Вставки и удаления RB и вставки AVL требуют от нуля до трех хвостовой рекурсивный вращения и обкатка амортизированный О (1) время,^[18][19] таким образом, в среднем одинаково постоянный. Удаление AVL, требующее O (журнал п) вращения в худшем случае также О (1) в среднем. Деревья RB требуют хранения одного бита информации (цвета) в каждом узле, в то время как деревья AVL в основном используют два бита для коэффициента баланса, хотя при хранении в дочерних элементах достаточно одного бита со значением «ниже, чем у брата». Самая большая разница между двумя структурами данных - это их предел высоты.

Для дерева размером п ≥ 1

• высота AVL-дерева не более

  ${displaystyle {egin{array}{ll}h&leqq ;clog _{2}(n+d)+b&<;clog _{2}(n+2)+bend{array}}}$

куда ${displaystyle varphi :={ frac {1+{sqrt {5}}}{2}}approx 1.618}$ то Золотое сечение, ${displaystyle c:={ frac {1}{log _{2}varphi }}approx 1.440,}$   ${displaystyle b:={ frac {c}{2}}log _{2}5-2approx ;-0.328,}$ и ${displaystyle d:=1+{ frac {1}{varphi ^{4}{sqrt {5}}}}approx 1.065}$.

• высота дерева RB не более

  ${displaystyle {egin{array}{ll}h&leqq ;2log _{2}(n+1)end{array}}}$ .^[20]

Деревья AVL более жестко сбалансированы, чем деревья RB с асимптотический отношение AVL / RB ≈ 0,720 максимальных высот. Для вставок и удалений Бен Пфафф показывает в 79 измерениях соотношение AVL / RB между 0,677 и 1,077 с медиана ≈0,947 и среднее геометрическое ≈0.910.^[21]

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

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

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

1. Эрик Александр. "АВЛ Деревья". Архивировано 31 июля 2019 года.
2. Седжвик, Роберт (1983). "Сбалансированные деревья". Алгоритмы. Эддисон-Уэсли. п.199. ISBN  0-201-06672-6.
3. Адельсон-Вельский, Георгий; Ландис, Евгений (1962). «Алгоритм организации информации». Известия АН СССР. (на русском). 146: 263–266. английский перевод Майрон Дж. Риччи в Советская математика - Доклады, 3:1259–1263, 1962.
4. Пфафф, Бен (июнь 2004 г.). «Анализ производительности BST в системном программном обеспечении» (PDF). Стэндфордский Университет.
5. Деревья AVL не сбалансированы по весу? (что означает: деревья AVL не сбалансированы по μ?)
   Таким образом: двоичное дерево называется ${displaystyle mu }$-балансированный, с ${displaystyle 0leq mu leq { frac {1}{2}}}$, если для каждого узла ${displaystyle N}$, неравенство

   ${displaystyle { frac {1}{2}}-mu leq { frac {|N_{l}|}{|N|+1}}leq { frac {1}{2}}+mu }$

   держит и ${displaystyle mu }$ минимально с этим свойством. ${displaystyle |N|}$ это количество узлов под деревом с ${displaystyle N}$ как корень (включая корень) и ${displaystyle N_{l}}$ левый дочерний узел ${displaystyle N}$.
6. Кнут, Дональд Э. (2000). Сортировка и поиск (2-е изд., 6. полиграфическое, обновленное и перераб. Ред.). Бостон [u.a.]: Эддисон-Уэсли. п. 459. ISBN  0-201-89685-0.
7. Раджиникантх. "Дерево AVL :: Структуры данных". btechsmartclass.com. Получено 2018-03-09.
8. Кнут, Дональд Э. (2000). Сортировка и поиск (2-е изд., 6. полиграфическое, обновл. И перераб. Ред.). Бостон [u.a.]: Эддисон-Уэсли. п. 460. ISBN  0-201-89685-0.
   Кнут имеет внутренние узлы и внешние узлы, первые соответствуют узлам, несущим ключи в статье, тогда как внешние узлы Кнута (которые не несут ключ) не имеют соответствия в статье. Тем не менее внешние узлы Кнута увеличивают высоту дерева на 1 (см. Рис. 20), приращения, которого в статье не происходит. В конце статьи с понятием высоты дерево, состоящее из корня, имеет высоту только 0, так что F₀₊₂ – 1 = 1 количество его узлов.
   NB: ${displaystyle lim _{height o infty }F_{height}{sqrt {5}},varphi ^{-height}=1}$.
9. Диксит, Дж. Б. (2010). Освоение структур данных с помощью языка C. Нью-Дели, Индия: University Science Press, отпечаток Laxmi Publications Pvt. ООО ISBN  9789380386720. OCLC  939446542.
10. Брасс, Питер (2008). Расширенные структуры данных. Кембридж: Издательство Кембриджского университета. ISBN  9780511438202. OCLC  312435417.
11. Хаббард, Джон Раст (2000). Очерк теории и проблем структур данных в Java Шаума. Нью-Йорк: Макгроу-Хилл. ISBN  0071378707. OCLC  48139308.
12. Вайс, Марк Аллен. (2006). Структуры данных и алгоритм анализа в C ++ (3-е изд.). Бостон: Пирсон Эддисон-Уэсли. п. 145. ISBN  0-321-37531-9. OCLC  61278554.
13. Кнут, Дональд Э. (2000). Сортировка и поиск (2-е изд., 6. полиграфическое, обновленное и перераб. Ред.). Бостон [u.a.]: Эддисон-Уэсли. С. 458–481. ISBN  0201896850.
14. Пфафф, Бен (2004). Введение в деревья двоичного поиска и сбалансированные деревья. Free Software Foundation, Inc., стр. 107–138.
15. Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2016), «Просто присоединитесь для параллельных упорядоченных множеств», Симпозиум по параллельным алгоритмам и архитектурам, ACM, стр. 253–264, arXiv:1602.02120, Дои:10.1145/2935764.2935768, ISBN  978-1-4503-4210-0.
16. Таким образом, вращения с корпусом Сбалансированный не происходят со прошивками.
17. Пол Э. Блэк (13 апреля 2015 г.). "АВЛ дерево". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий. Получено 2016-07-02.
18. Мельхорн и Сандерс 2008, стр.165, 158 Ошибка harvnb: цель отсутствует: CITEREFMehlhornSanders2008 (помощь)
19. Динеш П. Мехта, Сартадж Сахни (Ред.) Справочник по структурам данных и приложениям 10.4.2
20. Красно-черное дерево # Доказательство асимптотических оценок
21. Бен Пфафф: Анализ производительности BST в системном программном обеспечении. Стэнфордский университет 2004 г.

дальнейшее чтение

• Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Третье издание. Аддисон-Уэсли, 1997. ISBN  0-201-89685-0. Страницы 458–475 раздела 6.2.3: Сбалансированные деревья.

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

• Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. «АВЛ Дерево». Словарь алгоритмов и структур данных.