이진 트리
각 정점이 최대 2개의 자식 정점을 가지는 트리 자료구조로, Heap이나 이진 탐색 트리 같은 자료구조의 기반이 됩니다.
정의
트리는 방향이 존재하는 그래프의 일종으로, 부모 정점 아래 여러 자식 정점이 연결되고 각 자식 정점에 다시 자식 정점이 연결되는 재귀적 형태의 자료구조입니다. 그중 각 정점이 최대 2개의 자식만 가지는 트리를 이진 트리라고 합니다.
이진 트리의 종류
정점이 채워진 형태에 따라 다음과 같이 구분합니다.
- 포화 이진 트리: 마지막 레벨까지 모든 정점이 채워져 있는 트리
- 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨의 정점이 채워져 있는 트리
- 편향 이진 트리: 정점이 한 방향으로만 이어지는 트리
핵심 특징
- 정점이 N개인 경우, 최악의 경우 높이가 (N - 1)이 될 수 있습니다.
- 포화 이진 트리와 완전 이진 트리의 높이는 log N입니다.
- 높이가 h인 포화 이진 트리는 2^(h + 1) - 1개의 정점을 가집니다.
- 다른 자료구조를 만드는 데 주로 활용되며, 대표적으로 Heap과 이진 탐색 트리(BST)가 있습니다.
순회 방법
- 중위 순회(in-order): 왼쪽 정점 → 부모 정점 → 오른쪽 정점 순서로 방문
- 전위 순회(pre-order): 부모 정점 → 왼쪽 정점 → 오른쪽 정점 순서로 방문
- 후위 순회(post-order): 왼쪽 정점 → 오른쪽 정점 → 부모 정점 순서로 방문
- 층별 순회(level-order): 시작 정점의 레벨을 순서대로 방문한 뒤, 다음 레벨을 순서대로 방문
핵심 정리
이진 트리는 각 정점이 최대 2개의 자식을 갖는 재귀적 자료구조로, 채워진 형태에 따라 포화·완전·편향 이진 트리로 나뉘고 중위·전위·후위·층별 순회로 탐색합니다.