트리(Tree)

개요

트리(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트리까지 확장 가능하다. 트리 구조와 순회 방식을 정확히 이해하는 것은 효율적인 문제 해결을 위한 필수 기초 역량이다.