높이 h 인 빨강 - 검정 나무의 최소 노드 수에 대한 공식은 무엇입니까?

Question

나는 로그가 기수 2 인 곳에서 log (n + 1) < = h < = 2 * log (n + 1)이라고 읽었습니다. 그러나 알려진 몇 가지 최소 높이에서 이것을 시도 할 때 항상 운동.

지금까지 내가 알고 : 시간 = 1, 노드의 최소 번호에 대한

= 시간 = 2 2.

, 최소 노드 = 시간 = 3

4. 최소 노드 = 10.

그러나 이것은 완전히 빨강 - 검정 나무에 대한 규칙을 사용하여 추적함으로써 수행되었습니다.

이것을 찾으려고 할 때 검은 높이를 메모해야합니까, 아니면 접근/계산이 완전히 잘못 되었습니까?

Answer 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); }