- 탐색/삽입/삭제: 균형 잡힌 경우 \(O(\log N)\), 편향된 경우 \(O(N)\)
- 중위 순회(In-order): 항상 오름차순으로 원소를 방문한다
- Python 표준 라이브러리는 BST를 직접 제공하지 않는다 (
sortedcontainers.SortedList활용) - 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.
- 나무(tree)의 형태를 뒤집은 것과 같이 생겼다.
- 다수의 데이터를 관리하기에 적합한 트리 자료 구조의 가장 기본적인 형태
- 정렬된 데이터의 탐색, 삽입, 삭제를 평균 \(O(\log N)\) 에 수행할 수 있다.
- 데이터베이스 인덱스 구조의 기반이 되는 개념이다.
- 중위 순회를 수행하면 정렬된 순서로 데이터를 출력할 수 있다.
- 균형 이진 탐색 트리(AVL, Red-Black Tree)는 최악의 경우에도 \(O(\log N)\) 을 보장한다.
- 루트 노드(root node): 부모가 없는 최상위 노드
- 단말 노드(leaf node): 자식이 없는 노드
- 트리(tree)에서는 부모와 자식 관계가 성립한다 (직계).
- 형제 관계 (sibling, 방계): 부모 node로 부터 왼쪽 자식과 오른쪽 자식과의 관계
- 깊이(depth): 루트 노드에서의 길이(length), 루트 노드로부터 손자까지의 depth=2
- 이때, 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미한다.
- 트리의 높이(height)은 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다.
- 이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말한다.
- 다수의 데이터를 관리(조회, 저장, 삭제)하기 위한 가장 기본적인 자료구조 중 하나다.
- 이진 탐색 트리의 성질: 순서가 있음
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
- 루트 노드 기준 모든 왼쪽 노드들은 루트 노드보다 작음
- 루트 노드 기준 모든 오른쪽 노드들은 루트 노드보다 큼
- 2진 탐색을 가능하게 하는 구조
- 특정한 노드의 키(key) 값보다 그 왼쪽 자식 노드의 키(key) 값이 더 작다.
- 특정한 노드의 키(key) 값보다 그 오른쪽 자식 노드의 키(key) 값이 더 크다.
- 특정한 노드의 왼쪽 서브 트리, 오른쪽 서브 트리 모두 이진 탐색 트리다.
- worst case: 찾는게 없을 때 혹은 찾고자 하는 데이터가 가장 마지막에 있을 때
- 탐색시 재귀적으로 중앙값을 기준으로 오른쪽만 찾음
- 매 실행마다 데이터의 개수가 절반씩 줄어듬
- 그러면, 몇 번만에 사이즈가 1이 되는가?
- 수식 유도, input size를 N이라고 가정했을때
- \(N \times {(\frac{1}{2})}^{k}=1 \rightarrow N=2^k \rightarrow k = log_2N\)
- 위의 수식을 점근적 표기법으로 표현하면 \(\Theta(logN)\)
- best case: 한번에 찾았을 때
- \(\Theta(1)\)
- 그러므로, lower bound = \(\Theta(1)\), upper bound = \(O(logN)\)
- 루트 노드에서 출발하여 아래쪽으로 내려오면서, 삽입할 위치를 찾는다.
- 삽입할 노드의 키(key)가 작으면 왼쪽으로,
- 삽입할 노드의 키(key)가 크면 오른쪽으로 삽입
- 삽입할 노드 목록 예시: [7,4,5,9,6,2,3,2,8]으로 트리 생성해보기
- 루트 노드에서 출발하여 아래쪽으로 내려오면서, 찾고자 하는 원소를 조회한다. 삽입 연산과 같은 로직을 따름
- 1 삽입할 노드의 키(key)가 작으면 왼쪽으로, 2 삽입할 노드의 키(key)가 크면 오른쪽으로 조회
- 조회할 노드 목록 예시: 5번 노드
- 루트 노드에서 출발하여 아래쪽으로 내려오면서, 삭제할 원소에 접근한다.
- 삭제할 노드 목록 예시: 7번 노드
- Case #1 왼쪽 자식이 없는 경우 → 오른쪽 자식으로 대체
- Case #2 오른쪽 자식이 없는 경우 → 왼쪽 자식으로 대체
- Case #3 왼쪽, 오른쪽이 모두 있는 경우 → 오른쪽 서브
- 트리에서 가장 작은 노드로 대체
- 삭제할 노드 목록 예시: 4번 노드
- 트리에 포함되어 있는 정보를 모두 출력하고자 할 때, 어떤 방식을 사용할 수 있을까?
- 바로 순회(traversal)를 사용할 수 있다.
- 트리의 모든 노드를 특정한 순서(조건)에 따라서 방문하는 방법을 순회(traversal)라고 한다.
- 전위 순회(pre-order traverse): 루트 방문 → 왼쪽 자식 방문 → 오른쪽 자식 방문
- 중위 순회(in-order traverse): 왼쪽 자식 방문 → 루트 방문 → 오른쪽 자식 방문
- 후위 순회(post-order traverse): 왼쪽 자식 방문 → 오른쪽 자식 방문 → 루트 방문
- 전위(Pre-order): 루트 → 왼쪽 → 오른쪽 (트리 복사, 직렬화에 사용)
- 중위(In-order): 왼쪽 → 루트 → 오른쪽 (BST에서 오름차순 출력)
- 후위(Post-order): 왼쪽 → 오른쪽 → 루트 (트리 삭제, 후위 표기법에 사용)
- 전위 순회(pre-order traverse): A → B → D → E → C → F → G
- 중위 순회(in-order traverse): D → B → E → A → F → C → G
- 후위 순회(post-order traverse): D → E → B → F → G → C → A
- 방문 방법: 현재 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
- 방문 방법: 왼쪽 자식 노드 → 현재 노드 → 오른쪽 자식 노드
- 방문 방법: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 현재 노드
- 낮은 레벨(루트)부터 높은 레벨까지 순차적으로 방문한다.
- 단순히 루트 노드에서부터 너비 우선 탐색(BST)를 진행하면 된다.
- 레벨 순회 순회(level-order traverse): A → B → C → D → E → F → G
- 다른 메서드 안에서 사용되는 메서드는 이름 앞에 언더바(_) 기호를 붙인다.
- 편향 이진 트리는 다음의 두 가지 속성을 가진다.
- 같은 높이의 이진 트리 중 최소 개수의 노드 개수를 가진다.
- 왼쪽 혹은 오른쪽으로 한 방향에 대한 서브 트리를 가진다.
- 노드의 개수가 N개일 때, 시간 복잡도는 다음과 같다.
- 트리의 높이(height)을 H라고 할 때, 엄밀한 시간 복잡도는 \(O(H)\) 다.
- 이상적인 경우 H = log2 N로 볼 수 있다.
- 하지만 최악의 경우(편향된 경우) H = N로 볼 수 있다.
- AVL stands for Adelson-Velsky and Landis
- 이진 탐색 트리는 편향 트리가 될 수 있으므로, 최악의 경우 \(O(N)\) 을 요구한다.
- 반면에 AVL 트리는 균형이 갖춰진 이진 트리다.
- 간단한 구현 과정으로 완전 이진 트리에 가까운 형태를 유지하도록 한다.
- 데이터베이스 인덱스: MySQL의 B-트리 인덱스가 BST를 기반으로 범위 쿼리를 \(O(\log N)\) 에 처리한다.
- 파일 시스템: 디렉터리 구조가 트리 형태로 구성된다.
- 딥러닝 의사결정 트리: 피처 분기 구조가 이진 트리로 표현된다.
- 중위 순회 활용: BST의 중위 순회 결과가 정렬 배열이므로, 정렬된 데이터 순회에 활용된다.
- 자동완성 검색: Trie(접두사 트리)가 BST의 확장형으로 문자열 탐색을 구현한다.
1 트리(Tree)
정의: 이진 탐색 트리 (Binary Search Tree, BST)
이진 탐색 트리는 각 노드의 왼쪽 서브트리에는 더 작은 값, 오른쪽 서브트리에는 더 큰 값만 오는 이진 트리다.
2 왜 필요한가
3 트리 용어 정리
4 이진 트리(Binary Tree)
5 이진 탐색 트리(Binary Search Tree)
직관적 이해: 전화번호부 이진 탐색과 같다. 찾는 이름이 현재 페이지보다 앞이면 왼쪽 절반, 뒤면 오른쪽 절반을 탐색한다. 매번 탐색 범위가 절반으로 줄어 \(O(\log N)\) 이 된다.
BST 구조 시각화 (삽입 순서: 7, 4, 9, 2, 6):
7 ← 루트 (root)
/ \
4 9 ← 7보다 작으면 왼쪽, 크면 오른쪽
/ \
2 6 ← 4보다 작으면 왼쪽, 크면 오른쪽
탐색(6): 7→왼쪽→4→오른쪽→6 (3번 비교)
탐색(8): 7→오른쪽→9→왼쪽→없음 (3번 비교, 탐색 실패)
5.1 이진 탐색 트리(Binary Search Tree)의 성질
5.2 삽입 연산

