알고리즘 분석 | 자료구조 | 이진트리 종류 | Full binary | Complete binary

이전 포스팅

알고리즘 분석 | 이진 탐색트리 BST | inorder successor

이진트리의 개념과 종류

Fig. 1. 거의 완전한 이진 트리(Nealy complete)

이진트리(Binary Tree)란, 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조를 말합니다. 이진트리에서는 각 노드는 하나의 값과, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 가지며, 이러한 포인터를 이용해 트리를 탐색할 수 있습니다.

이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 이유 때문에, 트리의 높이가 낮아지게 됩니다. 즉, 트리의 높이는 log2(n) 이하가 되며, 이러한 특성 때문에 이진트리는 효율적인 탐색 및 정렬에 매우 유용합니다.

이진트리는 다양한 응용 분야에서 활용되며, 컴퓨터 과학에서는 이진트리를 기반으로 많은 자료구조와 알고리즘이 구현됩니다. 예를 들어, 이진검색트리(Binary Search Tree)는 이진트리를 이용하여 데이터를 정렬하고 탐색하는 자료구조이며, 힙(Heap)은 이진트리를 이용하여 우선순위 큐를 구현하는 자료구조입니다

---

 

풀 이진 트리 (Full Binary Tree)

Full binary tree는 모든 레벨에서 노드가 가득 찬 이진트리입니다. 즉, 모든 노드가 0개 혹은 2개의 자식 노드를 가지며, 모든 리프 노드의 레벨이 같은 이진트리입니다.

 

예를 들어, 다음과 같은 트리는 Full binary tree입니다

        A        level - 0          
      /   \       
     B     C     level - 1
    / \           
   D   E         level - 2

모든 레벨에서 노드가 가득 차 있고, 모든 리프 노드의 레벨이 같기 때문에 이 트리는 full binary tree입니다.

 

반면에, 다음과 같은 예시는 Full binary tree가 아닙니다.

         1
       /   \
      2     3
     / \   /
    4   5 6

3의 왼쪽 자식인 6이 없으므로 모든 레벨에서 노드가 가득 차있지 않고, 모든 리프 노드의 레벨이 같지 않기 때문에 이 트리는 full binary tree가 아닙니다.

---

 

완전 이진트리(Complete binary Tree)

완전 이진트리(Complete Binary Tree)란 모든 레벨에서 노드가 가득 차 있고, 마지막 레벨에서는 노드가 왼쪽부터 채워지는 이진트리를 말합니다. 아래는 7개의 노드를 가지는 완전 이진트리의 예시입니다.

        A
      /   \
     B     C
    / \   / 
   D   E F

 

반면에, 다음과 같은 예시는 Complete binary tree가 아닙니다.

       1
      / \
     2   3
    / \   \
   4  5    7

---

 

대체로 완전한 이진트리(Almost or Near complete binary tree)

거의 완전한 이진트리(Nearly Complete Binary Tree)란 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차 있고, 마지막 레벨에서는 노드가 왼쪽부터 채워지는 이진트리를 말합니다.

        A
      /   \
     B     C
    / \   / \
   D   E F   G
  / \
 H   I

반면에, 다음과 같은 예시는 Near complete binary tree가 아닙니다

        A
      /   \
     B     C
    / \     \
   D   E     G
  / \
 H   I

마지막 레벨을 제외한 모든 레벨의 노드가 가득 차 있어야하지만, 노드 C의 왼쪽 자식 노드가 비어있으므로, 다음과 같은 예시는 Near complete binary tree 가 아닙니다.

---