[알고리즘] 트리 구조
트리 구조
루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재
리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다
비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드
자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.
부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다
형제 : 부모가 같은 노드를 형제라 한다
조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다
자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다
레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 레벨은 0
차수 : 각 노드가 갖는 자식의 수 (degree). 모든 노드의 차수가 n 이하인 트리를 n진 트리라 한다
높이 : 루트에서 가장 멀리있는 리프까지의 거리. 리프 레벨의 최댓값을 높이라 한다
서브 트리 : 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리를 서브 트리라 한다
빈 트리 : 노드와 가지가 전혀 없는 트리를 빈 트리 또는 널 트리(null)이라 한다
노드 : 그래프의 점. 데이터를 담는 단위 (vertex) 보통 트리에서는 노드, 그래프에서는 정점이라 표현
간선 : 정점과 정점을 연결하는 선 (edge)
호 : 방향이 있는 간선 (arc). 유향 그래프 (directed graph)에서 쓰는 용어. 방향이 있는 간선은 Arc ≠ 일반 edge
순서 트리와 무순서 트리
순서 트리 (ordered tree) : 형제 노드의 순서관계가 있는 트리
무순서 트리 : 형제 노드의 순서 관계를 구분하지 않는 트리
Sparse vs Dense
정점 수: V, 간선 수: E일 때,
| 그래프 유형 | 간선 수 조건 | 특징 |
| Sparse (희소 그래프) | E ≪ V² (보통 O(V)) | 정점은 많지만 연결은 적음 |
| Dense (밀집 그래프) | E ≈ V² (거의 최대치) | 정점 대부분이 연결돼 있음 |
✅ 왜 중요한가 : 알고리즘 선택의 기준이 된다
Sparse : 크루스칼 (간선 정렬 후 선택), 다익스트라 (인접 리스트)
Dense : Prim (인접 행렬), Floyd-W ( $O(V^3)$ )
순서 트리의 검색
너비 우선 검색 (BFS)
aka 폭 우선 검색, 가로 검색, 수평 검색
낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법
깊이 우선 검색 (DFS)
aka 세로 검색, 수직 검색
리프에 도달할 때 까지 아래쪽으로 내려가면서 검색한다
리프에 도달해서 더이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다
스캔 과정에서 e노드를 몇번 지나갔는지 본다면 아래와 같다. 깊이 우선 탐색에서는 같은 노드를 최대 3번 지나갈 수 있다.
e → i : 전위 순회 (e에서 i로 내려가기 직전에 e를 1번 지나간다)
i → j : 중위순회 (i에서 j로 지나가는 도중에 e를 1번 지나간다)
j → e : 후위 순회 (j에서 e로 돌아올 때 e를 1번 지나간다)
트리의 순회 방법
- 전위 순회 (preorder traversal) : 노드 방문 → 왼쪽 자식 → 오른쪽 자식
- 중위 순회 (inorder traversal) : 왼쪽 자식 → 노드 방문 → 오른쪽 자식
- 후위 순회 (postorder traversal) : 왼쪽 자식 → 오른쪽 자식 → 노드 방문
왜 이런 순회가 나뉘는가?
연산자를 루트로 두고 , 중위순회 방식이다. 1+ 2+ 3 을 사람이 쓴다
컴퓨터는 1 2 + 3 + 로 연산하고 후위순회 한다
이진 트리와 이진 검색 트리
이진 트리
노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 무관
특징은 왼쪽 자식과 오른쪽 자식을 구분한다..?
왼쪽 자식을 루트로 하는 서브트리를 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리라 한다
완전 이진 트리
루트부터 아래쪽 레벨로 노드가 가득 차있고 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리
높이가 k인 완전 이진 트리가 가질 수 있는 노드의 수는 최대 $2^{k+1} + 1$ 개
n개의 노드를 저장할 수 있는 완전 이진 트리이의 높이는 $log n$
균형 검색 트리
높이를 O(log n)으로 제한하여 고안된 검색 트리
이진 균형 검색 트리의 예시로는 AVL 트리, 레드-블랙 트리
이진이 아닌 균형 검색 트리 예시로는 B 트리, 2-3 트리
이진 검색 트리
모든 노드가 다음 조건을 만족해야 한다
- 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 합니다
- 오른쪽 서브트리 노드의 키값은 자신의 노드 커야 한다
이진 검색 트리의 특징
- 구조가 단순하다
- 중위 순회의 깉이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다
- 이진 검색과 비슷한 방식으로 아주 빠르게 검색 가능하다
- 노드 삽입이 쉽다
트리 종류
| 용어 | 설명 |
| 이진 트리 (Binary Tree) | 모든 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리 |
| 포화 이진 트리 (Full Binary Tree) | 모든 노드가 0개 또는 2개의 자식만 가짐 (중간에 1개만 가지면 ❌) |
| 완전 이진 트리 (Complete Binary Tree) | 마지막 레벨을 제외한 모든 레벨이 노드로 꽉 차 있고, 마지막은 왼쪽부터 채워짐 |
| 정 이진 트리 (Proper / Strict Binary Tree) | 포화 이진 트리와 유사. 모든 노드가 자식이 없거나 정확히 2개 가짐 |
| 균형 이진 트리 (Balanced Binary Tree) | 왼쪽/오른쪽 서브트리의 높이 차이가 일정 이하 (보통 1 이하) |
| 이진 탐색 트리 (BST) | 왼쪽 < 현재 노드 < 오른쪽 조건을 만족하는 이진 트리 |
| AVL 트리 | 스스로 균형을 유지하는 BST. 삽입/삭제 시 자동으로 회전해서 균형 조정 |
| 레드-블랙 트리 | 균형 잡힌 BST의 일종. 색상 규칙으로 균형 유지 (운영체제, Java TreeMap 등에서 씀) |
| 힙 (Heap) | 완전 이진 트리 구조 + 부모-자식 간 크기 규칙 만족 (최대/최소 힙) |
| 트라이 (Trie) | 문자열 검색용 트리 (접두사 구조). 사전/자동완성 등에 사용 |
| 세그먼트 트리 | 구간 합, 구간 최대값 등을 빠르게 계산할 수 있는 트리 (알고리즘 문제에서 자주 등장) |
트리의 차이점 정리
| 이름 | 자식 수 제한 | 노드 배치 조건 | 균형 조건 | 주요 용도 |
| 이진 트리 | 최대 2개 | 없음 | 없음 | 기본 트리 구조 |
| 완전 이진 트리 | 최대 2개 | 마지막 레벨 왼쪽부터 채움 | ❌ | 힙 구현에 사용 |
| 포화 이진 트리 | 0개 또는 2개 | 모든 레벨 꽉 참 | ❌ | 이론적 모델 |
| 균형 이진 트리 | 최대 2개 | 없음 | ✅ 왼/오 높이 비슷 | 효율적 탐색 |
| BST | 최대 2개 | 왼쪽 < 루트 < 오른쪽 | ❌ (균형 아님) | 탐색, 삽입, 삭제 |
| AVL 트리 | 최대 2개 | BST 규칙 + 균형 유지 | ✅ (높이차 ≤ 1) | 항상 O(log N) 탐색 |
| 레드-블랙 트리 | 최대 2개 | BST + 색상 규칙 | ✅ | 시스템, 라이브러리 |
| 힙 | 최대 2개 | 완전 이진 트리 + 부모 > 자식 (또는 <) | ❌ | 우선순위 큐 |
| 트라이 | 자식 제한 없음 | 문자 단위로 자식 | ❌ | 문자열 검색 |
| 세그먼트 트리 | 2개 | 구간 쪼개서 노드 구성 | ❌ | 알고리즘에서 구간 처리 |