이진 탐색 트리

이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 한 유형으로, 모든 노드가 다음과 같은 이진 탐색 속성을 만족하는 트리 구조이다.

• 왼쪽 서브트리의 모든 노드는 부모 노드보다 작다.
• 오른쪽 서브트리의 모든 노드는 부모 노드보다 크다.
• 각 서브트리 또한 이진 탐색 트리이다.

이진 탐색 트리는 탐색, 삽입, 삭제 연산을 평균적으로 O(log N)에 수행할 수 있어, 정렬된 데이터를 효율적으로 관리하는 데 사용된다.

1 특징

• 각 노드의 최대 자식 노드 수는 2개이다.
• 중복된 값은 허용되지 않는 경우가 일반적이다.
• 정렬된 데이터를 효과적으로 탐색할 수 있다.
• 트리의 균형 상태에 따라 성능이 결정된다.
  • 균형 잡힌 경우: O(log N)
  • 편향된 경우: O(N) (한쪽으로 치우친 리스트 형태)

2 기본 연산

이진 탐색 트리는 다음과 같은 연산을 수행할 수 있다.

2.1 탐색(Search)

• 루트에서 시작하여 원하는 값을 찾을 때까지 왼쪽 또는 오른쪽으로 이동.
• 찾고자 하는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동.

2.2 삽입(Insertion)

• 새로운 노드를 추가할 위치를 찾은 후, 적절한 위치에 삽입.

2.3 삭제(Deletion)

삭제할 노드의 경우에 따라 다르게 처리됨:

• 자식이 없는 노드 → 단순히 제거.
• 자식이 하나인 노드 → 부모 노드와 직접 연결.
• 자식이 두 개인 노드 → 오른쪽 서브트리에서 가장 작은 값(후계자)을 찾아 대체.

3 예제

다음과 같은 BST를 고려하자.

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

• 탐색(6) → 8에서 왼쪽(3), 다시 오른쪽(6)으로 이동하여 찾음.
• 삽입(5) → 6의 왼쪽(4)에서 오른쪽(5)에 추가.
• 삭제(3) → 후계자(4)로 대체.

4 코드 예제

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

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

    def insert(self, value):
        if not self.root:
            self.root = Node(value)
            return
        self._insert(self.root, value)

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

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if not node or node.value == value:
            return node
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

# 예제 실행
bst = BST()
for num in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(num)

print(bst.search(6).value)  # 출력: 6

출력 결과 예시:
6

5 응용

이진 탐색 트리는 다양한 분야에서 활용된다.

• 데이터베이스 → 인덱싱 구조
• 운영체제 → 메모리 관리, 파일 시스템
• 네트워크 → 라우팅 테이블 최적화
• 인공지능 → 의사결정 트리(Decision Tree)

6 같이 보기

• 트리 이론
• AVL 트리
• 레드-블랙 트리
• B-트리

7 참고 문헌

• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
• Knuth, Donald E. "The Art of Computer Programming, Volume 3: Sorting and Searching." Addison-Wesley, 1998.