красная черная вставка дерева вставка - что такое страж?

Question

Я получил этот код из http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html и его конструктор для красного черного узла

RedBlackTree::RedBlackTree() 
{ 
    nil = new RedBlackTreeNode; 
    nil->left = nil->right = nil->parent = nil; 
    nil->red = 0; 
    nil->key = MIN_INT; 
    nil->storedEntry = NULL; 

    root = new RedBlackTreeNode; 
    root->parent = root->left = root->right = nil; 
    root->key = MAX_INT; 
    root->red=0; 
    root->storedEntry = NULL; 
} 

Что такое ноль и почему он инициализируется в конструкторе? Могу ли я просто объявить нулевой узел в своем личном поле данных и инициализировать его в моей функции вставки?

Answer 1

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

Answer 2

Это в основном место.

Из кодов README: /* Часовое используется для корня и для ноля. Эти часовые - , созданный при кадрировании RedBlackTreeCreate. root-> left всегда должен указывать на узел, который является корнем дерева. nil указывает на узел, который всегда должен быть черным, но имеет произвольных детей и родителя, а не ключ или информацию. Смысл использования этих сторожей так, что корень и нильполугруппы узлы не требуют особых случаев в коде */

Из википедии red-black tree

1.А узла красный или черный.

2. Корень черный. (Это правило иногда опускается. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборот, это правило мало влияет на анализ.)

3. Все листья (NIL) являются черными. (Все листья имеют тот же цвет, что и корень.)

4. Каждый красный узел должен иметь два черных дочерних узла.

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