[CS 기초 #8] 트리 구조: 이진 트리부터 B-트리까지 완벽 정리
[CS 기초 #8] 트리 구조: 이진 트리부터 B-트리까지 완벽 정리
트리의 세계에 오신 것을 환영합니다! 계층 구조를 표현하는 가장 강력한 자료구조를 배워봅시다.
🎯 이 글을 읽고 나면
- 트리, 이진 트리, BST의 차이를 명확히 설명할 수 있습니다
- 트리 순회 (전위, 중위, 후위)를 이해하고 구현할 수 있습니다
- 이진 탐색 트리(BST)의 삽입/삭제/검색을 할 수 있습니다
- AVL 트리와 Red-Black 트리의 필요성을 이해합니다
- 파일 시스템, DOM 등 실제 활용 사례를 설명할 수 있습니다
📚 사전 지식
- 재귀 함수: 트리는 재귀로 이해하면 쉽습니다
- 스택과 큐: 이전 글: 스택과 큐 참고
- 포인터/참조 개념: 연결 리스트와 유사합니다
💡 핵심 개념 미리보기
트리(Tree)는 계층적 관계를 표현하는 자료구조로, 부모-자식 관계로 연결됩니다. 파일 시스템(폴더 구조), HTML DOM, 조직도 등이 모두 트리입니다. 이진 탐색 트리(BST)를 사용하면 O(log n) 시간에 검색할 수 있어 매우 효율적입니다!
🌳 들어가며: 트리는 어디서 사용될까?
파일 시스템, 데이터베이스 인덱스, DOM, 의사결정 트리… 이 모든 것이 트리 구조로 이루어져 있습니다!
오늘은 계층적 데이터를 효율적으로 다루는 트리(Tree) 자료구조를 깊이 있게 알아보겠습니다. 단순한 이진 트리부터 데이터베이스의 핵심인 B-트리까지 모두 다룹니다!
📐 트리의 기본 개념
트리는 계층적 관계를 표현하는 비선형 자료구조입니다.
graph TD
A[루트 노드<br/>레벨 0]
B[내부 노드<br/>레벨 1]
C[내부 노드<br/>레벨 1]
D[리프 노드<br/>레벨 2]
E[리프 노드<br/>레벨 2]
F[리프 노드<br/>레벨 2]
G[리프 노드<br/>레벨 2]
A --> B
A --> C
B --> D
B --> E
C --> F
C --> G
style A fill:#ff9999
style B fill:#99ccff
style C fill:#99ccff
style D fill:#99ff99
style E fill:#99ff99
style F fill:#99ff99
style G fill:#99ff99
트리 용어 정리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class TreeTerminology:
"""트리 용어 설명"""
def __init__(self):
self.terms = {
"노드(Node)": "트리의 기본 단위",
"루트(Root)": "트리의 최상위 노드",
"부모(Parent)": "어떤 노드의 상위 노드",
"자식(Child)": "어떤 노드의 하위 노드",
"리프(Leaf)": "자식이 없는 노드",
"내부 노드": "자식이 있는 노드",
"형제(Sibling)": "같은 부모를 가진 노드들",
"깊이(Depth)": "루트로부터의 거리",
"높이(Height)": "리프까지의 최대 거리",
"레벨(Level)": "깊이 + 1",
"차수(Degree)": "자식 노드의 개수",
"서브트리": "노드와 그 자손들로 이루어진 트리"
}
def print_terms(self):
for term, description in self.terms.items():
print(f"• {term}: {description}")
# 용어 출력
terminology = TreeTerminology()
terminology.print_terms()
🌲 이진 트리 (Binary Tree)
각 노드가 최대 2개의 자식을 가지는 트리입니다.
이진 트리 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class TreeNode:
"""트리 노드"""
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
"""이진 트리"""
def __init__(self):
self.root = None
def insert_level_order(self, arr):
"""레벨 순서로 노드 삽입"""
if not arr:
return None
self.root = TreeNode(arr[0])
queue = [self.root]
i = 1
while queue and i < len(arr):
node = queue.pop(0)
# 왼쪽 자식
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
queue.append(node.left)
i += 1
# 오른쪽 자식
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
queue.append(node.right)
i += 1
return self.root
def height(self, node=None):
"""트리의 높이"""
if node is None:
node = self.root
if node is None:
return -1
left_height = self.height(node.left)
right_height = self.height(node.right)
return max(left_height, right_height) + 1
def size(self, node=None):
"""노드 개수"""
if node is None:
node = self.root
if node is None:
return 0
return 1 + self.size(node.left) + self.size(node.right)
def is_balanced(self, node=None):
"""균형 트리인지 확인"""
if node is None:
node = self.root
if node is None:
return True
left_height = self.height(node.left)
right_height = self.height(node.right)
if abs(left_height - right_height) > 1:
return False
return self.is_balanced(node.left) and self.is_balanced(node.right)
# 이진 트리 생성
bt = BinaryTree()
bt.insert_level_order([1, 2, 3, 4, 5, 6, 7])
print(f"트리 높이: {bt.height()}")
print(f"노드 개수: {bt.size()}")
print(f"균형 트리: {bt.is_balanced()}")
트리 순회 (Tree Traversal)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class TreeTraversal:
"""트리 순회 방법들"""
def preorder(self, node, result=None):
"""전위 순회: 루트 → 왼쪽 → 오른쪽"""
if result is None:
result = []
if node:
result.append(node.data)
self.preorder(node.left, result)
self.preorder(node.right, result)
return result
def inorder(self, node, result=None):
"""중위 순회: 왼쪽 → 루트 → 오른쪽"""
if result is None:
result = []
if node:
self.inorder(node.left, result)
result.append(node.data)
self.inorder(node.right, result)
return result
def postorder(self, node, result=None):
"""후위 순회: 왼쪽 → 오른쪽 → 루트"""
if result is None:
result = []
if node:
self.postorder(node.left, result)
self.postorder(node.right, result)
result.append(node.data)
return result
def levelorder(self, root):
"""레벨 순회 (BFS)"""
if not root:
return []
result = []
queue = [root]
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.pop(0)
level_nodes.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
return result
def iterative_inorder(self, root):
"""반복적 중위 순회 (스택 사용)"""
result = []
stack = []
current = root
while stack or current:
# 왼쪽 끝까지 이동
while current:
stack.append(current)
current = current.left
# 노드 처리
current = stack.pop()
result.append(current.data)
# 오른쪽으로 이동
current = current.right
return result
# 순회 테스트
bt = BinaryTree()
root = bt.insert_level_order([1, 2, 3, 4, 5, 6, 7])
traversal = TreeTraversal()
print(f"전위 순회: {traversal.preorder(root)}")
print(f"중위 순회: {traversal.inorder(root)}")
print(f"후위 순회: {traversal.postorder(root)}")
print(f"레벨 순회: {traversal.levelorder(root)}")
🔍 이진 탐색 트리 (Binary Search Tree)
왼쪽 자식 < 부모 < 오른쪽 자식의 규칙을 따르는 트리입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class BSTNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
"""이진 탐색 트리"""
def __init__(self):
self.root = None
def insert(self, data):
"""삽입 - O(log n) average, O(n) worst"""
self.root = self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
if node is None:
return BSTNode(data)
if data < node.data:
node.left = self._insert_recursive(node.left, data)
elif data > node.data:
node.right = self._insert_recursive(node.right, data)
return node
def search(self, data):
"""검색 - O(log n) average, O(n) worst"""
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
if node is None:
return False
if data == node.data:
return True
elif data < node.data:
return self._search_recursive(node.left, data)
else:
return self._search_recursive(node.right, data)
def delete(self, data):
"""삭제 - O(log n) average, O(n) worst"""
self.root = self._delete_recursive(self.root, data)
def _delete_recursive(self, node, data):
if node is None:
return None
if data < node.data:
node.left = self._delete_recursive(node.left, data)
elif data > node.data:
node.right = self._delete_recursive(node.right, data)
else:
# 삭제할 노드 발견
# Case 1: 리프 노드
if node.left is None and node.right is None:
return None
# Case 2: 자식이 하나
if node.left is None:
return node.right
if node.right is None:
return node.left
# Case 3: 자식이 둘
# 오른쪽 서브트리의 최소값으로 대체
min_node = self._find_min(node.right)
node.data = min_node.data
node.right = self._delete_recursive(node.right, min_node.data)
return node
def _find_min(self, node):
"""최소값 찾기"""
while node.left:
node = node.left
return node
def _find_max(self, node):
"""최대값 찾기"""
while node.right:
node = node.right
return node
def find_kth_smallest(self, k):
"""k번째 작은 값 찾기"""
self.count = 0
self.result = None
self._kth_smallest_helper(self.root, k)
return self.result
def _kth_smallest_helper(self, node, k):
if node is None:
return
# 중위 순회
self._kth_smallest_helper(node.left, k)
self.count += 1
if self.count == k:
self.result = node.data
return
self._kth_smallest_helper(node.right, k)
def is_valid_bst(self, node=None, min_val=float('-inf'), max_val=float('inf')):
"""유효한 BST인지 확인"""
if node is None:
node = self.root
if node is None:
return True
if node.data <= min_val or node.data >= max_val:
return False
return (self.is_valid_bst(node.left, min_val, node.data) and
self.is_valid_bst(node.right, node.data, max_val))
# BST 테스트
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
bst.insert(val)
print(f"40 검색: {bst.search(40)}")
print(f"45 검색: {bst.search(45)}")
print(f"3번째 작은 값: {bst.find_kth_smallest(3)}")
print(f"유효한 BST: {bst.is_valid_bst()}")
bst.delete(30)
print(f"30 삭제 후 검색: {bst.search(30)}")
⚖️ 균형 이진 탐색 트리
AVL 트리
자가 균형 이진 탐색 트리로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class AVLNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
class AVLTree:
"""AVL 트리"""
def __init__(self):
self.root = None
def get_height(self, node):
"""노드 높이 반환"""
if not node:
return 0
return node.height
def get_balance(self, node):
"""균형 인수 계산"""
if not node:
return 0
return self.get_height(node.left) - self.get_height(node.right)
def rotate_right(self, y):
"""오른쪽 회전"""
x = y.left
T2 = x.right
# 회전
x.right = y
y.left = T2
# 높이 업데이트
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
def rotate_left(self, x):
"""왼쪽 회전"""
y = x.right
T2 = y.left
# 회전
y.left = x
x.right = T2
# 높이 업데이트
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, data):
"""삽입 - O(log n)"""
self.root = self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
# 1. 일반 BST 삽입
if not node:
return AVLNode(data)
if data < node.data:
node.left = self._insert_recursive(node.left, data)
elif data > node.data:
node.right = self._insert_recursive(node.right, data)
else:
return node # 중복 허용 안 함
# 2. 높이 업데이트
node.height = 1 + max(self.get_height(node.left),
self.get_height(node.right))
# 3. 균형 인수 확인
balance = self.get_balance(node)
# 4. 불균형 처리 (4가지 경우)
# Left-Left
if balance > 1 and data < node.left.data:
return self.rotate_right(node)
# Right-Right
if balance < -1 and data > node.right.data:
return self.rotate_left(node)
# Left-Right
if balance > 1 and data > node.left.data:
node.left = self.rotate_left(node.left)
return self.rotate_right(node)
# Right-Left
if balance < -1 and data < node.right.data:
node.right = self.rotate_right(node.right)
return self.rotate_left(node)
return node
def print_tree(self, node=None, level=0, prefix="Root: "):
"""트리 시각화"""
if node is None:
node = self.root
if node:
print(" " * (level * 4) + prefix + str(node.data) +
f" (h={node.height}, b={self.get_balance(node)})")
if node.left or node.right:
if node.left:
self.print_tree(node.left, level + 1, "L--- ")
else:
print(" " * ((level + 1) * 4) + "L--- None")
if node.right:
self.print_tree(node.right, level + 1, "R--- ")
else:
print(" " * ((level + 1) * 4) + "R--- None")
# AVL 트리 테스트
avl = AVLTree()
values = [10, 20, 30, 40, 50, 25]
for val in values:
avl.insert(val)
print(f"\n{val} 삽입 후:")
avl.print_tree()
🔴 레드-블랙 트리
자가 균형 이진 탐색 트리의 또 다른 종류입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class RBNode:
def __init__(self, data, color="RED"):
self.data = data
self.color = color # RED or BLACK
self.left = None
self.right = None
self.parent = None
class RedBlackTree:
"""레드-블랙 트리 (간단한 구현)"""
def __init__(self):
self.nil = RBNode(None, "BLACK") # NIL 노드
self.root = self.nil
def rotate_left(self, x):
"""왼쪽 회전"""
y = x.right
x.right = y.left
if y.left != self.nil:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def insert(self, data):
"""삽입"""
node = RBNode(data)
node.left = self.nil
node.right = self.nil
parent = None
current = self.root
# BST 삽입
while current != self.nil:
parent = current
if node.data < current.data:
current = current.left
else:
current = current.right
node.parent = parent
if parent == None:
self.root = node
elif node.data < parent.data:
parent.left = node
else:
parent.right = node
# 레드-블랙 속성 복구
if node.parent == None:
node.color = "BLACK"
return
if node.parent.parent == None:
return
self._fix_insert(node)
def _fix_insert(self, node):
"""삽입 후 속성 복구"""
while node.parent.color == "RED":
if node.parent == node.parent.parent.right:
uncle = node.parent.parent.left
if uncle.color == "RED":
# Case 1: 삼촌이 빨간색
uncle.color = "BLACK"
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
# Case 2, 3: 삼촌이 검은색
if node == node.parent.left:
node = node.parent
self.rotate_right(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self.rotate_left(node.parent.parent)
else:
# 대칭 케이스
uncle = node.parent.parent.right
if uncle.color == "RED":
uncle.color = "BLACK"
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
self.rotate_left(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self.rotate_right(node.parent.parent)
if node == self.root:
break
self.root.color = "BLACK"
🌴 힙 (Heap)
완전 이진 트리로, 부모가 자식보다 크거나(Max Heap) 작은(Min Heap) 특성을 가집니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class MaxHeap:
"""최대 힙"""
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, value):
"""삽입 - O(log n)"""
self.heap.append(value)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, i):
"""위로 재정렬"""
parent = self.parent(i)
if i > 0 and self.heap[i] > self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
self._heapify_up(parent)
def extract_max(self):
"""최대값 추출 - O(log n)"""
if not self.heap:
return None
if len(self.heap) == 1:
return self.heap.pop()
max_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return max_val
def _heapify_down(self, i):
"""아래로 재정렬"""
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self._heapify_down(largest)
def build_heap(self, arr):
"""배열로부터 힙 구성 - O(n)"""
self.heap = arr.copy()
# 마지막 내부 노드부터 시작
for i in range(len(self.heap) // 2 - 1, -1, -1):
self._heapify_down(i)
def heap_sort(self, arr):
"""힙 정렬 - O(n log n)"""
self.build_heap(arr)
sorted_arr = []
while self.heap:
sorted_arr.insert(0, self.extract_max())
return sorted_arr
# 힙 테스트
heap = MaxHeap()
values = [3, 7, 2, 9, 1, 5, 8]
for val in values:
heap.insert(val)
print(f"힙: {heap.heap}")
# 힙 정렬
arr = [3, 7, 2, 9, 1, 5, 8]
heap2 = MaxHeap()
sorted_arr = heap2.heap_sort(arr)
print(f"정렬 결과: {sorted_arr}")
🗂️ B-트리
데이터베이스와 파일 시스템에서 사용되는 자가 균형 트리입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class BTreeNode:
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
def split(self, parent, index):
"""노드 분할"""
new_node = BTreeNode(self.leaf)
mid = len(self.keys) // 2
new_node.keys = self.keys[mid + 1:]
self.keys = self.keys[:mid]
if not self.leaf:
new_node.children = self.children[mid + 1:]
self.children = self.children[:mid + 1]
parent.keys.insert(index, self.keys[mid])
parent.children.insert(index + 1, new_node)
class BTree:
"""B-트리 (간단한 구현)"""
def __init__(self, degree=3):
self.root = BTreeNode()
self.degree = degree # 최소 차수
def search(self, key, node=None):
"""검색 - O(log n)"""
if node is None:
node = self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return True
if node.leaf:
return False
return self.search(key, node.children[i])
def insert(self, key):
"""삽입 - O(log n)"""
root = self.root
if len(root.keys) >= 2 * self.degree - 1:
# 루트가 가득 찬 경우
new_root = BTreeNode(leaf=False)
new_root.children.append(self.root)
root.split(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _insert_non_full(self, node, key):
"""노드가 가득 차지 않은 경우 삽입"""
i = len(node.keys) - 1
if node.leaf:
# 리프 노드에 삽입
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
# 내부 노드
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) >= 2 * self.degree - 1:
# 자식이 가득 찬 경우
node.children[i].split(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key)
def print_tree(self, node=None, level=0):
"""트리 출력"""
if node is None:
node = self.root
print(f"{' ' * level}Level {level}: {node.keys}")
if not node.leaf:
for child in node.children:
self.print_tree(child, level + 1)
# B-트리 테스트
btree = BTree(degree=3)
values = [10, 20, 5, 6, 12, 30, 7, 17]
for val in values:
btree.insert(val)
print(f"\n{val} 삽입 후:")
btree.print_tree()
🌲 트라이 (Trie)
문자열 검색에 특화된 트리 구조입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
"""트라이 (Prefix Tree)"""
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""단어 삽입 - O(m), m = 단어 길이"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
"""단어 검색 - O(m)"""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
"""접두사 검색 - O(m)"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def auto_complete(self, prefix):
"""자동 완성"""
node = self.root
# 접두사까지 이동
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
# 모든 단어 수집
words = []
self._collect_words(node, prefix, words)
return words
def _collect_words(self, node, prefix, words):
"""재귀적으로 단어 수집"""
if node.is_end_of_word:
words.append(prefix)
for char, child_node in node.children.items():
self._collect_words(child_node, prefix + char, words)
# 트라이 테스트
trie = Trie()
words = ["apple", "app", "apricot", "application", "apply", "banana", "band"]
for word in words:
trie.insert(word)
print(f"'app' 검색: {trie.search('app')}")
print(f"'appl' 검색: {trie.search('appl')}")
print(f"'app'로 시작: {trie.starts_with('app')}")
print(f"'app' 자동완성: {trie.auto_complete('app')}")
💡 실전 문제 풀이
문제 1: 이진 트리 직렬화/역직렬화
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def serialize(root):
"""이진 트리를 문자열로 직렬화"""
if not root:
return "null"
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(str(node.data))
queue.append(node.left)
queue.append(node.right)
else:
result.append("null")
# 마지막 null들 제거
while result and result[-1] == "null":
result.pop()
return ",".join(result)
def deserialize(data):
"""문자열을 이진 트리로 역직렬화"""
if not data or data == "null":
return None
values = data.split(",")
root = TreeNode(int(values[0]))
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] != "null":
node.left = TreeNode(int(values[i]))
queue.append(node.left)
i += 1
if i < len(values) and values[i] != "null":
node.right = TreeNode(int(values[i]))
queue.append(node.right)
i += 1
return root
문제 2: 최소 공통 조상 (LCA)
1
2
3
4
5
6
7
8
9
10
11
12
def lowest_common_ancestor(root, p, q):
"""이진 트리에서 두 노드의 최소 공통 조상 찾기"""
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else right
🎯 핵심 정리
꼭 기억해야 할 5가지
- 트리는 계층적 관계를 표현하는 비선형 구조
- BST는 효율적인 검색을 위한 정렬된 트리
- AVL/RB 트리는 자가 균형으로 O(log n) 보장
- 힙은 우선순위 큐 구현에 최적
- B-트리는 디스크 I/O 최적화된 트리
실무 활용 팁
- 빠른 검색이 필요하면 → BST, AVL
- 우선순위 처리가 필요하면 → 힙
- 문자열 검색/자동완성 → 트라이
- 데이터베이스 인덱스 → B-트리
📚 추가 학습 자료
추천 문제
- LeetCode: Binary Tree Inorder Traversal, Validate BST
- 프로그래머스: 이진 탐색 트리
- 백준: 1991(트리 순회), 2250(트리의 높이와 너비)
🚀 다음 시간 예고
다음 포스트에서는 그래프(Graph)를 다룹니다. DFS, BFS부터 최단 경로 알고리즘까지 알아보겠습니다!
📌 시리즈 네비게이션
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.