트리(Tree)란?
트리는 사이클이 없는 그래프의 특수한 형태로,
정점(Node, 노드)과 이를 연결하는 간선(Link, branch)으로 구성됩니다.
- 노드(Node): 트리의 기본 단위
- 루트 노드(Root node): 트리의 시작점
- 단말 노드(Leaf node): 자식이 없는 노드
- 비단말 노드(Non-terminal node): 자식이 하나 이상 있는 노드
- 부모(Parent) / 자식(Child) 노드: 상위-하위 관계를 가지는 노드
- 형제(Sibling): 같은 부모를 공유하는 노드
- 레벨(Level): 루트의 레벨을 1로 했을 때, 아래로 내려가며 1씩 증가
- 깊이(Depth, Height): 트리에서 가질 수 있는 최대 레벨
- 차수(Degree): 한 노드에서 뻗어나가는 자식 수
- 숲(Forest): 여러 개의 트리 집합
- 이진 트리(Binary Tree)
- 이진 트리는 모든 노드의 차수가 최대 2 이하인 트리입니다. 즉, 각 노드는 최대 왼쪽 자식(Left Child), 오른쪽 자식(Right Child) 두 개만 가질 수 있습니다.
특징
레벨 i에서 최대 노드 수는 2^(i-1)
단말 노드 수 n₀와 차수가 2인 노드 수 n₂ 사이에는 항상 n₀ = n₂ + 1 성립
배열로 표현 가능 (완전 이진 트리의 경우 null 없이 표현됨)
주요 활용
표현식 트리(Expression Tree): 수학식을 트리 구조로 표현
이진 힙(Binary Heap): 우선순위 큐 구현
게임 상태 트리: 체스나 틱택토 같은 게임에서 AI 의사결정
시간 복잡도
삽입 / 삭제 / 탐색:
최선(균형 트리): O(log n)
최악(편향 트리): O(n)
이진 트리의 종류
- 정 이진 트리(Full Binary Tree)
모든 노드가 0개 또는 2개의 자식을 가짐 - 포화 이진 트리(Perfect Binary Tree)
모든 노드가 2개의 자식을 가지고, 리프 노드가 모두 같은 레벨에 존재 - 완전 이진 트리(Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽에서 오른쪽 순서대로 채워짐
순회(Traversal) 방법
- 전위 순회 (Preorder: Root → Left → Right)
사용 예: 트리 복사, 디렉토리 구조 출력 - 중위 순회 (Inorder: Left → Root → Right)
사용 예: 이진 탐색 트리에서 정렬된 순서 출력 - 후위 순회 (Postorder: Left → Right → Root)
사용 예: 폴더/파일 크기 계산 - 레벨 순회 (Level-order: BFS)
사용 예: 최단 경로 탐색
이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리는 이진 트리 구조에 탐색 규칙을 부여한 것입니다.
왼쪽 자식 < 부모 < 오른쪽 자식
탐색, 삽입, 삭제 모두 평균 O(log n)
편향될 경우 최악 O(n)
활용 예
데이터베이스 인덱스
사전(Dictionary)
집합(Set)
균형 이진 탐색 트리 (Balanced BST)
BST가 한쪽으로 치우치면 O(n)이 되므로, 균형을 유지하는 트리 구조가 필요합니다.
AVL 트리: 모든 노드의 균형 인수(Balance factor)가 -1, 0, 1을 유지
레드-블랙 트리: 각 노드에 색(빨강/검정)을 두어 규칙을 통해 균형 유지
이 구조들은 항상 O(log n) 성능을 보장합니다.
게임 개발에서의 활용 예시
게임 상태 관리 – 체스, 바둑 등에서 가능한 모든 상태 탐색
AI 결정 트리 – 승률 계산 및 최적 수 선택
점수/랭킹 시스템 – 빠른 검색, 삽입, 삭제
경로 탐색 – A* 알고리즘에서 이진 힙 활용
자원 관리 – 아이템, 이벤트를 빠르게 검색 및 업데이트
장단점 정리
✅ 장점
구조적 탐색이 가능
배열 기반으로 단순 표현 가능
❌ 단점
불균형 트리일 경우 탐색 성능 저하텍스트
배열 표현 시 삽입/삭제에 비효율 발생
