정의
이진 트리(英: binary tree)는 각 노드가 최대 두 개의 자식 노드를 갖는 트리 형태의 자료구조이다. 자식 노드는 일반적으로 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분한다. 루트(root)라 불리는 최상위 노드에서 시작하여, 모든 노드는 하나의 부모 노드와 연결되며, 사이클이 존재하지 않는다.
특성
| 특성 | 설명 |
|---|---|
| 노드 수 | 트리의 깊이(레벨) d에 대해 최대 노드 수는 2^d − 1이다. |
| 높이 | 트리의 높이(또는 깊이)는 루트에서 가장 깊은 리프 노드까지의 경로 길이이다. |
| 완전 이진 트리 | 레벨 k (0 ≤ k < h‑1) 에서는 모든 노드가 두 자식을 가지고, 마지막 레벨 h‑1 은 왼쪽부터 순서대로 채워진 트리. |
| 포화 이진 트리 | 모든 레벨이 완전히 채워진 트리로, 노드 수가 2^h − 1 (h는 트리 높이)인 경우. |
| 균형 이진 트리 | 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 일정 임계값 이하인 트리(예: AVL 트리, Red‑Black 트리). |
구현 방법
- 배열 기반: 완전 이진 트리의 경우 배열(또는 동적 배열)로 구현이 가능하며, 인덱스 i에 대한 왼쪽 자식은 2i + 1, 오른쪽 자식은 2i + 2 로 접근한다.
- 포인터 기반: 각 노드가
left와right포인터(또는 레퍼런스)를 포함하는 구조체/클래스로 구현한다. 이는 비완전 트리에서도 유연하게 사용된다.
주요 활용 사례
| 분야 | 구체적인 예 |
|---|---|
| 검색 | 이진 탐색 트리(Binary Search Tree, BST)는 정렬된 키를 이용해 평균 O(log n)의 탐색·삽입·삭제를 제공한다. |
| 우선순위 큐 | 힙(Heap)은 완전 이진 트리 형태로 구현되며, 최소/최대 힙은 O(log n)의 삽입·삭제 연산을 지원한다. |
| 컴파일러 | 구문 트리(parse tree) 또는 추상 구문 트리(Abstract Syntax Tree, AST)는 표현식·문장의 구조를 이진 트리 형태로 표현한다. |
| 압축 | 허프만 코딩(Huffman coding)에서 사용되는 허프만 트리는 가중치에 따라 이진 트리를 구성한다. |
| 네트워크·그래픽 | 이진 공간 파티션(Binary Space Partition, BSP) 트리는 2D·3D 공간을 재귀적으로 분할한다. |
역사
이진 트리 개념은 그래프 이론과 초기 컴퓨터 과학에서 자연스럽게 등장하였다. 1960년대와 1970년대에 자료구조와 알고리즘 교과서에서 정형화되었으며, 1972년 G. M. A. Knuth의 The Art of Computer Programming에 상세히 다루어졌다. 이후 1970년대 후반에 AVL 트리(Georgy Adelson‑Velsky, Evgenii Landis)와 1972년의 Red‑Black 트리(Leo J. Guibas, Robert Sedgewick)와 같은 균형 이진 트리 구조가 제안되어 실용적인 성능을 보장하도록 발전하였다.
관련 개념
- 트리(자료구조): 일반적인 계층적 구조로, 루트와 여러 자식 노드를 포함한다.
- 그래프: 트리도 사이클이 없는 연결 그래프의 일종이다.
- 다진 트리(m-ary tree): 각 노드가 m개의 자식을 가질 수 있는 트리.
- 균형 트리: AVL 트리, Red‑Black 트리, 2‑3‑4 트리 등.
- 힙: 완전 이진 트리를 기반으로 한 우선순위 큐 구현체.
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison‑Wesley.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison‑Wesley.
(※ 본 문서는 2026년 현재 공개된 학술·교육 자료를 기반으로 작성되었으며, 최신 연구 동향에 대한 내용은 포함하지 않을 수 있다.)