Красно-черные деревья, связь между черными и красными узлами - PullRequest
Новая
       38

Красно-черные деревья, связь между черными и красными узлами

0 голосов
/ 12 апреля 2011

Одним из вопросов из моей домашней работы было найти точную нижнюю границу 

(#black nodes)/(#red nodes)

в rb-дереве.оценка должна быть не асимптотической.Любые предложения?

Ваша помощь будет принята с благодарностью.

1 Ответ

3 голосов
/ 12 апреля 2011

Предполагая, что это домашнее задание:

Давайте рассмотрим некоторые свойства RedBlack Trees из Wikipedia :

  1. ...
  2. Корень черный.
  3. Все листья черные.
  4. Оба потомка каждого красного узла черные.
  5. ...

Чтобы получить нижнюю границу # B / # R, вы хотите построить дерево, которое имеет как можно больше красных узлов. (К сожалению, из-за 2,3,4 вы не можете построить все красное дерево)

Некоторые вопросы, о которых стоит задуматься:

  • Вы можете разместить больше красных узлов в сбалансированных или не сбалансированных деревьях?
  • имеет значение четная или нечетная максимальная высота?
  • учитывая, что дерево содержит 3, 7, ..., (2 ^ n) -1 задних узлов, сколько красных можно разместить?
...