[자료 구조] 이진 트리 Binary Tree

출처

ChatGPT

---

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다. 이 트리 구조는 컴퓨터 과학에서 매우 널리 사용되는 자료 구조 중 하나이며, 데이터의 계층적 관계를 나타내거나 효율적인 검색, 삽입, 삭제 연산을 지원하는 데 유용하다.

• 관련 글 -> [자료구조] 트리 Tree

 

이진 트리의 기본 개념

루트 노드 Root Node

트리의 최상위에 있는 노드이다. 트리는 이 노드를 시작으로 다른 노드들과 연결되나.

자식 노트 Child Node

특정 노트에서 바로 아래에 연결된 노드이다. 이전 트리에서는 왼쪽 자식 노드와 오른쪽 자식 노드로 구분된다.

부모 노드 Parent Node

자식 노드를 가지고 있는 노드이다. 자식과 부모는 서로 계층적으로 연결되어 있다.

잎 노드 Leaf Node

자식 노드를 가지지 않는, 즉 트리의 말단에 위치한 노드이다.

서브트리 Subtree

이진 트리의 특정 노드를 루트로 하는 트리 부분이다.

 

이진 트리의 특징

노드 수

높이가 h인 이진 트리의 최대 노드 수는 2^h -1 개이다. 예를 들어, 높이가  3인 트리의 최대 노드 수는 2^3 -1 = 7 개이다.

포화 이진 트리 Full Binary Tree

모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리이다.

완전 이진 트리 Complete Binary Tree

모든 례벨에서 노드가 꽉 차 있으며, 마지막 레벨에서는 왼쪽에서부터 차례대로 노드가 채워져 있는 트리이다.

균형 이진 트리 Balanced Binary Tree

좌우 서브프리의 높이 차이가 1 이하인 이진 트리이다. 균형을 유지함으로써 검색 및 삽입/삭제 연산이 효율적으로 수행된다.

 

이진 트리의 종료

1. 포화 이진 트리 Full Binary Tree

각 노드가 0개 또는 2개의 자식 노드를 갖는다.

모든 리프 노드가 동일한 깊이에 있다.

    1
   / \
  2   3
 / \ / \
4  5 6  7

 

2. 완전 이진 트리 Complete Binary Tree

마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽에서부터 채워진다.

    1
   / \
  2   3
 / \ / 
4  5 6

 

3. 이진 참색 트리 Binary Search Tree, BST

왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 크다

데이터를 정렬된 형태로 저장하여 검색, 삽입, 삭제가 효율적으로 수행된다.

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

 

4. 균형 이진 트리 Balanced Binary Tree

좌우 서브트리의 높이 차이가 1 이하로 균형을 유지하는 트리이다.

레드-블랙 트리(Red-Black Tree), AVL 트리 등이 균형 이진 트리의 예이다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

이진 트리의 순회 Traversal

이진 트리에서는 노드를 방문하는 순서에 따라 다양한 순회 방법이 있다.

 

예시 이진 트리

        1
       / \
      2   3
     / \
    4   5

1. 전위 순회(Pre-order Traversal)

• 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문한다.
• 예시 : 1,2,4,5,3

2. 중위 순회(In-order Traversal)

• 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문한다.
• 예시 : 4,2,5,1,3

3. 후위 순위(Post-order Traversal)

• 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문한다.
• 예시 : 4,5,2,3,1

4. 레벨 순회(Level-order Traversal)

• 트리의 각 레벨을 왼쪽에서 오른쪽으로 순서대로 방문한다.
• 예시 : 1,2,3,4,5

 

이진 트리의 시간 복잡도

이진 트리에서 주요 연산의 시간 복잡도는 트리의 높이에 따라 결정된다. 트리가 균형을 유지할 때, 이진 트리의 높이는 O(lon n)이 되며, 대부분의 연산(탐색, 삽입, 삭제)의 시간 복잡도는 다음과 같다.

• 탐색: O(log n) (균형 잡힌 트리일 경우)
• 삽입: O(log n)
• 삭제: O(log n)

그러나 트리가 한쪽으로 치우친 경우에는 최악의 경우 시간 복잡도가 O(n)이 될 수 있다.

 

이진 트리의 응용

이진 탐색 트리 BST

정렬된 데이터를 빠르게 탐색, 삽입, 삭제하기 위한 트리

힙 Heap

우선순위 큐를 구현할 대 사용하는 완전 이진 트리

허프만트리

데이터 압축 알고리즘에서 사용하는 트리 구조