Поведение операции вставки красно-черного дерева для отсортированных значений

Question

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

Позвольте мне проиллюстрировать это набором данных [10, 5, 2].

Итак, Initial 10 будет вставлен и будет корнем дерева, а его цвет будет черным. 10

Далее мы добавим 5 под корнем 10. Цвет 5 будет красным (На данный момент он не нарушает ни одно из свойств).

Теперь мы добавим добавление 2. После добавления дерево будет выглядеть так: Добавление 2(цвет которого красный) нарушит правило, запрещающее красного ребенка под красным родителем. В красно-черном дереве есть 3 случая:- Все три случая предполагают, что у parentOf(newInsertedNode) есть одноуровневый элемент. Но в моем случае у parentOf(2) = 5 нет родного брата. Итак, как этот сценарий будет рассматриваться в алгоритме Красно-черного дерева.

Answer 1

Специфика красно-черных деревьев может немного отличаться в зависимости от статьи / книги / реализации.

Тем не менее, есть очень распространенный вариант, используемый Введение в алгоритмы (CLRS). В этом варианте есть специальные NIL дети. NIL child содержит специальный ключ "Null", указывающий, что это просто лист.

Инварианты для деревьев RB:

1. Каждый узел красный или черный.
2. Корень черный.
3. Каждый лист (NIL) черный.
4. Если узел красный, то оба его потомка черные.
5. Для каждого узла все простые пути от узла до листьев-потомков содержат одинаковое количество черных узлов

Отметим, в частности, инвариант 3 - NIL узлы черные.

---

Используя этот общий вариант, ваше дерево RB имеет 4 дополнительных узла:

1. правильный ребенок 10

2. Правильный ребенок 5

3. Левые и правые дети 2 лет

Правильный ребенок 5 лет - это брат, которого вам не хватает.