높이균형트리의 최소 노드수 구하기

출처 : 정보올림피아드 2012년 중등부 15번 문제

정답) 54개

문제풀이)

최소 노드 이므로 1 일때는 1

높이 2일때는 루트노드 1 + 왼쪽 노드 1 이다.

높이 3일때는 루트노드 1 + 왼쪽/오른쪽 2 + 자신의 높이 1 = 4이다.

높이 4일때는 루트노드 1 + 왼쪽/오른쪽 2 + 왼쪽 자식 2 + 오른쪽 자식 1 + 왼쪽 손자 1 = 7

그림을 그려 보면 바로 전 트리를 왼쪽에 갖다 놓은 후에 그 전전 트리를 오른쪽에 갖다 놓고 루트를 하나 올리는 형식이 된다.

 

이러한 규칙으로 테이블을 그려 보면 다음과 같이 그릴 수 있습니다

전항 + 전전항 + 현재 루트(1) 형식으로 구할 수 있습니다.