Рубрики

Красно-Черное Дерево | Комплект 2 (Вставка)

В предыдущем посте мы обсуждали введение в красно-черные деревья. В этом посте вставка обсуждается.

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

1) Перекраска
2) Вращение

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

Цвет узла NULL считается ЧЕРНЫМ.

Позвольте x быть недавно вставленным узлом.
1) Выполните стандартную вставку BST и сделайте цвет вновь вставленных узлов красным.

2) Если x — корень, измените цвет x на ЧЕРНЫЙ (высота черного дерева целиком увеличивается на 1).

3) Выполните следующие действия, если цвет родительского элемента x не черный, а x не является корневым.
…. а) Если дядя х красный ( красный родитель должен быть черным из свойства 4 )
……. (I) Измените цвет родителя и дяди на ЧЕРНЫЙ.
…… .. (ii) цвет прародителя как красный.
…… .. (iii) Измените прародителя x = x, повторите шаги 2 и 3 для нового x.

…. б) Если дядя х черный , то может быть четыре конфигурации для х, родителя х ( р ) и прародителя х ( г ) (это похоже на дерево AVL )
…… .. i) Левый левый регистр (p — левый потомок g, а x — левый потомок p)
…… .. б) Левый Правый случай (р левый ребенок г и х прав ребенка р)
…… .. iii) Правый правый случай (Зеркало случая i)
…… .. iv) Правый левый кейс (зеркало кейса ii)

Ниже приведены операции, которые должны быть выполнены в четырех случаях, когда дядя ЧЕРНЫЙ.

Все четыре случая, когда дядя ЧЕРНЫЙ

Левый левый корпус (см. G, p и x)

Левый и правый регистр (см. G, p и x)

Правый правый регистр (см. G, p и x)

Правый левый регистр (см. G, p и x)

Примеры вставки

Упражнение:
Вставьте 2, 6 и 13 ниже дерева.

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

Красно-Черное Дерево | Набор 3 (Удалить)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Красно-Черное Дерево | Комплект 2 (Вставка)

0.00 (0%) 0 votes