Вставка красное черное дерево
Я вставил узел 36 в красное черное дерево, и получилось следующее красное черное дерево:
моя проблема в том, как обрабатывать двойной красный в этом особом случае? это случай 2 или 3?
1 ответ
Основанный на свойствах и случаях Википедии...
36 будет вставлен в случае 5, вращающийся 22 оставил.
Родитель Р красный, но дядя черный или нет.
Википедия просто говорит "дядя черный", но, посмотрев на код, вы увидите, что этот случай срабатывает.
Обратите внимание, что дерево без 36 уже был недействительным, потому что свойство 5 (все пути от любого данного узла до его конечных узлов содержат одинаковое количество черных узлов) не сохраняется:
- От 20 до 15 содержит 1 черный узел
- 20-30 содержит 2 черных узла
Предполагая, что порядок вставки 20, 15, 22, 30, 36...
Все узлы вставлены как красные.
22 будет вставлен в случае 2.
Родитель черный.
30 будет вставлен в случае 3, делая 22 а также 15 черный и 20 красный.
Родитель и дядя красные; оба перекрашиваются в черный цвет, а дедушка становится красным.
36 будет вставлен в случае 5, вращающийся 22 оставил.
Родитель Р красный, но дядя черный или нет.
22 не иметь левого ребенка
следовательно..
Случай 1: Реструктуризация
мы оставим вращение
30 -> корень "черный"
22 -> левый ребенок "красный"
36-> правый ребенок "красный"