이진 탐색 트리(Binary Search Tree, BST)

개요

이진 탐색 트리(BST, Binary Search Tree)는 이진 트리의 일종으로, 왼쪽 서브트리에는 루트보다 작은 값이, 오른쪽 서브트리에는 루트보다 큰 값이 저장되는 자료구조이다. 중복 없는 정렬된 데이터를 저장하면서 빠르게 탐색, 삽입, 삭제가 가능하며, 평균적으로 O(log n)의 성능을 보인다. 알고리즘 문제풀이와 데이터베이스, 메모리 관리 등 다양한 분야에 활용된다.

---

1. BST의 구조와 특징

구성 요소	설명
루트(Root)	트리의 최상위 노드
노드(Node)	데이터와 자식 포인터를 포함한 단위
왼쪽 자식	루트보다 작은 값
오른쪽 자식	루트보다 큰 값

BST는 모든 노드에 대해 왼쪽 < 루트 < 오른쪽이 성립한다.

---

2. BST의 연산 동작 원리

연산	동작 방식	시간 복잡도 (평균/최악)
탐색(Search)	루트부터 값 비교, 작으면 왼쪽, 크면 오른쪽으로 이동	O(log n) / O(n)
삽입(Insert)	비어있는 위치를 찾아 새 노드 추가	O(log n) / O(n)
삭제(Delete)	0, 1, 2개의 자식을 가진 경우로 나누어 처리	O(log n) / O(n)

최악의 경우는 편향 트리(선형 구조)일 때 발생한다.

---

3. 파이썬 BST 구현 예시 (삽입 및 중위 순회)

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=' ')
        inorder(node.right)

# 사용 예시
root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, k)
inorder(root)  # 출력: 20 30 40 50 60 70 80

---

4. BST의 장점과 단점

구분	장점	단점
탐색 성능	평균 O(log n) 탐색 가능	편향될 경우 O(n)까지 성능 저하
정렬 출력	중위 순회 시 오름차순 정렬	트리 균형 유지 필요
구현 난이도	재귀적으로 구현하기 직관적	삭제 연산 구현이 복잡할 수 있음

---

5. 균형 이진 탐색 트리와 비교

트리 유형	설명	균형 유지	성능
일반 BST	삽입 순서에 따라 편향 가능	X	O(log n) ~ O(n)
AVL 트리	균형 인수(Balance Factor) 유지	O	O(log n)
Red-Black 트리	색상 기반 균형 유지	O	O(log n)

---

6. 활용 분야

분야	활용 예시
정렬된 데이터 저장	오름차순/내림차순 출력
탐색 기반 문제	검색, 삽입, 삭제 반복 문제
중위 순회 출력	정렬 결과 얻기
알고리즘 문제풀이	K번째 수, 트리의 높이, 범위 탐색 등

---

7. 결론

이진 탐색 트리는 정렬된 데이터를 트리 구조로 효율적으로 저장하고 탐색할 수 있는 자료구조다. 탐색, 삽입, 삭제 모두 평균 O(log n)의 성능을 보이지만, 편향된 트리가 되지 않도록 균형 유지가 중요하다. 중위 순회를 활용한 정렬 출력, 반복적 탐색 문제 해결에 매우 유용하며, 고급 트리 구조인 AVL, Red-Black Tree의 기초가 되는 개념이다.