트리와 이진 탐색 트리 (Tree and BST)
트리와 이진 탐색 트리 (Tree and BST)¶
개요¶
트리는 계층적 구조를 나타내는 비선형 자료구조입니다. 이진 탐색 트리(BST)는 효율적인 탐색, 삽입, 삭제를 지원합니다.
목차¶
1. 트리 기본 개념¶
용어 정리¶
(A) ← 루트 (Root)
/ | \
(B)(C)(D) ← 내부 노드 (Internal)
/ \ \
(E)(F) (G) ← 리프 (Leaf)
- 루트: 최상위 노드 (A)
- 리프: 자식이 없는 노드 (E, F, C, G)
- 간선: 노드 연결선
- 부모/자식: A는 B의 부모, B는 A의 자식
- 형제: 같은 부모를 가진 노드 (B, C, D)
- 깊이: 루트에서의 거리 (A=0, B=1, E=2)
- 높이: 가장 깊은 리프까지 거리
이진 트리 (Binary Tree)¶
각 노드가 최대 2개의 자식을 가짐
(1)
/ \
(2) (3)
/ \ /
(4)(5)(6)
특별한 이진 트리:
- 완전 이진 트리: 마지막 레벨 제외 모두 채워짐
- 포화 이진 트리: 모든 레벨이 완전히 채워짐
- 편향 트리: 한쪽으로만 자식이 있음
노드 구조¶
// C
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// C++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
# Python
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
2. 트리 순회¶
순회 방법¶
(1)
/ \
(2) (3)
/ \
(4)(5)
전위 (Preorder): 루트 → 왼쪽 → 오른쪽
1 → 2 → 4 → 5 → 3
중위 (Inorder): 왼쪽 → 루트 → 오른쪽
4 → 2 → 5 → 1 → 3
후위 (Postorder): 왼쪽 → 오른쪽 → 루트
4 → 5 → 2 → 3 → 1
레벨 (Level-order): 레벨별로 왼쪽에서 오른쪽
1 → 2 → 3 → 4 → 5
재귀 구현¶
// C++
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " "; // 방문
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " "; // 방문
inorder(root->right);
}
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " "; // 방문
}
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
반복 구현 (스택)¶
// C++ - 중위 순회
vector<int> inorderIterative(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top();
st.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
레벨 순회 (BFS)¶
// C++
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
3. 이진 탐색 트리 (BST)¶
BST 속성¶
모든 노드에 대해:
- 왼쪽 서브트리의 모든 값 < 노드 값
- 오른쪽 서브트리의 모든 값 > 노드 값
(8)
/ \
(3) (10)
/ \ \
(1)(6) (14)
/ \ /
(4)(7)(13)
중위 순회: 1, 3, 4, 6, 7, 8, 10, 13, 14 (정렬됨!)
BST 연산 복잡도¶
┌──────────┬─────────────┬─────────────┐
│ 연산 │ 평균 │ 최악 │
├──────────┼─────────────┼─────────────┤
│ 탐색 │ O(log n) │ O(n) │
│ 삽입 │ O(log n) │ O(n) │
│ 삭제 │ O(log n) │ O(n) │
└──────────┴─────────────┴─────────────┘
최악: 편향 트리 (연결 리스트처럼 됨)
4. BST 연산¶
4.1 탐색¶
// C++
TreeNode* search(TreeNode* root, int key) {
if (!root || root->val == key)
return root;
if (key < root->val)
return search(root->left, key);
return search(root->right, key);
}
// 반복
TreeNode* searchIterative(TreeNode* root, int key) {
while (root && root->val != key) {
if (key < root->val)
root = root->left;
else
root = root->right;
}
return root;
}
def search(root, key):
if not root or root.val == key:
return root
if key < root.val:
return search(root.left, key)
return search(root.right, key)
4.2 삽입¶
5 삽입:
(8) (8)
/ \ / \
(3) (10) → (3) (10)
/ \ / \
(1)(6) (1)(6)
/
(5)
// C++
TreeNode* insert(TreeNode* root, int key) {
if (!root) return new TreeNode(key);
if (key < root->val)
root->left = insert(root->left, key);
else if (key > root->val)
root->right = insert(root->right, key);
return root;
}
def insert(root, key):
if not root:
return TreeNode(key)
if key < root.val:
root.left = insert(root.left, key)
elif key > root.val:
root.right = insert(root.right, key)
return root
4.3 삭제¶
3가지 경우:
1. 리프 노드: 그냥 삭제
2. 자식 1개: 자식으로 대체
3. 자식 2개: 후속자(inorder successor)로 대체
- 오른쪽 서브트리의 최솟값
- 또는 왼쪽 서브트리의 최댓값
(8) (8)
/ \ / \
(3) (10) → (4) (10)
/ \ / \
(1)(6) (1)(6)
/
(4)
3 삭제: 후속자 4로 대체
// C++
TreeNode* findMin(TreeNode* root) {
while (root->left)
root = root->left;
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 찾음!
if (!root->left) {
TreeNode* temp = root->right;
delete root;
return temp;
}
if (!root->right) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// 자식 2개: 후속자로 대체
TreeNode* successor = findMin(root->right);
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
return root;
}
def delete_node(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
# 후속자 찾기
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = delete_node(root.right, successor.val)
return root
5. 균형 트리 개념¶
편향 트리 문제¶
1 → 2 → 3 → 4 → 5
모든 연산이 O(n)!
균형 트리 종류¶
1. AVL 트리
- 모든 노드에서 왼쪽/오른쪽 높이 차 ≤ 1
- 삽입/삭제 시 회전으로 균형 유지
2. Red-Black 트리
- 각 노드가 빨강/검정
- 특정 규칙으로 균형 유지
- C++ map, set의 기반
3. B-트리
- 다진 탐색 트리
- 데이터베이스에서 사용
트리 높이 계산¶
def height(root):
if not root:
return -1 # 또는 0
return 1 + max(height(root.left), height(root.right))
BST 검증¶
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.val) and
is_valid_bst(root.right, root.val, max_val))
6. 연습 문제¶
문제 1: 최소 공통 조상 (LCA)¶
BST에서 두 노드의 최소 공통 조상 찾기
정답 코드
def lowest_common_ancestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
추천 문제¶
| 난이도 | 문제 | 플랫폼 | 유형 |
|---|---|---|---|
| ⭐ | 트리 순회 | 백준 | 순회 |
| ⭐⭐ | Validate BST | LeetCode | BST |
| ⭐⭐ | Binary Tree Inorder | LeetCode | 순회 |
| ⭐⭐ | 이진 검색 트리 | 백준 | BST |
| ⭐⭐⭐ | LCA | LeetCode | LCA |
다음 단계¶
- 10_Heaps_and_Priority_Queues.md - 힙, 우선순위 큐
참고 자료¶
- Tree Visualization
- Introduction to Algorithms (CLRS) - Chapter 12, 13