지난번에 트리Tree에 대한 개념을 설명했었습니당!

오늘은 이진 트리Binary Tree에 대해 설명하겠습니당.

이진 트리(Binary Tree)

이진 트리는 루트 노드Root Node를 중심으로 두 개의 서브 트리Tree(큰 트리에 속하는 작은 트리)로 나뉘어지는 트리입니당.

일반적으로 트리는 최대 2개의 노드를 가지는 이진 트리를 많이 사용합니당.

구성

위에 그림은 모두 이진 트리를 의미해용.

루트 노드를 기준으로 깊이를 Level-0이라 표현합니당. 여기서 Level은 트리의 '층'을 의미합니당. Level의 값은 0부터 시작해용. 그리고 트리의 최고 레벨은 높이Height라고 합니당! 위 그림의 모든 트리(우측 빼고)는 높이Height가 2입니당!

가운데처럼 자식 노드가 2개가 아니라도 이진 트리라고 할 수 있습니당.

그리고, 마지막은 아예 없는데, 이처럼 아무런 구조가 없는 공집합도 이진 트리에 포함됩니당.

이진 트리는 배열Array로도 표현할 수가 있어용. 가운데 그림을 보시면 이해하시기 수월할텐데용, 노드가 없는 경우엔 배열에 아무런 값을 넣지 않습니당.

여기서 알 수 있는 사실은, 이진 트리는 노드의 개수가 n개이고, 루트 노드가 0이 아닌 1에서 부터 시작할 경우 i번째 노드에 대해서 부모(i) = $\frac{i}{2}$, 왼쪽 자식(i) = $2i$, 오른쪽 자식(i) = $2i + 1$입니당.

좌측 트리에 2를 기준으로 설명하자면, 2는 배열 기준 인덱스가 2이고, 부모 인덱스는 $\frac{2}{2} = 1$이 되고 좌측 자식은 $2\cdot 2 = 4$, 그리고 우측은 $2\cdot 2 + 1 = 5$이 되는 것을 확인하실 수 있어용!

종류

이진 트리는 구성에 따라 부르는 명칭이 각각 따로 있습니당!

좌측부터 설명하자면, 모든 레벨이 꽉 찬 트리를 포화 이진 트리Perfect Binary Tree, PBT라고 하고,

위에서 아래로, 좌측부터 우측까지 순서대로 쌓인 트리를 완전 이진 트리Complete Binary Tree, CBT라고 합니당.

그리고 마지막으로, 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리를 정 이진 트리Full Binary Tree, FBT 또는 적정 이진 트리Proper Binary Tree라고 합니당.

그래서 어디에 쓰여요?

추후에 정리하겠지만, 이런 자료 구조는 탐색에 용이하게 쓰여용! 원하는 결과를 빠르게 찾는건 프로그래밍에선 매우 중요한 요소입니당.

트리 구성이 잘 되어 있다면, 탐색을 하는데 모든 요소를 찾지 않고, 절반에 가까운 원소를 배제해서 찾기 때문에 순회하면서 찾는 것보다 훨씬 효율적으로 찾게 됩니당!

오늘은 여기까지 정리할게용