Что считается листом у красно-черных деревьев?

Я изучаю красно-черные деревья из CLRS. У меня есть 2 вопроса по части, где обсуждаются свойства красно-черных деревьев. Отрывок из CLRS выглядит следующим образом:

Красно-черное дерево - это двоичное дерево, которое удовлетворяет следующим красно-черным свойствам:

  1. Каждый узел красный или черный

  2. Корень черный

  3. Каждый лист (NIL) черный

  4. Если узел красный, то оба его дочерних элемента черные.

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

Прежде всего, в нем говорится, что красно-черное дерево - это двоичное дерево. Почему они не сказали, что красно-черное дерево - это двоичное дерево поиска. Я думал, что вся цель красно-черного дерева - поддерживать баланс в дереве поиска для обеспечения операций logN. Во-вторых, почему лист на красно-черном дереве - НЕТ?

В обычных бинарных деревьях мы к этому привыкли:

               4
         5            7
    3        2     Nil Nil
 Nil Nil  Nil Nil

В этом случае 3, 2 и 7 - это листья. Почему листья в CLRS обозначены как «ноль»?


algorithm red-black-tree binary-search-tree clrs
person Ralph    schedule 08.11.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

В книге красно-черное дерево называется двоичным деревом поиска, оно находится в самом начале главы.

Также в этой главе они указывают, что узлы, помеченные как nil, являются фактическими узлами (называемыми часовыми) с теми же полями, что и обычный узел, но с полем color с фиксированным значением «черный» (другие поля могут быть установленным в произвольные значения); эти узлы всегда появляются в виде листьев в дереве. Таким образом, он отличается от обычного BST, где лист - это узел, у которого левое поддерево и правое поддерево равны nil.

person Óscar López    schedule 08.11.2015
comment
Тогда почему Кормен и компания ссылаются на лист как на Ниль в своем описании свойств красно-черных деревьев? - person Ralph; 08.11.2015
comment
@Ralphyabro Я пошел за своей копией CLRS и исправил свой ответ, см. Выше. - person Óscar López; 08.11.2015
comment
Спасибо! Итак, концепция листьев, имеющих два нуля, не существует в красно-черных деревьях. Что завершает простой путь, так это узел NIL, который, я полагаю, всегда черный и не содержит значения? Я прав? - person Ralph; 08.11.2015
comment
Да, это зависит от того, как вы заполняете поля, как указано в книге, это произвольное значение. Вы даже можете иметь одноэлементный nil узел и проверять его, используя сравнение идентичности. - person Óscar López; 08.11.2015
comment
@ ÓscarLópez, поэтому, когда он говорит о красно-черном дереве n узлов, включает ли оно NIL узла? - person ETHER; 10.06.2018
comment
Нет, NIL-узлы не включаются при подсчете количества узлов в дереве. - person Óscar López; 10.06.2018
comment
Спасибо за быстрый ответ - person ETHER; 10.06.2018