Topic
트리(Tree)
JackerLab
2025. 3. 29. 20:59
728x90
반응형
개요
트리(Tree)는 노드(Node)와 간선(Edge)로 구성된 계층적 비선형 자료구조로, 하나의 루트 노드(Root)에서 시작하여 자식 노드로 분기되는 구조를 가진다. 트리는 컴퓨터 과학에서 데이터 분류, 탐색, 계층 구조 표현 등 매우 널리 사용되며, 이진 트리, 이진 탐색 트리, 힙, 트라이, AVL 트리, B트리 등 다양한 종류가 있다.
1. 트리의 개념과 구성 요소
| 구성 요소 | 설명 |
| 노드(Node) | 데이터를 담는 기본 단위 |
| 루트(Root) | 트리의 시작 노드 (부모가 없음) |
| 부모(Parent), 자식(Child) | 노드 간 관계 정의 |
| 리프(Leaf) | 자식이 없는 마지막 노드 |
| 서브트리(Subtree) | 특정 노드를 루트로 하는 부분 트리 |
| 간선(Edge) | 노드 간 연결 관계 |
2. 트리의 특성
| 특성 | 설명 |
| 비선형 구조 | 노드 간 관계가 계층적이며 일방향적 |
| 순환 없음 | 트리는 사이클이 없는 그래프 |
| 노드 수 vs 간선 수 | 간선 수 = 노드 수 - 1 |
| 재귀적 구조 | 각 노드는 자신을 루트로 하는 트리를 가질 수 있음 |
3. 트리의 종류
| 종류 | 설명 |
| 이진 트리 | 모든 노드가 최대 2개의 자식을 가짐 |
| 이진 탐색 트리(BST) | 왼쪽 < 루트 < 오른쪽 조건 만족 |
| 완전 이진 트리 | 마지막 레벨을 제외하고 모든 레벨이 채워짐 |
| 포화 이진 트리 | 모든 레벨이 완전히 채워짐 |
| 균형 이진 트리 | 좌우 서브트리 높이 차이가 최소 |
| 힙(Heap) | 최대값 또는 최소값이 루트에 위치 |
| 트라이(Trie) | 문자열 검색을 위한 트리 구조 |
| B-트리 | 다진 트리, 디스크 기반 탐색에 효율적 |
4. 파이썬 이진 트리 구현 예시
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# 트리 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)5. 트리 순회 방식 (Traversal)
| 순회 방식 | 순서 |
| 전위 순회 (Preorder) | 루트 → 왼쪽 → 오른쪽 |
| 중위 순회 (Inorder) | 왼쪽 → 루트 → 오른쪽 (BST 오름차순) |
| 후위 순회 (Postorder) | 왼쪽 → 오른쪽 → 루트 |
| 레벨 순회 (Level-order) | 위에서 아래로, 왼쪽부터 (BFS 기반) |
6. 시간 및 공간 복잡도
| 연산 | 복잡도 (일반 트리 기준) |
| 삽입, 삭제, 탐색 | O(n) |
| 이진 탐색 트리(BST) 탐색 | 평균 O(log n), 최악 O(n) |
| 균형 BST (AVL, Red-Black) | O(log n) |
7. 트리의 활용 사례
| 분야 | 활용 예시 |
| 데이터베이스 | 인덱스(B-트리, B+트리) |
| 운영체제 | 파일 디렉터리 구조 |
| 네트워크 | 라우팅 트리, 멀티캐스트 경로 구성 |
| 문자열 검색 | Trie, Ternary Tree |
| 게임 개발 | 상태 공간 탐색 (Minimax Tree) |
| UI 구조 | DOM 트리, 컴포넌트 트리 |
8. 결론
트리는 다양한 문제를 계층적, 논리적으로 표현하고 탐색하는 데 매우 적합한 자료구조이다. 트리는 알고리즘, 시스템, 인공지능, 웹 개발 등 모든 분야에서 핵심적으로 사용되며, 이진 트리를 시작으로 트라이, 힙, B트리까지 확장 가능하다. 트리 구조와 순회 방식을 정확히 이해하는 것은 효율적인 문제 해결을 위한 필수 기초 역량이다.
728x90
반응형