🌲 이진 탐색 트리 (Binary Search Tree, BST) 완벽 정리

---

✅ 이진 탐색 트리란?

이진 탐색 트리(BST)는 이진 트리의 일종으로, 왼쪽 서브트리에는 현재 노드보다 작은 값, 오른쪽 서브트리에는 현재 노드보다 큰 값이 위치하는 구조를 가진다.
이러한 규칙 덕분에 데이터를 빠르게 탐색할 수 있으며, 정렬된 데이터를 다룰 때 매우 유용하게 사용된다.

---

✅ BST의 특징

• 중복되지 않는 값들로 구성된다. (일반적으로 중복을 허용하지 않음)
• 노드 삽입 시, 해당 값보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다.
• 정렬된 데이터를 트리 형태로 저장할 수 있다.
• 중위 순회(Inorder Traversal)를 하면 오름차순으로 정렬된 결과를 얻을 수 있다.

---

📌 BST 시각적 예시

다음과 같은 숫자들이 순서대로 삽입될 경우:

10 → 5 → 15 → 3 → 7 → 13 → 18

구성되는 트리 구조는 아래와 같다.

    10
   /  \
  5    15
 / \   / \
3   7 13 18

---

✅ 주요 연산

1. 탐색 (Search)

• 현재 노드의 값과 비교
  • 같으면 찾은 것
  • 작으면 왼쪽 서브트리
  • 크면 오른쪽 서브트리
• 시간복잡도: 평균 O(log n), 최악 O(n) (편향 트리일 경우)

2. 삽입 (Insert)

• 루트부터 탐색하며 적절한 위치에 새로운 노드를 추가
• 왼쪽/오른쪽 자식 중 비어있는 곳에 삽입

3. 삭제 (Delete)

삭제는 총 3가지 경우로 나뉜다.

• 리프 노드일 경우: 그냥 제거
• 한 개의 자식만 있을 경우: 해당 자식으로 대체
• 두 개의 자식을 가진 경우: 오른쪽 서브트리에서 가장 작은 노드(후계자)로 대체

---

✅ 파이썬 구현 예제

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

# BST 삽입
def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

# BST 탐색
def search(node, key):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search(node.left, key)
    else:
        return search(node.right, key)

# 중위 순회 (오름차순 출력)
def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=' ')
        inorder(node.right)

# 최소값 찾기 (삭제 연산에 필요)
def find_min(node):
    while node.left:
        node = node.left
    return node

# BST 삭제
def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # case 1: no child
        if node.left is None and node.right is None:
            return None
        # case 2: one child
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        # case 3: two children
        successor = find_min(node.right)
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node

# 실행 예시
root = None
for num in [10, 5, 15, 3, 7, 13, 18]:
    root = insert(root, num)

print("Inorder Traversal:")
inorder(root)  # 출력: 3 5 7 10 13 15 18

# 탐색
print("\n\nSearch 13:")
found = search(root, 13)
print("Found!" if found else "Not found")

# 삭제
root = delete(root, 10)
print("\nInorder after deleting 10:")
inorder(root)

---

🎯 마무리 요약

• BST는 정렬된 데이터를 트리 형태로 저장하며, 삽입/삭제/탐색 모두 평균 O(log n)의 시간복잡도를 가진다.
• 중위 순회를 하면 오름차순 정렬 결과를 얻을 수 있다.
• 삭제 연산은 세 가지 경우(리프 노드, 자식 1개, 자식 2개)를 구분해서 처리해야 한다.
• 편향된 BST는 선형 구조가 되어 성능이 저하되므로, 이후 배울 AVL 트리, Red-Black 트리 와 같은 균형 트리가 등장하게 된다.