이진 탐색 트리(Binary Search Tree, BST): 탐색 최적화 데이터 구조

🔹 이진 탐색 트리란?

1. 이진 탐색 트리(Binary Search Tree, BST)의 정의

이진 탐색 트리(Binary Search Tree, BST)는 각 노드의 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지는 특성을 갖는 이진 트리입니다. 이러한 특성 덕분에 탐색, 삽입, 삭제 연산이 평균 O(log n)의 시간 복잡도를 유지할 수 있습니다.

✅ BST의 주요 특징:

• 이진 트리(Binary Tree)의 한 유형
• 각 노드의 왼쪽 서브트리는 부모보다 작은 값들로 구성
• 각 노드의 오른쪽 서브트리는 부모보다 큰 값들로 구성
• 중위 순회(Inorder Traversal)를 수행하면 정렬된 데이터를 얻을 수 있음
• 탐색, 삽입, 삭제 연산이 평균적으로 O(log n)의 시간 복잡도를 가짐

📌 BST는 탐색 및 정렬이 빈번한 데이터 처리에 적합한 구조입니다.

---

🔹 BST의 주요 연산

1. 삽입(Insertion) - O(log n)

✅ 새로운 노드를 적절한 위치에 추가하는 연산

✔️ BST 삽입 연산 예제 (Python):

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(self.root, data)

    def _insert(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert(node.right, data)

📌 BST에 데이터를 삽입하면 자동으로 정렬된 형태를 유지합니다.

2. 탐색(Search) - O(log n)

✅ 특정 데이터를 찾는 연산

✔️ BST 탐색 연산 예제 (Python):

def search(node, key):
    if node is None or node.data == key:
        return node
    if key < node.data:
        return search(node.left, key)
    return search(node.right, key)

📌 BST의 탐색 연산은 최악의 경우 O(n), 평균적으로 O(log n)의 성능을 가집니다.

3. 삭제(Deletion) - O(log n)

✅ 특정 노드를 제거하는 연산 (3가지 경우 고려)

• 삭제할 노드가 리프 노드일 경우 → 단순히 제거
• 삭제할 노드가 하나의 자식을 가질 경우 → 부모 노드가 해당 자식을 가리키도록 변경
• 삭제할 노드가 두 개의 자식을 가질 경우 → 오른쪽 서브트리에서 최솟값(후계자)을 찾아 대체

✔️ BST 삭제 연산 예제 (Python):

def delete(node, key):
    if node is None:
        return node
    if key < node.data:
        node.left = delete(node.left, key)
    elif key > node.data:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        temp = find_min(node.right)
        node.data = temp.data
        node.right = delete(node.right, temp.data)
    return node

def find_min(node):
    while node.left:
        node = node.left
    return node

📌 삭제 연산에서 두 개의 자식을 가진 경우, 오른쪽 서브트리의 최솟값을 찾아 대체합니다.

---

🔹 BST 순회 방법

✅ 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽
✅ 중위 순회(Inorder): 왼쪽 → 루트 → 오른쪽 (정렬된 데이터 반환)
✅ 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트
✅ 레벨 순회(Level Order): BFS를 사용하여 레벨별로 탐색

✔️ 중위 순회 예제 (Python):

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.data, end=" ")
        inorder_traversal(node.right)

📌 중위 순회(Inorder Traversal)를 수행하면 오름차순으로 정렬된 결과를 얻을 수 있습니다.

---

🔹 BST의 활용 사례

✅ 데이터 탐색(Search): 정렬된 데이터를 빠르게 찾을 수 있음
✅ 자동 정렬(Auto Sorting): 삽입 시 자동으로 정렬된 구조 유지
✅ 이진 탐색(Binary Search) 활용: O(log n)으로 효율적인 검색 가능
✅ 데이터베이스 인덱싱(Indexing): 빠른 데이터 검색을 위한 인덱스 구조로 활용
✅ 우선순위 큐(Priority Queue) 및 힙(Heap) 구현: 응용 가능

📌 BST는 검색 및 정렬이 필요한 다양한 시스템에서 핵심적인 역할을 합니다.

---

📌 결론

✅ 이진 탐색 트리(Binary Search Tree, BST)는 데이터 탐색 및 정렬이 중요한 경우 활용되는 트리 구조입니다.
✅ 탐색, 삽입, 삭제 연산이 평균적으로 O(log n)의 성능을 가지며, 균형이 맞지 않을 경우 O(n)까지 성능이 저하될 수 있습니다.
✅ 균형 이진 탐색 트리(AVL, Red-Black Tree)와 함께 활용하면 성능 저하를 방지할 수 있습니다.
✅ BST는 데이터베이스 인덱싱, 검색 엔진, 우선순위 큐, 머신러닝의 의사결정 트리 등에 활용됩니다.