Дерево WAVL

Дерево WAVL
Тип	Дерево
Изобретенный	2009
Изобретено	Бернхард Хёплер, Сиддхартха Сен и Роберт Э. Тарьян
Временная сложность в нотации «большое О» Операция Средний Худший случай Поиск ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Вставлять ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Удалить ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Сложность пространства Космос ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

В информатике дерево WAVL или слабое дерево AVL — это самобалансирующееся бинарное дерево поиска . Деревья WAVL названы в честь деревьев AVL , другого типа сбалансированного дерева поиска, и тесно связаны как с деревьями AVL, так и с красно-черными деревьями , которые все попадают в общую структуру сбалансированных по рангу деревьев . Как и другие сбалансированные бинарные деревья поиска, деревья WAVL могут обрабатывать операции вставки, удаления и поиска за время O (log n ) на операцию. ^{[1] [2]}

Деревья WAVL разработаны для объединения некоторых лучших свойств как деревьев AVL, так и красно-черных деревьев. Одним из преимуществ деревьев AVL по сравнению с красно-черными деревьями является их большая сбалансированность: они имеют высоту не более (для дерева с n элементами данных, где — золотое сечение ), в то время как красно-черные деревья имеют большую максимальную высоту, . Если дерево WAVL создано с использованием только вставок, без удалений, то оно имеет ту же малую границу высоты, что и дерево AVL. С другой стороны, красно-черные деревья имеют преимущество перед деревьями AVL в меньшей реструктуризации своих деревьев. В деревьях AVL каждое удаление может потребовать логарифмического числа операций поворота дерева , в то время как красно-черные деревья имеют более простые операции удаления, которые используют только постоянное число поворотов дерева. Деревья WAVL, как и красно-черные деревья, используют только постоянное число поворотов дерева, и константа даже лучше, чем для красно-черных деревьев. ^{[1] [2]}${\displaystyle \log _{\varphi }n\приблизительно 1,44\log _{2}n}$${\displaystyle \varphi}$${\displaystyle 2\log _{2}n}$

Деревья WAVL были введены Haeupler, Sen & Tarjan (2015). Те же авторы также представили общее представление о деревьях AVL, деревьях WAVL и красно-черных деревьях как о типах сбалансированных по рангу деревьев. ^[2]

Различные бинарные деревья поиска имеют разные алгоритмы для вставки/удаления и алгоритмов балансировки, что затрудняет систематическое исследование. Авторы Haeupler, Sen & Tarjan (2015) вводят структуру сбалансированных деревьев ранга для унификации изучения бинарных деревьев поиска, определяя двоичное дерево ранга, и каждое двоичное дерево поиска следует определенным ограничениям, применяемым к функции ранга. Обратите внимание, что структура не определяет алгоритмы, в которых эти деревья реализованы.

Ранговое двоичное дерево — это двоичное дерево, в котором каждый узел x связан с рангом r(x). По соглашению пустой узел имеет ранг -1. Для узла x, который не является корнем, разность рангов равна , и такой узел называется i-потомком, если разность рангов равна i. Узел имеет тип , если разность рангов его левого и правого потомков равна i и j (без учета порядка).${\displaystyle r(p(x))-r(x)}$${\displaystyle я,j}$

При этом мы можем определить дополнительные правила, соответствующие различным деревьям:

• Правило AVL, которое соответствует дереву AVL : каждый узел имеет тип 1,1 или 1,2.
• Правило 2-3, которое соответствует бинаризированному дереву 2-3: каждый узел имеет тип 0,1 или 1,1, и ни один родительский узел 0-дочернего узла не является 0-дочерним узлом.
• Правило «красный-черный», которое соответствует дереву «красный-черный» : все различия рангов равны 0 или 1, и ни один родитель 0-дочернего элемента не является 0-дочерним элементом. Обратите внимание, что правило «красный-черный» обобщает правило 2-3, допуская узел типа 0,0.

Пока все эти правила симметричны для левого узла и правого узла. Нарушение таких симметрий порождает другие правила:

• Правило двух-трех с правым уклоном, которое соответствует бинаризированному дереву 2-3 с правым уклоном: каждый узел имеет номер 1,1 или 0,1, ни один родительский узел 0-дочернего узла не является 0-дочерним узлом, и ни одного 0-дочернего узла не осталось.
• Правило двух-трех с левым уклоном, которое соответствует бинаризированному дереву 2-3 с левым уклоном: каждый узел имеет номер 1,1 или 0,1, ни один родительский элемент 0-дочернего элемента не является 0-дочерним элементом, и ни один 0-дочерний элемент не является правым.
• Правило правого уклона «красно-черного», которое соответствует дереву левого уклона «красно-черного»: ни один родительский узел 0-дочернего узла не является 0-дочерним узлом, и ни один 0-дочерний узел 0,1-узла не остается.
• Правило левостороннего красно-черного, которое соответствует левостороннему красно-черному дереву : все разности рангов равны 0 или 1, ни один родительский узел 0-дочернего узла не является 0-дочерним узлом, и ни один 0-дочерний узел 0,1-узла не является правым.

