Какова формула для минимального числа узлов в красно-черном дереве высоты h?

Я прочитал, что это log (n+1)

Пока я знаю, что:

Для для h = 1, минимальное число узлов = 2.

Для h = 2, минимальные узлы = 4.

Для h = 3, минимальные узлы = 10.

Однако это было сделано чисто путем прослеживания его, используя правила для красно-черных деревьев.

Должен ли я принимать во внимание высоту черного цвета при попытке найти это или мой подход / расчеты просто полностью неверны?

1 2
algorithm red-black-tree binary-search-tree

1 ответ:

Мы можем рекурсивно найти минимальное число узлов.
count_minimum_node вернет количество узлов для достижения высоты h. 

int count_node(int h) 
{
    int sum = h;
    for(int i=1; i<=h-2; i++) sum += count_node(i);
    return sum;
}

int count_minimum_node(int h) { return count_node(h+1); }
1