Дети на красно-черном дереве?

Согласно этому объяснению красно-черного дерева, дерево должно иметь следующие свойства:

  1. Узел может быть красным или черным.
  2. Корень черный. (Это правило иногда опускается. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборот, это правило мало влияет на анализ.)
  3. Все листья (NIL) черные. (Все листья того же цвета, что и корень.)
  4. Оба дочерних элемента каждого красного узла черные.
  5. Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов.

Что мешает сделать каждый узел черным?


algorithm red-black-tree
person dublintech    schedule 28.03.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Возможно. Но для поддержания условия 5 иногда вы можете захотеть покрасить узел в КРАСНЫЙ цвет.

Например, рассмотрим следующий пример.

  a
 / \
b   c

Здесь все узлы могут быть ЧЕРНЫМИ

Теперь, если вы хотите вставить новый узел, какой цвет вы выберете? КРАСНЫЙ. поскольку если вы выберете черный цвет, условие 5 не будет выполнено. Таким образом, вы можете продолжать вставлять КРАСНЫЕ узлы, если ни одно из условий (1-4) не нарушено.

person vishnu viswanath    schedule 28.03.2013

arrow_upward
1
arrow_downward

Последнее правило, которое вы процитировали: «Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов».

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

person interjay    schedule 28.03.2013