Слабое дерево AVL определяется слабым правилом AVL:

• Слабое правило AVL: все различия рангов равны 1 или 2, а все конечные узлы имеют ранг 0.

Обратите внимание, что слабое дерево AVL обобщает дерево AVL, допуская узел типа 2,2. Простое доказательство показывает, что слабое дерево AVL можно раскрасить таким образом, чтобы оно представляло собой красно-черное дерево. Таким образом, в некотором смысле слабое дерево AVL объединяет свойства дерева AVL и красно-черного дерева.

Как и в случае с бинарными деревьями поиска в более общем смысле, дерево WAVL состоит из набора узлов двух типов: внутренних узлов и внешних узлов. Внутренний узел хранит элемент данных и связан со своим родителем (за исключением назначенного корневого узла, у которого нет родителя) и ровно с двумя дочерними узлами в дереве, левым дочерним узлом и правым дочерним узлом. Внешний узел не несет никаких данных и имеет ссылку только на своего родителя в дереве. Эти узлы организованы так, чтобы сформировать бинарное дерево, так что для любого внутреннего узла x родителями левого и правого дочерних узлов x являются сами x . Внешние узлы образуют листья дерева. ^[3] Элементы данных организованы в дереве таким образом, что симметричный обход дерева перечисляет элементы данных в отсортированном порядке. ^[4]

Деревья WAVL отличаются от других типов двоичных деревьев поиска тем, что они используют ранги . Это числа, связанные с каждым узлом, которые обеспечивают приближение расстояния от узла до его самого дальнего потомка-листа. В отличие от деревьев AVL, где ранги определяются как такие же, как высоты узлов, ранги не всегда равны высотам в деревьях WAVL. Разность рангов узла x определяется как разность между рангом родителя x и рангом x. Ранги должны подчиняться следующим свойствам: ^{[1] [2]}

• Свойство внешнего узла: каждый внешний узел имеет ранг 0 ^[5]
• Свойство ранговой разницы: если некорневой узел имеет ранг r , то ранг его родителя должен быть либо r + 1 , либо r + 2. Другими словами, ранговая разница для любого некорневого узла равна 1 или 2. ^[1]
• Свойство внутреннего узла: внутренний узел с двумя внешними дочерними узлами должен иметь ранг ровно 1.

Поиск ключа k в дереве WAVL во многом такой же, как и в любой сбалансированной структуре данных двоичного дерева поиска. Начинается с корня дерева, а затем многократно сравнивается k с элементом данных, хранящимся в каждом узле на пути от корня, следуя по пути к левому потомку узла, когда k меньше значения в узле, или вместо этого следуя по пути к правому потомку, когда k больше значения в узле. Когда достигается узел со значением, равным k , или достигается внешний узел, поиск останавливается. ^[6]

Если поиск останавливается на внутреннем узле, то ключ k найден. Если же поиск останавливается на внешнем узле, то позиция, в которую должен быть вставлен k (если он был вставлен), найдена. ^[6]

Вставка внутреннего узла с ключом k в дерево WAVL требует поиска k в дереве, заканчивающегося на внешнем узле, затем замены этого внешнего узла новым внутренним узлом с двумя внешними потомками и, наконец, повторной балансировки дерева. Шаг повторной балансировки может быть выполнен как сверху вниз, так и снизу вверх, ^[2], но версия повторной балансировки снизу вверх наиболее точно соответствует деревьям AVL. ^{[1] [2]}

Ребалансировка снизу вверх начинается с рассмотрения разницы рангов между узлом (вначале это был только что вставленный узел) и его родителем. Если родителя нет, баланс восстанавливается. До начала вставки разница рангов между родителем и узлом была 1 или 2, но эта разница была уменьшена на 1, поскольку поддерево с корнем в узле стало выше. Если новая разница рангов между родителем и узлом равна 1, баланс восстанавливается. В противном случае, если родственный узел, другой дочерний узел родителя, имеет разницу рангов 1 с родителем, повысьте родителя — увеличьте его ранг, увеличив разницу рангов между ним и каждым из его дочерних узлов — и продолжайте ребалансировку со старым родителем в качестве нового узла.

