이진 트리(Binary Tree)

개요

이진 트리(Binary Tree)는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 계층적 구조이다. 트리의 기본이자 다양한 트리 기반 알고리즘의 뼈대 역할을 하며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie), 표현식 트리 등으로 확장된다. 노드의 위치와 순서가 중요한 구조로, 다양한 순회 알고리즘이 적용된다.

---

1. 이진 트리의 구조와 용어

용어	설명
노드(Node)	데이터를 저장하는 기본 단위
루트(Root)	트리의 시작 노드 (부모 없음)
왼쪽 자식(Left Child)	루트 기준 왼쪽 하위 노드
오른쪽 자식(Right Child)	루트 기준 오른쪽 하위 노드
리프(Leaf)	자식이 없는 노드
서브트리(Subtree)	특정 노드를 루트로 하는 하위 트리

---

2. 이진 트리의 종류

유형	설명
포화 이진 트리 (Perfect)	모든 레벨이 완전히 채워짐
완전 이진 트리 (Complete)	마지막 레벨을 제외하고 노드가 모두 채워짐
균형 이진 트리 (Balanced)	좌우 서브트리 높이 차이가 1 이하
편향 이진 트리	한쪽으로 치우친 트리 (선형 구조)

---

3. 이진 트리의 특징

• 최대 노드 수: 2^h - 1 (높이 h일 때)
• 레벨 l에 존재할 수 있는 최대 노드 수: 2^l
• n개의 노드 → 최대 높이 = n, 최소 높이 = log₂(n)

---

4. 파이썬 이진 트리 구현 예시

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# 트리 구성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

---

5. 이진 트리 순회 방법

순회 방식	순서	특징
전위 순회	루트 → 왼쪽 → 오른쪽	복사, 구조 출력
중위 순회	왼쪽 → 루트 → 오른쪽	이진 탐색 트리 정렬 출력
후위 순회	왼쪽 → 오른쪽 → 루트	삭제, 후행 처리
레벨 순회	위에서 아래로, 왼쪽에서 오른쪽	BFS 기반

---

6. 이진 트리의 활용 분야

분야	활용 예시
이진 탐색 트리	정렬된 데이터의 빠른 탐색/삽입/삭제
힙 트리	최대/최소값 추출을 위한 우선순위 큐 기반
수식 트리	수식의 계층 구조 표현 및 계산
표현식 트리	컴파일러에서 수식 평가 구조 구성
그래프 순회	DFS/BFS 구현 기반

---

7. 시간 및 공간 복잡도 (균형 트리 기준)

연산	평균 시간 복잡도	최악
삽입 / 삭제 / 탐색	O(log n)	O(n) (편향 트리 시)
순회 (DFS/BFS)	O(n)	O(n)

균형 유지가 중요한 이유는 탐색 속도에 직접 영향을 주기 때문이다.

---

8. 결론

이진 트리는 각 노드가 두 개의 자식을 가지는 트리 구조로, 다양한 트리 알고리즘의 기초가 되는 자료구조다. 탐색, 정렬, 표현식 처리 등 폭넓은 응용이 가능하며, 순회 방식과 균형 구조를 정확히 이해하는 것이 중요하다. 이진 탐색 트리, 힙, 트라이, AVL 트리 등의 구조 학습은 이진 트리 기반에서 출발한다.