[DS] 이진 트리 - binary tree (개념 및 이진 트리의 종류)

이미지 출처 : Pixabay

트리 Tree 는 원소들을 계층적으로 저장하는 비선형 non-linear 자료구조입니다. 

* 위 그림의 나무를 뒤집어 둔 것과 비슷하게 생겼습니다.

최상의 원소 루트 root를 제외한 각각의 원소는 하나의 부모 parent 노드와 0개 이상의 자식 child 노드들을 가지고 있습니다.

여기서 자식이 없는 노드를 외부 노드 external node 혹은 리프 노드 leaf node, 하나 이상의 자식 노드를 가진 노드를 내부 노드 internal node 라 칭합니다.

이 중에서, 이진 트리 혹은 바이너리 트리 binary tree 는 하나의 노드가 최대 2개의 자식을 가지는 트리 자료구조를 의미합니다.

아래 그림은 바이너리 트리가 어떻게 구성되는지를 나타낸 것입니다.

이진 트리 - binary tree

이진 트리에서는 내부 노드의 자식을 왼쪽 자식 left child 혹은 오른쪽 자식 right child 으로 분류합니다.

내부 노드의 왼쪽 자식을 루트로 갖는 서브트리를 왼쪽 서브트리 left subtree, 오른쪽 자식을 루트로 갖는 서브트리를 오른쪽 서브트리 right subtree 라 칭합니다.

트리 자료구조에서 루트 노드의 깊이는 0이며 위 그림에서 초록색으로 하이라이트 된 노드의 깊이는 2, 주항색으로 하이라이트 된 노드의 깊이는 4입니다. 즉, 깊이란 루트 노드에서 몇 번의 재귀호출을 통하여 해당 노드에 접근이 가능한지를 나타낸 것이라 할 수 있겠습니다.

따라서 트리의 높이는 외부 노드의 최대 깊이와 같습니다.

 

트리를 구현하기 위해서는 트리 내에 회로 Cycle 이 존재하지 않아야 합니다.

이진 트리는 자료의 삭입, 삭제 방법에 따라 정 이진 트리 Full binary tree(혹은 적정 이진 트리 Proper binary tree), 완전 이진 트리 Complete binary tree, 포화 이진 트리 Perfect binary tree 로 나뉩니다.

 

정 이진 트리 Full binary tree (혹은 적정 이진 트리 Proper binary tree)는 각 내부 노드가 두 개의 자식 노드를 갖는 순서화된 트리입니다. (홀수 개의 자식 노드를 가질 수 없습니다.)

완전 이진 트리 Complete binary tree 는 부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 트리를 말하며, 마지막 레벨을 제외하고 모든 노드가 가득 차 있어야 합니다. 또한, 마지막 레벨의 노드도 왼쪽으로 몰려 있어야 합니다. (중간에 빈 곳이 없어야 합니다.)

포화 이진 트리 Perfect binary tree 는 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 이진 트리를 의미합니다.

이를 그림으로 나타내면 다음과 같습니다 : 

적정/완전/포화 이진 트리

위 그림에서 같은 색으로 칠해진 노드들은 같은 레벨에 위치함을 의미합니다.

 

이 때, 각 노드에 유일한 unique 값이 존재하며, 그 노드의 왼쪽 서브트리는 그 노드의 값보다 작은 값을 가진 노드들로, 오른쪽 서브트리는 그 노드의 값보다 큰 값을 가진 노드들로 구성된 트리를 이진 탐색 트리 Binary search tree 라 합니다. 그 중에서도, 완전 균형 트리의 형태를 취하고 있는 이진 탐색 트리를 균형 이진 탐색 트리 Balanced binary search tree 라 칭합니다.

그리고 부모 자식 간의 대소 관계는 정의되어 있으나 형제간의 대소관계는 정의되어 있지 않은 완전 이진 트리 자료구조의 일종을 힙 Heap 이라 합니다.

균형 이진 탐색 트리 / 힙

균형 이진 트리가 아닐 때, 입력되는 값의 순서에 따라 트리의 구조가 결정되어 한쪽으로 노드들이 몰리게 되는 편향 이진 트리 Skewed binary tree 구조가 될 가능성이 있습니다. 최악의 경우 그냥 모든 내부 노드가 왼쪽 자식만 가지게 되는 경우가 발생할 수 있습니다. 이런 문제를 해결하기 위하여 삽입/삭제 시 마다 트리의 구조를 재조정 Rebalancing 하는 과정을 거치는 균형 이진 탐색 트리 (예 : AVL tree, Red-black tree) 생성 알고리즘을 도입합니다.