Балансировка поворотами АВЛ-деревьев

В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает разбалансировка поддерева. Для выправления ситуации применяются повороты вокруг тех или иных узлов дерева.

См. вопрос про вставку узлов, там всё есть

Оценка сбалансированных деревьев

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

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

Из формулы, приведенной в начале этого вопроса, высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших n имеет место оценка 1,04log₂n. Таким образом, выполнение основных операций требует порядка log₂n сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые 2 включения и на каждые 5 исключений.

Красно-чёрные деревья и их свойства

Красно-черное дерево – это еще одна форма сбалансированного бинарного поискового дерева. Время поиска, вставки или удаления узла для красно-черного дерева является логарифмической функцией от числа узлов.

Данный тип деревьев отличается от других реализаций следующими свойствами:

- каждый узел ассоциируется с определенным цветом - красным или черным;

- корневой узел может быть любого цвета;

- красные узлы могут иметь только черные дочерние узлы;

- все пути от узла до любого листа, расположенного ниже в дереве, содержат одно и то же количество черных узлов.

Высота красно-черного дерева, состоящего из N узлов, лежит в диапазоне от двоичного логарифма log(N+1) до 2 * log(N+1).

Варианты вставки узла в красно-чёрное дерево

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

Для упрощения алгоритма предполагается, что листья (узлы, не имеющие потомков) имеют черный цвет.

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

- происходит изменение цвета;

- требуется сделать один поворот;

- требуется сделать двойной поворот.

Для этого в памяти кроме текущего узла нужно хранить еще три уровня дерева: «родителя», «деда» и «прадеда» текущего узла.

 

Варианты удаления узла из красно-чёрного дерева

При удалении узла из цветного дерева цвет родительского узла не изменяется. Удаление красного узла не влечет никаких последствий, коллизию может вызвать только удаление узла черного цвета. Поэтому при удалении черного узла для обеспечения целостности дерева необходимо использовать различные операции: простую смену цвета (если это возможно) или одну или несколько ротаций. Ниже представлены 4 ситуации, возможных при удалении черного узла.

Если при удалении черного узла, его «брат» (узел, находящийся на том же уровне, что и удаляемый) и все их четыре потомка имеют черный цвет (это вариант I на рисунке 2), то выполняется изменение цвета.

 Если «брат» удаляемого узла окрашен в красный цвет, то производится ротация, изображенная на варианте II.

 Если удаляемый узел и его «брат» черного цвета, а правый потомок «брата» - красного, то выполняется двойная ротация, изображенная на варианте 4.

 Если левый потомок «брата» красного, то выполняется одиночная ротация, как в пятом варианте.