[자료구조] 완전 이진 트리를 배열로 만들 경우 크기 계산

완전 이진 트리를 동적 배열로 생성하려면 전체 크기 (배열사이즈)를 알아야 합니다.

N=5 일 때, 트리의 전체 크기 구하기

완전 이진 트리는 자식이 생길때 마다 노드가 2개씩 증가하는 것을 알 수 있습니다.

완전 이진 트리에서 N = 5 라고 하는 말은 리프 노드의 갯수가 위의 그림과 같이 5개가 있다는 것을 알 수 있습니다.

 

먼저 트리의 전체 크기를 구하려면 트리의 높이(h)를 먼저 구해야 합니다.

완전 이진 트리의 특성상, ( h >= 1) , 2^(h-1) < N <= 2^h 이 성립하므로, 모든 항에 log2를 해주면

h-1 < log2N <= h 이기 때문에 올림을 해주면 높이 h 값을 구할 수 있습니다.

 

즉, N = 5 일 경우 h = 3입니다.

int h = (int) Math.ceil(Math.log(N) / Math.log(2)) // log2(N)
int treeSize = (int) Math.pow(2, h + 1) - 1;

h = 3 일 경우의 포화 이진 트리의 크기를 트리의 전체 크기로 하도록 합니다.

treeSize를 구할 경우 등비 수열의 합을 이용해서 구할 수 있습니다.

등비수열의 합 ( 네이버 검색 )

트리의 노드의 갯수는 첫째 항 a = 1이고, 공비 r= 2인 등비 수열입니다.

1 + 2 + 4 + 8 + ... + 2^n ( n = 1부터 시작 )

즉, 높이가 h 인 포화 이진 트리의 전체 크기는 등비수열의 합 공식에 따라

(2 ^ (h+1) ) - 1로 구할 수 있습니다.