реализация вставки красного черного дерева - что такое часовой?

Я получил этот код с сайта 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;  
}

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


c++ red-black-tree binary-search-tree
person Community    schedule 31.07.2014    source источник
comment
nil является листовым узлом. Один из способов взглянуть на дерево RB — увидеть все листья как nil узла.   -  person scohe001    schedule 01.08.2014
comment
en.wikipedia.org/wiki/Sentinel_value   -  person Ed S.    schedule 01.08.2014

Ответы (2)


arrow_upward
2
arrow_downward

По сути, это заполнитель.

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

Из википедии красно-черное дерево

1. Узел либо красный, либо черный.

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

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

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

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

person Camron_Godbout    schedule 31.07.2014

arrow_upward
1
arrow_downward

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

person sp2danny    schedule 31.07.2014