이진 트리 (Binary Tree)

이진 트리 (Binary Tree)

각 노드가 최대 2개의 자식(왼쪽, 오른쪽)을 가지는 트리 구조로, 재귀적 정의를 따르며 다양한 응용이 가능한 기본적인 트리 형태

목적: 계층 구조, 검색·정렬 기반, 효율적 연산, 분할 정복

특징: 최대 자식 2개, 재귀적 구조, 왼쪽/오른쪽 구분

구성요소: 노드(데이터+left+right), 루트, 리프

종류

• •완전 이진 트리(Complete): 마지막 레벨 제외 모두 채워짐, 왼쪽부터 채움, 힙
• •포화 이진 트리(Full): 모든 레벨이 꽉 참, 노드 수 = 2^(h+1) - 1 (h=간선 수)
• •균형 이진 트리(Balanced): 좌우 서브트리 높이 차이 ≤ 1, AVL, Red-Black
• •이진 탐색 트리(BST): 왼쪽 < 부모 < 오른쪽

성질

• •높이 h인 이진 트리: 최대 노드 = 2^(h+1) - 1 (h=간선 수)
• •n개 노드: 최소 높이 = ⌊log₂(n)⌋ (h=간선 수)
• •리프 개수 = 차수 2인 노드 개수 + 1

순회: 전위(Preorder), 중위(Inorder), 후위(Postorder), 레벨순서(BFS)

시간 복잡도: 탐색·삽입·삭제 O(h), 균형 트리 O(log n), 편향 트리 O(n)

공간 복잡도: O(n)

장점: 단순한 구조, 재귀적 처리, 분할 정복, 다양한 응용

단점: 불균형 시 O(n), 균형 유지 필요

적용사례: 이진 탐색 트리, 힙, 허프만 코딩, 수식 트리, 결정 트리

비교: 이진 트리(자식≤2) vs 일반 트리(자식 무제한)

연관: 트리, BST, 힙, 순회, 균형 트리