Наконец, при разнице рангов 0 и 2 для узла и родственного элемента один или два поворота дерева с соответствующими корректировками разности рангов могут восстановить баланс. Промежуточный дочерний элемент узла — это тот, у которого ключ находится между ключами узла и родителя. Если разность рангов для этого дочернего элемента и узла равна 2, выполните поворот, чтобы переместить узел вверх по дереву, а родителя вниз, затем понизьте родительский элемент — уменьшите его ранг, отрегулировав разность рангов вокруг него — и баланс будет восстановлен. В противном случае выполните поворот, чтобы переместить дочерний элемент вверх, а узел вниз, затем снова выполните поворот, чтобы переместить дочерний элемент вверх, а родителя вниз. Повысьте дочерний элемент, понизьте узел и родителя, и баланс будет восстановлен.

Таким образом, в целом процедура вставки состоит из поиска, создания постоянного числа новых узлов, логарифмического числа изменений ранга и постоянного числа поворотов дерева. ^{[1] [2]}

Удаление внутреннего узла из дерева WAVL начинается с обычного удаления бинарного дерева поиска . Для внутреннего узла без внешнего потомка это означает поиск его преемника в дереве, замену узла его преемником и последующее удаление узла из его новой позиции в дереве, где его левый потомок обязательно является внешним узлом. Чтобы удалить внутренний узел с внешним потомком, замените узел другим потомком.

Перебалансировка снизу вверх начинается с рассмотрения разницы рангов между узлом (первоначально узлом, который заменил удаленный узел) и его родителем. Если родителя нет, баланс восстанавливается. До начала удаления разница рангов между родителем и узлом была 1 или 2, но эта разница была увеличена на 1, поскольку поддерево с корнем в узле сократилось. Если у родителя теперь есть два внешних потомка, свойство внутреннего узла нарушается, поскольку родитель имеет ранг 2. Родитель должен быть понижен, и перебалансировка продолжается с родителем в качестве узла, который является корнем слишком короткого поддерева.

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

Наконец, при разнице рангов 3 и 1 для узла и брата, и при наличии у брата или сестры ребенка с разницей рангов 1, один или два поворота дерева с соответствующими корректировками разниц рангов могут восстановить баланс. Определите детей брата или сестры как племянницу и племянника, где ключ племянницы лежит между ключами родителя и брата или сестры, а ключ племянника — нет. Если разность рангов между братом или сестрой и племянником равна 1, выполните поворот, чтобы переместить брата или сестру вверх, а родителя вниз, повысьте брата или сестру и понизьте родителя один раз, по крайней мере, и дважды, если необходимо, чтобы избежать нарушения свойства внутреннего узла. В противном случае, если разница в рангах между братом или сестрой и племянником равна 1, выполните поворот, чтобы переместить племянницу вверх, а брата или сестру вниз, выполните повторный поворот, чтобы переместить племянницу вверх, а родителя вниз, повысьте племянницу дважды, понизьте брата или сестру один раз и понизьте родителя дважды.

В целом удаление состоит из поиска вниз для нахождения узла с внешним потомком, удаления постоянного числа новых узлов, логарифмического числа изменений ранга и постоянного числа поворотов дерева.[1][2]

Стоит сравнить результат удаления, которое вызвало бы повороты на нескольких уровнях в дереве AVL, с поворотом и изменениями ранга, выполненными в дереве WAVL. На втором изображении узел со значением 12 был удален, после чего последовал поворот вправо и присвоение всем внешним узлам ранга ноль.

Каждый поиск, вставка или удаление в дереве WAVL включает в себя следование одному пути в дереве и выполнение постоянного числа шагов для каждого узла в пути. В дереве WAVL с n элементами, которое подверглось только вставкам, максимальная длина пути составляет . Если могли произойти как вставки, так и удаления, максимальная длина пути составляет . Следовательно, в любом случае наихудшее время для каждого поиска, вставки или удаления в дереве WAVL с n элементами данных составляет O (log n ) .${\displaystyle \log _{\varphi }n\приблизительно 1,44\log _{2}n}$${\displaystyle 2\log _{2}n}$

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

Деревья WAVL тесно связаны как с деревьями AVL , так и с красно-черными деревьями . Каждое дерево AVL может иметь ранги, назначенные его узлам таким образом, что оно превращается в дерево WAVL. И каждое дерево WAVL может иметь свои узлы, окрашенные в красный и черный цвет (и его ранги переназначенные) таким образом, что оно превращается в красно-черное дерево. Однако некоторые деревья WAVL не происходят из деревьев AVL таким образом, а некоторые красно-черные деревья не происходят из деревьев WAVL таким образом.

