В информатике дерево WAVL или слабое дерево AVL — это самобалансирующееся бинарное дерево поиска . Деревья WAVL названы в честь деревьев AVL , другого типа сбалансированного дерева поиска, и тесно связаны как с деревьями AVL, так и с красно-черными деревьями , которые все попадают в общую структуру сбалансированных по рангу деревьев . Как и другие сбалансированные бинарные деревья поиска, деревья WAVL могут обрабатывать операции вставки, удаления и поиска за время O (log n ) на операцию. [1] [2]
Деревья WAVL разработаны для объединения некоторых лучших свойств как деревьев AVL, так и красно-черных деревьев. Одним из преимуществ деревьев AVL по сравнению с красно-черными деревьями является их большая сбалансированность: они имеют высоту не более (для дерева с n элементами данных, где — золотое сечение ), в то время как красно-черные деревья имеют большую максимальную высоту, . Если дерево WAVL создано с использованием только вставок, без удалений, то оно имеет ту же малую границу высоты, что и дерево AVL. С другой стороны, красно-черные деревья имеют преимущество перед деревьями AVL в меньшей реструктуризации своих деревьев. В деревьях AVL каждое удаление может потребовать логарифмического числа операций поворота дерева , в то время как красно-черные деревья имеют более простые операции удаления, которые используют только постоянное число поворотов дерева. Деревья WAVL, как и красно-черные деревья, используют только постоянное число поворотов дерева, и константа даже лучше, чем для красно-черных деревьев. [1] [2]
Деревья WAVL были введены Haeupler, Sen & Tarjan (2015). Те же авторы также представили общее представление о деревьях AVL, деревьях WAVL и красно-черных деревьях как о типах сбалансированных по рангу деревьев. [2]
Различные бинарные деревья поиска имеют разные алгоритмы для вставки/удаления и алгоритмов балансировки, что затрудняет систематическое исследование. Авторы Haeupler, Sen & Tarjan (2015) вводят структуру сбалансированных деревьев ранга для унификации изучения бинарных деревьев поиска, определяя двоичное дерево ранга, и каждое двоичное дерево поиска следует определенным ограничениям, применяемым к функции ранга. Обратите внимание, что структура не определяет алгоритмы, в которых эти деревья реализованы.
Ранговое двоичное дерево — это двоичное дерево, в котором каждый узел x связан с рангом r(x). По соглашению пустой узел имеет ранг -1. Для узла x, который не является корнем, разность рангов равна , и такой узел называется i-потомком, если разность рангов равна i. Узел имеет тип , если разность рангов его левого и правого потомков равна i и j (без учета порядка).
При этом мы можем определить дополнительные правила, соответствующие различным деревьям:
Пока все эти правила симметричны для левого узла и правого узла. Нарушение таких симметрий порождает другие правила:
Слабое дерево AVL определяется слабым правилом AVL:
Обратите внимание, что слабое дерево AVL обобщает дерево AVL, допуская узел типа 2,2. Простое доказательство показывает, что слабое дерево AVL можно раскрасить таким образом, чтобы оно представляло собой красно-черное дерево. Таким образом, в некотором смысле слабое дерево AVL объединяет свойства дерева AVL и красно-черного дерева.
Как и в случае с бинарными деревьями поиска в более общем смысле, дерево WAVL состоит из набора узлов двух типов: внутренних узлов и внешних узлов. Внутренний узел хранит элемент данных и связан со своим родителем (за исключением назначенного корневого узла, у которого нет родителя) и ровно с двумя дочерними узлами в дереве, левым дочерним узлом и правым дочерним узлом. Внешний узел не несет никаких данных и имеет ссылку только на своего родителя в дереве. Эти узлы организованы так, чтобы сформировать бинарное дерево, так что для любого внутреннего узла x родителями левого и правого дочерних узлов x являются сами x . Внешние узлы образуют листья дерева. [3] Элементы данных организованы в дереве таким образом, что симметричный обход дерева перечисляет элементы данных в отсортированном порядке. [4]
Деревья WAVL отличаются от других типов двоичных деревьев поиска тем, что они используют ранги . Это числа, связанные с каждым узлом, которые обеспечивают приближение расстояния от узла до его самого дальнего потомка-листа. В отличие от деревьев AVL, где ранги определяются как такие же, как высоты узлов, ранги не всегда равны высотам в деревьях WAVL. Разность рангов узла x определяется как разность между рангом родителя x и рангом x. Ранги должны подчиняться следующим свойствам: [1] [2]
Поиск ключа 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 ) .
Кроме того, после нахождения узла для вставки и удаления амортизированная сложность операций реструктуризации дерева постоянна. Добавление или удаление самого узла занимает постоянное время, количество поворотов всегда не более чем постоянно, и можно показать, что общее количество изменений ранга в узлах линейно зависит от количества как вставок, так и удалений.
Деревья 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]
Красно -черное дерево — это сбалансированное бинарное дерево поиска, в котором каждый узел имеет цвет (красный или черный), удовлетворяющий следующим свойствам:
Красно-черные деревья можно эквивалентно определить в терминах системы рангов, хранящихся в узлах, удовлетворяющих следующим требованиям (отличным от требований к рангам в деревьях WAVL):
Эквивалентность между определениями на основе цвета и ранга можно увидеть, в одном направлении, раскрасив узел в черный цвет, если его родитель имеет больший ранг, и в красный цвет, если его родитель имеет равный ранг. В другом направлении цвета можно преобразовать в ранги, сделав ранг черного узла равным числу черных узлов на любом пути к внешнему узлу, и сделав ранг красного узла равным его родителю. [8]
Ранги узлов в дереве WAVL можно преобразовать в систему рангов узлов, удовлетворяющую требованиям для красно-черных деревьев, разделив каждый ранг на два и округлив до ближайшего целого числа. [9] Благодаря этому преобразованию для каждого дерева WAVL существует допустимое красно-черное дерево с той же структурой. Поскольку красно-черные деревья имеют максимальную высоту , то же самое верно и для деревьев WAVL. [1] [2] Однако существуют красно-черные деревья, которым нельзя задать допустимую функцию ранга дерева WAVL. [2]
Несмотря на то, что с точки зрения их древовидных структур деревья WAVL являются особыми случаями красно-черных деревьев, их операции обновления отличаются. Повороты деревьев, используемые в операциях обновления деревьев WAVL, могут вносить изменения, которые не были бы разрешены в красно-черном дереве, поскольку они фактически вызвали бы перекраску больших поддеревьев красно-черного дерева, а не вносили бы изменения цвета только на одном пути в дереве. [2] Это позволяет деревьям WAVL выполнять меньше поворотов деревьев на удаление, в худшем случае, чем красно-черные деревья. [1] [2]
