자료구조
Tree트리
트리(Tree)는 노드(Node)와 간선(Edge)으로 구성된 비선형 계층 자료구조다. 하나의 루트 노드에서 시작해 가지(Branch)처럼 뻗어나가며, 사이클이 없는 연결 그래프라는 특성을 갖는다.
기본 용어
| 용어 | 설명 |
|---|---|
| 루트 (Root) | 트리의 최상위 노드. 부모가 없는 유일한 노드 |
| 부모 (Parent) | 자식 노드와 간선으로 연결된 상위 노드 |
| 자식 (Child) | 부모 노드에서 아래로 연결된 노드 |
| 형제 (Sibling) | 같은 부모를 공유하는 노드들 |
| 잎 (Leaf) | 자식이 없는 노드 (단말 노드) |
| 내부 노드 (Internal Node) | 자식이 하나 이상 있는 노드 |
| 깊이 (Depth) | 루트에서 해당 노드까지의 간선 수 |
| 높이 (Height) | 노드에서 가장 먼 잎까지의 간선 수 |
| 차수 (Degree) | 노드가 가진 자식의 수 |
| 레벨 (Level) | 깊이 + 1 (루트가 레벨 1) |
| 서브트리 (Subtree) | 특정 노드와 그 모든 자손으로 이루어진 트리 |
트리의 특성
- •노드 수가 N이면 간선 수는 정확히 N - 1
- •임의의 두 노드 사이에 정확히 하나의 경로만 존재
- •사이클(Cycle) 없음
트리 순회 (Traversal)
트리의 모든 노드를 방문하는 방법이다.
| 순회 방법 | 순서 | 결과 (위 트리) |
|---|---|---|
| 전위 (Preorder) | 루트 → 왼쪽 → 오른쪽 | A B D E C |
| 중위 (Inorder) | 왼쪽 → 루트 → 오른쪽 | D B E A C |
| 후위 (Postorder) | 왼쪽 → 오른쪽 → 루트 | D E B C A |
| 레벨 순서 (BFS) | 레벨별로 좌→우 | A B C D E |
트리의 종류
| 트리 종류 | 특징 | 주요 용도 |
|---|---|---|
| 이진 트리 (Binary Tree) | 각 노드의 자식이 최대 2개 | 일반 이진 구조 |
| 이진 탐색 트리 (BST) | 왼쪽 < 루트 < 오른쪽 | 탐색·삽입·삭제 O(log n) |
| AVL 트리 | 균형 이진 탐색 트리, 높이 차 ≤ 1 | 균형 유지 탐색 |
| 레드-블랙 트리 | 색깔 규칙으로 균형 보장 | Java TreeMap, C++ map |
| B-트리 | 다방향 균형 트리, 디스크 효율 | 데이터베이스 인덱스 |
| 트라이 (Trie) | 문자열 전용 접두사 트리 | 자동완성, 사전 |
| 세그먼트 트리 | 구간 질의·업데이트 | 범위 합, 최솟값 쿼리 |
| 펜윅 트리 (BIT) | 세그먼트 트리의 경량 버전 | 누적합 쿼리 |
| 힙 (Heap) | 부모 ≥ 자식인 완전 이진 트리 | 우선순위 큐 |
| 머클 트리 | 해시 기반 트리 | 블록체인 데이터 검증 |
구현 (Python)
트리 vs 그래프
| 항목 | 트리 | 그래프 |
|---|---|---|
| 사이클 | 없음 | 있을 수 있음 |
| 루트 | 있음 | 없음 |
| 간선 수 | N - 1 | 제한 없음 |
| 방향성 | 암묵적 (부모→자식) | 무방향/유방향 모두 가능 |
트리는 그래프의 특수한 형태(비순환 연결 그래프)다.
응용
- •파일 시스템: 디렉터리 계층 구조
- •DOM: HTML 문서의 요소 트리
- •컴파일러: 추상 구문 트리(AST)
- •데이터베이스: B-트리 기반 인덱스
- •네트워크 라우팅: 스패닝 트리(STP)
- •머신러닝: 결정 트리, 랜덤 포레스트
- •블록체인: 머클 트리로 트랜잭션 검증
