Является ли дерево со всеми черными узлами красным черным деревом?

Question

Кажется, определение в вики не точное:

http://en.wikipedia.org/wiki/Red-black_tree#Properties

Является ли дерево со всеми черными узлами красным черным деревом?

Если определение rbtree не столь строгое, как мы решаем, печатать ли дочерние элементы черного узла как красный или черный?

Answer 1

Да , дерево со всеми черными узлами может быть красно-черным деревом. Дерево должно быть идеальным бинарным деревом ( все листья имеют одинаковую глубину или один и тот же уровень, и в котором каждый родитель имеет двух детей ), и, таким образом, это единственное дерево, чья высота черного равно его высоте дерева .

Answer 2

Красно-черное дерево - это просто двоичное представление дерева 2-3-4 .Любой красный узел в красно-черном дереве соответствует куску его родительского узла в аналогичном дереве 2-3-4.Например:

           [black 5]
          /         \
      [red 3]     [black 6]
     /       \
[black 2] [black 4]

- представление дерева 2-3-4

    [3 | 5]
   /   |   \
 [2]  [4]  [6]

Если красно-черное дерево имеет только черные узлы ,означает, что оно представляет собой 2-3-4 дерева только с 2 узлами (отдельные записи), а не с 3 узлами (например, [3 | 5] в примере) или с 4 узлами.Обратите внимание, что это просто простое двоичное дерево поиска.

Answer 3

Возможно иметь правильное красно-черное дерево, которое имеет все черные узлы. Тривиально, RBTree с единственным узлом или с единственными конечными узлами, являющимися прямыми дочерними узлами корня, будет всеми задними узлами.

Answer 4

Чтобы ответить на вторую часть вопроса о решении, печатать ли узел красным или черным, эта информация хранится в каждом узле.

В типичном бинарном дереве поиска каждый узел содержит значение, левый указатель и правый указатель (и, возможно, родительский указатель).В красно-черном дереве каждый узел содержит все эти вещи плюс дополнительное поле, указывающее, является ли этот узел красным или черным.Различные операции над деревом, такие как вставка или удаление, несут ответственность за постоянное поддержание этой информации о цвете.

Вам никогда не дали бы неокрашенное дерево и сказали бы выбирать цвета для узлов (кромевозможно, как домашнее задание или экзаменационный вопрос).

Answer 5

Вот пример, показывающий, что все узлы красно-черного дерева черные:

Сначала вставьте {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} в порядке возрастания в красно-черное дерево. Затем удалите {10, 9, 8} в порядке убывания из красно-черного дерева.

Наконец, все узлы этого красно-черного дерева черные.

Красно-черное дерево, все чёрные узлы которого совпадают с B-деревом (m = 4), чьи узлы имеют только один ключ.

Answer 6

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

Вы можете сами доказать, что дерево со всеми черными узлами может быть красным черным деревом, если построить небольшое дерево такого типа. Например:

                            2,black
                      1,black      3,black 

В этом дереве есть все черные узлы, и оно удовлетворяет всем условиям. Предположим, что root имеет nil в качестве родителя, а оба конечных узла имеют обоих дочерних узлов как nil. Надеюсь, это поможет.

Answer 7

Да, но это не относится к красно-черному дереву со всеми красными узлами. Такое дерево недопустимо. Существуют ограничения на то, какие узлы должны быть черными. Например, листовые узлы должны быть черными, а потомки красного узла должны быть черными.