WAVL-дерево

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

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

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

Деревья WAVL были представлены Хэуплером, Сеном и Тарджаном (2015) . Те же авторы также представили общий взгляд на деревья AVL, WAVL и красно-черные деревья как на типы деревьев со сбалансированным рангом.

Структура сбалансированных деревьев по рангам

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

Бинарное дерево ранга — это бинарное дерево, в котором каждому узлу x сопоставлен ранг r(x). По соглашению пустой узел имеет ранг -1. Для узла x, который не является корнем, разница в рангах равна $r(p(x))-r(x)$, и такой узел называется i-дочерним, если разница рангов равна i. Узел имеет тип $i,j$ если разница в рангах его левого и правого дочерних элементов равна i и 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 . Внешние узлы образуют листья дерева. Элементы данных располагаются в дереве таким образом, что при неупорядоченном обходе дерева элементы данных перечисляются в отсортированном порядке.

Что отличает деревья WAVL от других типов двоичных деревьев поиска, так это использование в них рангов . Это числа, связанные с каждым узлом, которые дают приблизительное расстояние от узла до его самого дальнего потомка-листа. В отличие от деревьев AVL, где ранги определяются как высоты узлов, ранги не всегда равны высотам в деревьях WAVL. Разница в рангах узла x определяется как разница между рангом родительского узла x и рангом x. Ряды должны соответствовать следующим свойствам:

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

Операции

Идет поиск

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

Если поиск останавливается на внутреннем узле, ключ k найден. Если вместо этого поиск останавливается на внешнем узле, то позиция, куда был бы вставлен k (если бы он был вставлен), найдена.

Вставка

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

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

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

Таким образом, в целом процедура вставки состоит из поиска, создания постоянного числа новых узлов, логарифмического числа изменений ранга и постоянного количества вращений дерева.

Удаление

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

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

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

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

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

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

Дерево Фибоначчи с рангами

Дерево Фибоначчи с рангами после удаления

Вычислительная сложность

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

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

Связанные структуры

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

Деревья АВЛ

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

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

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

Красно-черные деревья

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

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

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

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

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

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

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