개념
왼쪽 < 부모 < 오른쪽 규칙을 만족하는 이진 트리
효율적인 탐색, 삽입, 삭제를 위한 정렬된 트리 구조
BST의 특징
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
규칙
- 왼쪽 서브트리: 부모보다 작은 값
- 오른쪽 서브트리: 부모보다 큰 값
- 중위 순회: 오름차순으로 정렬
시간복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
최악의 경우: 편향 트리 (한쪽으로만 치우침)
장점과 단점
장점
- 빠른 탐색: 평균
O(log n) - 정렬 유지: 중위 순회로 정렬된 순서
- 범위 검색: 특정 범위의 값을 효율적으로 찾기
단점
- 편향 가능: 최악의 경우
O(n) - 균형 유지 불가: 삽입 순서에 따라 성능 저하
- 해결책: AVL 트리, Red-Black 트리 등 자가 균형 트리
Python 구현
1. BST 클래스
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None2. 삽입 (Insert)
def insert(self, val):
self.root = self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
# Base Case: 빈 자리 발견
if not node:
return TreeNode(val)
# 값 비교하여 왼쪽/오른쪽 결정
if val < node.val:
node.left = self._insert_recursive(node.left, val)
elif val > node.val:
node.right = self._insert_recursive(node.right, val)
# val == node.val이면 중복이므로 삽입 안 함
return node
# 반복문 버전
def insert_iterative(self, val):
if not self.root:
self.root = TreeNode(val)
return
current = self.root
while True:
if val < current.val:
if not current.left:
current.left = TreeNode(val)
break
current = current.left
elif val > current.val:
if not current.right:
current.right = TreeNode(val)
break
current = current.right
else:
break # 중복
# 시간복잡도: O(log n) 평균, O(n) 최악3. 탐색 (Search)
def search(self, val):
return self._search_recursive(self.root, val)
def _search_recursive(self, node, val):
# Base Case
if not node or node.val == val:
return node
# 값 비교
if val < node.val:
return self._search_recursive(node.left, val)
else:
return self._search_recursive(node.right, val)
# 반복문 버전
def search_iterative(self, val):
current = self.root
while current:
if val == current.val:
return current
elif val < current.val:
current = current.left
else:
current = current.right
return None
# 시간복잡도: O(log n) 평균, O(n) 최악4. 삭제 (Delete)
def delete(self, val):
self.root = self._delete_recursive(self.root, val)
def _delete_recursive(self, node, val):
if not node:
return None
# 값 찾기
if val < node.val:
node.left = self._delete_recursive(node.left, val)
elif val > node.val:
node.right = self._delete_recursive(node.right, val)
else:
# 삭제할 노드 발견
# Case 1: 자식이 없거나 하나만 있는 경우
if not node.left:
return node.right
if not node.right:
return node.left
# Case 2: 자식이 둘 다 있는 경우
# 오른쪽 서브트리의 최솟값을 찾아 대체
min_node = self._find_min(node.right)
node.val = min_node.val
node.right = self._delete_recursive(node.right, min_node.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
# 시간복잡도: O(log n) 평균, O(n) 최악5. 순회 및 유틸리티
def inorder(self):
"""중위 순회: 오름차순 정렬"""
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node.left, result)
result.append(node.val)
self._inorder_recursive(node.right, result)
def find_min(self):
"""최솟값 찾기"""
if not self.root:
return None
current = self.root
while current.left:
current = current.left
return current.val
def find_max(self):
"""최댓값 찾기"""
if not self.root:
return None
current = self.root
while current.right:
current = current.right
return current.val자주 나오는 문제 유형
1. BST 검증
문제: 주어진 트리가 유효한 BST인지 확인
def is_valid_bst(root):
def validate(node, min_val, max_val):
if not node:
return True
# 범위 체크
if node.val <= min_val or node.val >= max_val:
return False
# 왼쪽은 max를 현재 노드로, 오른쪽은 min을 현재 노드로
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
# 시간복잡도: O(n)
# 공간복잡도: O(h) - h: 높이핵심: 각 노드가 유효한 범위 내에 있는지 확인
2. K번째로 작은 원소
문제: BST에서 K번째로 작은 원소 찾기
def kth_smallest(root, k):
# 중위 순회로 k번째 원소 찾기
count = 0
result = None
def inorder(node):
nonlocal count, result
if not node or result is not None:
return
# 왼쪽 방문
inorder(node.left)
# 현재 노드 처리
count += 1
if count == k:
result = node.val
return
# 오른쪽 방문
inorder(node.right)
inorder(root)
return result
# 시간복잡도: O(k)
# 공간복잡도: O(h)핵심: 중위 순회로 오름차순 접근, K번째에서 중단
3. BST를 균형 BST로 변환
문제: 정렬된 배열을 높이 균형 BST로 변환
def sorted_array_to_bst(nums):
def build(left, right):
if left > right:
return None
# 중간값을 루트로
mid = (left + right) // 2
node = TreeNode(nums[mid])
# 재귀적으로 서브트리 생성
node.left = build(left, mid - 1)
node.right = build(mid + 1, right)
return node
return build(0, len(nums) - 1)
# 테스트
# nums = [-10, -3, 0, 5, 9]
# 0
# / \
# -3 9
# / /
# -10 5
# 시간복잡도: O(n)
# 공간복잡도: O(log n)핵심: 중간값을 루트로 하여 균형 유지
4. 두 BST 노드의 합
문제: BST에서 합이 K가 되는 두 노드 찾기
def find_target(root, k):
# 중위 순회로 정렬된 리스트 생성
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
nums = inorder(root)
# 투 포인터로 합 찾기
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == k:
return True
elif total < k:
left += 1
else:
right -= 1
return False
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: BST를 정렬된 배열로 변환 후 투 포인터
5. BST에서 범위 합
문제: L 이상 R 이하 값의 합 구하기
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
# 현재 노드가 범위 내
if low <= root.val <= high:
total += root.val
# 왼쪽 탐색 (현재 값이 low보다 크면)
if root.val > low:
total += range_sum_bst(root.left, low, high)
# 오른쪽 탐색 (현재 값이 high보다 작으면)
if root.val < high:
total += range_sum_bst(root.right, low, high)
return total
# 테스트
# 10
# / \
# 5 15
# / \ \
# 3 7 18
# range_sum_bst(root, 7, 15) → 32 (7 + 10 + 15)
# 시간복잡도: O(n)핵심: BST 특성을 이용한 가지치기
6. BST의 최소 공통 조상 (LCA)
문제: BST에서 두 노드의 최소 공통 조상 찾기
def lowest_common_ancestor_bst(root, p, q):
# p와 q가 모두 왼쪽에 있으면 왼쪽으로
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor_bst(root.left, p, q)
# p와 q가 모두 오른쪽에 있으면 오른쪽으로
if p.val > root.val and q.val > root.val:
return lowest_common_ancestor_bst(root.right, p, q)
# 분기점 → 현재 노드가 LCA
return root
# 반복문 버전
def lca_iterative(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
# 시간복잡도: O(h) - h: 높이
# 공간복잡도: O(1) - 반복문핵심: BST 특성으로 일반 트리의 O(n)을 O(h)로 개선
추천 연습 문제
기초
중급
- LeetCode 98 - Validate BST
- LeetCode 230 - Kth Smallest Element
- LeetCode 108 - Convert Sorted Array to BST
- LeetCode 653 - Two Sum IV
고급
- LeetCode 450 - Delete Node in BST
- LeetCode 938 - Range Sum of BST
- LeetCode 235 - Lowest Common Ancestor of BST
핵심 요약
| 개념 | 설명 |
|---|---|
| BST 규칙 | 왼쪽 < 부모 < 오른쪽 |
| 중위 순회 | 오름차순 정렬 |
| 평균 시간 | O(log n) |
| 최악 시간 | O(n) - 편향 트리 |
BST vs 이진 트리
| 특성 | 이진 트리 | BST |
|---|---|---|
| 정렬 | 없음 | 있음 |
| 탐색 | O(n) | O(log n) 평균 |
| 삽입 | O(1) | O(log n) 평균 |
| 중위 순회 | 임의 순서 | 오름차순 |
BST 문제 해결 패턴
1. 범위 검증 패턴
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))2. BST → 정렬 배열 패턴
def inorder_to_array(root):
result = []
def inorder(node):
if node:
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result3. 정렬 배열 → BST 패턴
def array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = array_to_bst(nums[:mid])
root.right = array_to_bst(nums[mid+1:])
return rootBST 최적화
균형 잡힌 BST
# AVL 트리, Red-Black 트리 등으로 균형 유지
# Python의 sortedcontainers.SortedDict 사용 가능
from sortedcontainers import SortedDict
sd = SortedDict()
sd[3] = 'three'
sd[1] = 'one'
sd[2] = 'two'
print(list(sd.keys())) # [1, 2, 3]BST vs Hash Table
| 특성 | BST | Hash Table |
|---|---|---|
| 탐색 | O(log n) | O(1) |
| 정렬 | 유지 | 없음 |
| 범위 검색 | 효율적 | 비효율적 |
| 메모리 | 적음 | 많음 |
주의사항
-
중복 값 처리
- 보통 중복 허용 안 함
- 필요시 노드에 카운트 저장
-
편향 방지
- 무작위 순서로 삽입
- 자가 균형 트리 사용 (AVL, Red-Black)
-
삭제 시 주의
- 자식이 둘인 경우 후속자(successor) 찾기
- 오른쪽 서브트리의 최솟값 또는 왼쪽 서브트리의 최댓값