이진 트리는 기본적인 트리의 형태 중 하나이다.
이진 트리란?
한 부모가 가질 수 있는 자식 노드의 개수가 최대 2개로 제한되어 있는 트리를 말한다.
그러나 자식의 개수와 트리의 형태에 따라 특별한 이진 트리의 종류가 있다.
정 이진 트리 (Full binary tree)
(출처는 GeeksForGeeks)
정 이진 트리는 모든 부모 노드가 자식 노드를 0개 혹은 2개로만 가지는 트리를 말한다.
완전 이진 트리 (Complete binary tree)
완전 이진 트리는 마지막 리프 노드를 제외한 모든 노드가 차 있고 마지막 레벨의 경우 모든 노드가 채워져 있진 않아도 왼쪽에서 오른쪽 방향으로는 다 차있는 트리를 말한다.
완전 이진 트리의 특징
바로 트리에 저장된 노드의 개수가 n개라고 할 때, 트리의 높이가 lg(n) 에 비례한다는 것이다. 그 이유는 등비수열의 합을 살펴보면 된다.
높이가 h인 트리의 최소 노드 개수는 1 + 2 + 2^2 + 2^3 +...+ 2^(h-1) + 1이고 최대 노드 개수는 1 + 2 + 2^2 + ... + 2^h이다.
따라서 2^h <= n <= 2^(h+1) -1 이고
2^h <= n < 2^(h+1) 이 성립하게 된다.
양변에 lg를 씌우면 h <= lg(n) 이다.
여기서 더 나아가, 현재 노드의 개수에서 2배가 된다면 아래와 같은 식이 성립한다.
lg(2n) = lg(2) + lg(n) = 1 + lg(n) >= h +1
즉 노드의 개수가 최소 2배가 되면 높이도 1 늘어나는 것을 확인할 수 있다.
결론적으로 완전 이진 트리의 노드를 탐색하기 위한 시간복잡도는 O(lg(n)) 에 비례한다는 것.
포화 이진 트리 (Perfect binary tree)
포화 이진 트리는 정 이진 트리와 완전 이진 트리의 특징을 모두 갖춘 트리이다. (그나저나 번역된 것이 더 헷갈린다... perfect가 완전 아닌가? 이거는 둘째치고, 왜 포화는 full이 아니지?)
포화 이진 트리의 특징
포화 이진 트리의 특징은 노드의 개수나 트리의 높이 중 하나만 알면 나머지 정보를 모두 알 수 있다는 것이다.
트리의 높이가 10인 트리에서 총 노드 개수는? 2^11 - 1
(참고로 root node만 있는 트리는 트리의 높이가 0이다. 0부터 시작.)
노드의 개수가 127개인 트리에서 트리의 높이는? 6
아주 쉽게 구할 수 있다. 근데 이걸 어따 써먹지?
