이진 트리 공부

이진트리에 대해서 공부해보자

 

728x90

 

 

---

 

 

 

1. 개념

 

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리(Tree) 자료구조를 말한다. 여기서 두 개의 자식 노드는 각각 왼쪽 자식(left child), 오른쪽 자식(right child) 이라고 부른다. 트리는 그래프 이론의 한 형태인데, 방향성이 있고 순환(cycle)이 없는 연결 구조를 가지며, 이 중 이진 트리는 특별히 자식이 둘 이하라는 제약 조건이 붙은 것이다.

 

 

 

 

 

2. 이진 트리의 기본 용어

 

루트(root): 트리의 가장 꼭대기 노드. 부모가 없다.
리프(leaf): 자식이 없는 노드. (즉, 말단 노드)
내부 노드(internal node): 자식이 하나 이상 있는 노드.
서브트리(subtree): 어떤 노드를 루트로 하는 작은 트리 구조.
높이(height): 루트에서 가장 깊은 리프 노드까지의 경로 길이.
레벨(level): 루트는 레벨 0, 그 자식들은 레벨 1, 그 자식들은 레벨 2... 이렇게 내려간다.

 

 

 

 

 

3. 이진 트리의 종류

 

이진 트리는 제약 조건에 따라 여러 종류로 나뉜다.

종류	설명
포화 이진 트리(Full Binary Tree)	모든 노드가 0개 또는 2개의 자식을 가짐.
완전 이진 트리(Complete Binary Tree)	마지막 레벨을 제외하고 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 트리.
균형 이진 트리(Balanced Binary Tree)	모든 리프 노드의 깊이가 비슷한 트리. (AVL 트리 등이 예)
이진 탐색 트리(Binary Search Tree, BST)	왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값을 저장하는 트리.

 

 

 

 

 

 

4. 이진 트리의 주요 특징

 

공간 복잡도: n개의 노드가 있으면 간선(edge)은 항상 n-1개이다.

 

탐색, 삽입, 삭제 시간 복잡도:
일반 이진 트리는 O(n)일 수 있다. (최악의 경우)
하지만 균형 잡힌 이진 트리(Balanced Tree, 예: AVL, Red-Black Tree)는 O(log n)로 빠르다.

 

순회(traversal) 방법이 다양하다:
전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽
중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽
후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트
레벨 순서 순회 (Level-order): 너비 우선 탐색(BFS)

 

 

예시

      10
     /  \
    5   15
   / \    \
  2   7    20

 

전위 순회: 10 → 5 → 2 → 7 → 15 → 20
중위 순회: 2 → 5 → 7 → 10 → 15 → 20
후위 순회: 2 → 7 → 5 → 20 → 15 → 10
레벨 순서: 10 → 5 → 15 → 2 → 7 → 20

 

 

 

 

 

 

5. 이진 트리의 실제 활용

 

이진 탐색 트리(BST): 빠른 탐색과 삽입/삭제를 지원하는 자료구조.
힙(Heap): 우선순위 큐(priority queue) 구현에 사용됨.
하프만 트리(Huffman Tree): 데이터 압축 알고리즘(하프만 코딩)에 사용.
문법 분석(parse tree): 컴파일러에서 소스 코드를 파싱할 때.