Как определить, может ли красно-черное дерево иметь X черных узлов и Y красных узлов или нет

Question

На следующей неделе у меня экзамен по алгоритмам, и мне были заданы вопросы для его подготовки.Однако один из этих вопросов поставил меня в тупик.

«Можем ли мы нарисовать красно-черное дерево с 7 черными узлами и 10 красными узлами? Почему?»

Похоже, на него можно было бы быстро ответить, но я не могу обдумать это.

CRLS дает нам максимальную высоту дерева RB с n внутренними узлами: 2 * lg (n + 1).

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

Любые советы?

Answer 1

ответ прост.

Поскольку мы знаем, что красный узел может иметь только черного родителя. Макс. Нет. из узлов будет, когда каждый черный узел каждого дочернего узла красного и, следовательно, каждый черный узел имеет красный родительский. Таким образом, для «n» черных узлов «2n» красных узлов возможны.

Подумайте так:

1. поставить первый узел (который является корнем) и сделать его черным
2. сделать обоих своих детей красными
3. делает левого и правого потомков обоих этих красных узлов черными, а для всех этих черных узлов
4. следуйте той же процедуре, что и root, пока число черных узлов не достигнет заданного значения (в данном случае 7)

надеюсь, это помогло вам визуализировать решение.

Answer 2

Поскольку это подготовка к экзамену, я не хочу давать вам прямой ответ, но я думаю, что вам нужно учесть свойства, определяющие порядок построения красно-черного дерева:

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

(Stoleэто со страницы википедии: http://en.wikipedia.org/wiki/Red-black_tree)

Учитывая количество перечисленных вами узлов, можете ли вы удовлетворить все эти свойства?

Answer 3

Ответ критически зависит от того, использует ли ваше дерево RB черные фиктивные узлы на листьях, и если да, то они включены в число семи черных узлов. Если нет, рассмотрим полное дерево из семи черных узлов

        *
       / \
      *   *
     /\   /\
    *  * *  *

У вас не будет особых проблем с добавлением десяти красных узлов.