Удаление узла из полностью черного красного черного дерева

Удаление узла «0» в вашем дереве на самом деле самый сложный случай. Давайте шаг за шагом следуем описанию из Википедии:

Мы используем метку M для обозначения удаляемого узла; C будет обозначать выбранного дочернего элемента M, который мы также будем называть «его дочерним элементом». Если у M есть неконечный дочерний элемент, назовите его дочерним элементом C; в противном случае выберите любой лист в качестве его дочернего элемента, C.

Итак, в этом случае M — это ваш узел «0», который будет удален, а C — любой из его дочерних элементов NIL (листья, которые всегда равны NIL). Просто напомню, что ваше исходное дерево - после вашего красивого ascii-арта:

                     3(B)
                 /          \
                /            \
               1(B)          5(B)
             /     \        /    \
            /       \      /      \
           0(B)     2(B) 4(B)     6(B)

Таким образом, M равно «0», и обратите внимание, что C (лист NIL) здесь не закрашен. Википедия следует:

Сложный случай, когда и M, и C черные (это наш случай).... На приведенных ниже диаграммах мы также будем использовать P для нового родителя N (старого родителя M), SL для Левый дочерний элемент S и SR для правого дочернего элемента S.

Итак, P — это «1», а S — это «2», все узлы черные. Затем вы следуете описаниям случаев. Вы пропускаете случай 1, так как «0» не является корневым. Вы пропускаете случай 2, так как «2» не красный. Случай 3 соответствует:

Случай 3: дети P, S и S черные. В этом случае мы просто перекрашиваем S в красный цвет. В результате все пути, проходящие через S, а это в точности те пути, которые не проходят через N, имеют на одну черную вершину меньше. Поскольку удаление исходного родителя N сделало все пути, проходящие через N, на один черный узел меньше, это выравнивает ситуацию. Однако все пути через P теперь имеют на один черный узел меньше, чем пути, не проходящие через P, поэтому свойство 5 (все пути от любого заданного узла к его листовым узлам содержат одинаковое количество черных узлов) по-прежнему нарушается. Чтобы исправить это, мы выполняем процедуру ребалансировки на P, начиная со случая 1.

Итак, в этот момент вы удаляете «0» и перекрашиваете S = «2» в красный цвет:

                     3(B)
                 /          \
                /            \
               1(B)          5(B)
                   \        /    \
                    \      /      \
                    2(R) 4(B)     6(B)

Затем, следуя описанию, вы переходите к варианту 1, но на этот раз с его родительским узлом P (= "1"), замененным на N. Но N = "1" не является корнем, поэтому вы переходите к варианту 2. S = " 5" не красный, поэтому мы снова переходим к случаю 3. И здесь мы перекрашиваем S = "5" в красный цвет:

                     3(B)
                 /          \
                /            \
               1(B)          5(R)
                   \        /    \
                    \      /      \
                    2(R) 4(B)     6(B)

Затем мы должны снова перейти к случаю 1, на этот раз заменив P = «3» на N. N = "3" и мы видим, что это корень, и так готово! Дерево сбалансировано!