Дерево AVL — это своего рода сбалансированное двоичное дерево поиска, в котором два дочерних узла каждого внутреннего узла должны иметь высоты, отличающиеся не более чем на единицу. ^[7] Высота внешнего узла равна нулю, а высота любого внутреннего узла всегда равна единице плюс максимальная из высот его двух дочерних узлов. Таким образом, функция высоты дерева AVL подчиняется ограничениям дерева WAVL, и мы можем преобразовать любое дерево AVL в дерево WAVL, используя высоту каждого узла в качестве его ранга. ^{[1] [2]}

Ключевое различие между деревом AVL и деревом WAVL возникает, когда узел имеет двух потомков с одинаковым рангом или высотой. В дереве AVL, если узел x имеет двух потомков одинаковой высоты h , то высота x должна быть ровно h + 1. Напротив, в дереве WAVL, если узел x имеет двух потомков одинакового ранга r , то ранг x может быть либо r + 1 , либо r + 2. Это связано с тем, что ранг не строго равен высоте в дереве WAVL. Эта большая гибкость в рангах также приводит к большей гибкости в структурах: некоторые деревья WAVL не могут быть преобразованы в деревья AVL даже путем изменения их рангов, поскольку они включают узлы, высоты потомков которых отличаются более чем на единицу. ^[2] Однако можно сказать, что все деревья AVL являются деревьями WAVL. Деревья AVL являются деревьями WAVL без типа узла, который имеет обоих потомков с разницей рангов 2. ^[1]

Если дерево WAVL создано только с помощью операций вставки, то его структура будет такой же, как структура дерева AVL, созданного той же последовательностью вставки, а его ранги будут такими же, как ранги соответствующего дерева AVL. Только посредством операций удаления дерево WAVL может стать отличным от дерева AVL. В частности, это означает, что дерево WAVL, созданное только с помощью вставок, имеет высоту не более . ^[2]${\displaystyle \log _{\varphi }n\приблизительно 1,44\log _{2}n}$

Красно -черное дерево — это сбалансированное бинарное дерево поиска, в котором каждый узел имеет цвет (красный или черный), удовлетворяющий следующим свойствам:

• Внешние узлы черные.
• Если внутренний узел красный, то оба его дочерних узла черные.
• Все пути от корня до внешнего узла имеют одинаковое количество черных узлов.

Красно-черные деревья можно эквивалентно определить в терминах системы рангов, хранящихся в узлах, удовлетворяющих следующим требованиям (отличным от требований к рангам в деревьях WAVL):

• Ранг внешнего узла всегда равен 0, а ранг его родителя всегда равен 1.
• Ранг любого некорневого узла равен либо рангу его родителя, либо рангу его родителя минус 1.
• Никакие два последовательных ребра на любом пути «корень-лист» не имеют разности рангов 0.

Эквивалентность между определениями на основе цвета и ранга можно увидеть, в одном направлении, раскрасив узел в черный цвет, если его родитель имеет больший ранг, и в красный цвет, если его родитель имеет равный ранг. В другом направлении цвета можно преобразовать в ранги, сделав ранг черного узла равным числу черных узлов на любом пути к внешнему узлу, и сделав ранг красного узла равным его родителю. ^[8]

Ранги узлов в дереве WAVL можно преобразовать в систему рангов узлов, удовлетворяющую требованиям для красно-черных деревьев, разделив каждый ранг на два и округлив до ближайшего целого числа. ^[9] Благодаря этому преобразованию для каждого дерева WAVL существует допустимое красно-черное дерево с той же структурой. Поскольку красно-черные деревья имеют максимальную высоту , то же самое верно и для деревьев WAVL. ^{[1] [2]} Однако существуют красно-черные деревья, которым нельзя задать допустимую функцию ранга дерева WAVL. ^[2]${\displaystyle 2\log _{2}n}$

Несмотря на то, что с точки зрения их древовидных структур деревья WAVL являются особыми случаями красно-черных деревьев, их операции обновления отличаются. Повороты деревьев, используемые в операциях обновления деревьев WAVL, могут вносить изменения, которые не были бы разрешены в красно-черном дереве, поскольку они фактически вызвали бы перекраску больших поддеревьев красно-черного дерева, а не вносили бы изменения цвета только на одном пути в дереве. ^[2] Это позволяет деревьям WAVL выполнять меньше поворотов деревьев на удаление, в худшем случае, чем красно-черные деревья. ^{[1] [2]}