Красные Черные Деревья - Так как у каждого листа есть два нулевых ребенка, зачем даже звонить этим черным?

Question

Я ничего не наблюдал, кроме лекций CS о красных черных деревьях, и каждый, когда подсчитывает черную высоту дерева, считает NULL Узлы черными. Зачем даже беспокоиться? Например, следующее дерево:

Если бы я спросил вас, что черная высота этого дерева, вы сказали бы три. Но, если я сбрил все узлы NULL (потому что они подразумеваются) и снова спросил вас, вы бы сказали два. Действительно ли это имеет значение? Я знаю, что некоторые алгоритмы, как в случае вставки, где вы должны проверить, если Uncle является Black, но можно было бы написать, что в коде, как следующее:

Node *uncle = uncle(child); 
if (uncle == NULL || uncle->color == BLACK) 

Вы не должны написать

if (uncle->color == BLACK) 

Так если это не имеет значения при просмотре дерева и в коде, мы должны отдельно определить NULL от цвета, почему даже называть их одним и тем же для начала?

Answer 1

Причина, по которой вам нужно проверить, является ли значение uncle равноценным при вставке, является то, что хотя дети листа считаются черными узлами, они по-прежнему не имеют значения. Это приводит к тому, что вы должны проверить if uncle == null перед проверкой if uncle-> color == BLACK. Если uncle действительно является дочерним листом aka null, то вы знаете, что это ребенок листа и больше не можете перейти на другую половину условного выражения, иначе вы получите исключение (попытка проверить цвет нулевого объекта приведет к некоторому исключению) , Тем не менее, вам все еще нужна эта другая половина условного условия для проверки фактических черных объектов в дереве.

Но я предполагаю, что другая часть вашего вопроса - почему в первую очередь заставляют детей с черными листьями?

Рассмотрим эту картину из http://www.geeksforgeeks.org/red-black-tree-set-2-insert/

После вставки 30 в дерево выше, 30-х годов дядя теперь должен быть проверен, так как в настоящее время существует два соседних красных узлов. Обратите внимание, что 10-летний левый ребенок, будучи 30-летним дядей, равен нулю. Поскольку нулевой объект указывает на черный объект, вы знаете, что должен произойти случай вращения 2. Как вы это сделаете в коде? Посмотрите на код в ваш вопрос,

if (uncle == NULL || uncle->color == BLACK) 

Вы не можете просто проверить цвет дяди, потому что могут быть случаи, когда дядя «нулевой», что делает его невозможно проверить цвет. Цвет детей листа является черным по понятию, следовательно, картина в вашем вопросе. В противном случае мы не будем называть дочерние элементы листа пустыми, мы будем называть их черными объектами.