Почему мы не добавляем черный узел вместо красного узла при вставке красного черного дерева?

Question

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

Answer 1

Я думаю, что это связано с правилами красных черных деревьев...

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

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

                       B(10)
             R(5)                    B(15) 
    B(1)              B(6)       B(NIL)   B(NIL)
B(NIL) B(NIL)    B(NIL) B(NIL)

Вы заметите, что на каждом пути есть 3 черных узла. Если вы попытаетесь вставить новый узел 16 младше 15 лет в качестве черного узла (имейте в виду, что вы добавляете 2 черных ноля под узлом, который вы добавляете), этот путь станет длиннее (4). Это было бы неправильно, как это:

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     B(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)

Чтобы все правила выполнялись, вам нужно вставить красный узел, и количество черных узлов на каждом пути останется равным.

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     R(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)