5.3 조회 연산
5.4 삭제 연산

6 트리의 순회
트리 순회는 “어떤 순서로 모든 노드를 방문하는가”의 문제다. 루트를 언제 방문하느냐에 따라 전위/중위/후위로 나뉜다.
6.1 트리의 순회 한 눈에 보기

6.2 전위 순회(pre-order traverse)
6.3 중위 순회(Inorder Traversal)
6.4 후위 순회(Postorder Traversal)
6.5 레벨 순회(Level Order Traversal)
7 이진 탐색 트리의 구현
def search(self, node, key):
return self._search(self.root, key) # search: recursively 조회
def _search(self, node, key):
if node is None or node.key == key:
return node
# 현재 노드의 key보다 작은 경우
if node.key > key:
return self._search(node.left, key)
# 현재 노드의 key보다 큰 경우
elif node.key < key:
return self._search(node.right, key)7.1 편향 이진 트리(Skewed Binary Tree)
7.2 이진 탐색 트리의 시간 복잡도
| Number | Methods | 조회 | 삽입 | 삭제 | 수정 |
|---|---|---|---|---|---|
| 1 | 균형 잡힌 이진 탐색 트리 | \(O(logN)\) | \(O(logN)\) | \(O(logN)\) | \(O(logN)\) |
| 2 | 편향 이진 탐색 트리 | \(O(N)\) | \(O(N)\) | \(O(N)\) | \(O(N)\) |
See 표 1.
7.3 균형 잡힌 트리: AVL 트리
from collections import deque
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self, node, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None or node.key == key:
return node
# 현재 노드의 key보다 작은 경우
if node.key > key:
return self._search(node.left, key)
# 현재 노드의 key보다 큰 경우
elif node.key < key:
return self._search(node.right, key)
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return Node(key)
# 현재 노드의 key보다 작은 경우
if node.key > key:
node.left = self._insert(node.left, key)
# 현재 노드의 key보다 큰 경우
elif node.key < key:
node.right = self._insert(node.right, key)
return node
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
# 현재 노드의 key보다 작은 경우
if node.key > key:
node.left = self._delete(node.left, key)
# 현재 노드의 key보다 큰 경우
elif node.key < key:
node.right = self._delete(node.right, key)
# 삭제할 노드를 찾은 경우
else:
# 왼쪽 자식이 없는 경우
if node.left is None:
return node.right
# 오른쪽 자식이 없는 경우
elif node.right is None:
return node.left
# 왼쪽과 오른쪽 자식 모두 있는 경우
node.key = self._get_min(node.right)
node.right = self._delete(node.right, node.key)
return node
def _get_min(self, node):
key = node.key
while node.left:
key = node.left.key
node = node.left
return key
def preorder(self):
self._preorder(self.root)
def _preorder(self, node):
if node:
print(node.key, end=' ')
self._preorder(node.left)
self._preorder(node.right)
def inorder(self):
self._inorder(self.root)
def _inorder(self, node):
if node:
self._inorder(node.left)
print(node.key, end=' ')
self._inorder(node.right)
def postorder(self):
self._postorder(self.root)
def _postorder(self, node):
if node:
self._postorder(node.left)
self._postorder(node.right)
print(node.key, end=' ')
def levelorder(self):
return self._levelorder(self.root)
def _levelorder(self, node):
if node is None:
return
result = []
queue = deque()
queue.append((0, node)) # (level, node)
while queue:
level, node = queue.popleft()
if node:
result.append((level, node.key))
queue.append((level + 1, node.left))
queue.append((level + 1, node.right))
for level, key in result:
print(f"level: {level}, key: {key}")
def to_list(self):
return self._to_list(self.root)
def _to_list(self, node):
if node is None:
return []
return self._to_list(node.left) + [node.key] + self._to_list(
node.right)
arr = [7, 4, 5, 9, 6, 3, 2, 8]
bst = BinarySearchTree()
for x in arr:
bst.insert(x)
print('전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()
bst.delete(7)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()
bst.delete(4)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()
bst.delete(3)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()
print(bst.to_list())
# 출력:
# 전위 순회: 7 4 3 2 5 6 9 8
# 중위 순회: 2 3 4 5 6 7 8 9
# 후위 순회: 2 3 6 5 4 8 9 7
# [레벨 순회]
# level: 0, key: 7
# level: 1, key: 4
# level: 1, key: 9
# level: 2, key: 3
# level: 2, key: 5
# level: 2, key: 8
# level: 3, key: 2
# level: 3, key: 6
# (delete(7) 후)
# 전위 순회: 8 4 3 2 5 6 9
# 중위 순회: 2 3 4 5 6 8 9
# 후위 순회: 2 3 6 5 4 9 8
# (delete(4) 후)
# 전위 순회: 8 5 3 2 6 9
# 중위 순회: 2 3 5 6 8 9
# 후위 순회: 2 3 6 5 9 8
# (delete(3) 후)
# 전위 순회: 8 5 2 6 9
# 중위 순회: 2 5 6 8 9
# 후위 순회: 2 6 5 9 8
# [2, 5, 6, 8, 9]