CS학습2026년 8월 18일

이진 탐색 트리(Binary Search Tree): 정렬된 데이터를 효율적으로 탐색하고 관리하기 위한 트리 기반 자료구조

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이며, 왼쪽 자식 노드는 현재 노드 값보다 작고, 오른쪽 자식 노드는 현재 노드 값보다 큰 값을 가진다. 이러한 특성 덕분에 검색, 삽입, 삭제 연산에서 평균적으로 O(log n)의 시간 복잡도를 보인다. 정렬된 데이터를 빠르게 관리해야 할 때 유용하게 사용된다.

송민성4분 읽기

1. 개념

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 트리 구조이다. 중요한 규칙은 다음과 같다.

왼쪽 자식 노드: 현재 노드의 값보다 작다.
오른쪽 자식 노드: 현재 노드의 값보다 크다.

이러한 규칙을 만족하는 트리 구조를 이진 탐색 트리라고 한다. 루트 노드를 기준으로 왼쪽 서브트리는 루트 노드보다 작은 값들로 구성되고, 오른쪽 서브트리는 루트 노드보다 큰 값들로 구성된다. 이 규칙은 모든 서브트리에도 동일하게 적용된다.

2. 왜 사용하는가

이진 탐색 트리는 데이터를 정렬된 상태로 유지하면서 효율적인 탐색을 가능하게 한다. 선형 자료구조(배열, 연결 리스트)에서 데이터를 검색하려면 최악의 경우 O(n)의 시간이 걸리는 반면, 이진 탐색 트리는 평균적으로 O(log n)의 시간 복잡도로 데이터를 검색할 수 있다. 특히 데이터가 자주 삽입, 삭제, 검색되는 경우 성능 향상을 기대할 수 있다.

3. 동작 원리

검색(Search): 루트 노드부터 시작하여 검색하려는 값과 현재 노드 값을 비교한다. 값이 작으면 왼쪽 자식으로 이동하고, 값이 크면 오른쪽 자식으로 이동한다. 일치하는 값을 찾으면 검색 성공, 더 이상 이동할 노드가 없으면 검색 실패이다.

삽입(Insert): 새로운 노드를 삽입할 위치를 찾기 위해 검색과 유사한 방식으로 트리를 탐색한다. 삽입할 위치(더 이상 이동할 노드가 없는 지점)를 찾으면 해당 위치에 새로운 노드를 삽입한다.

삭제(Delete): 삭제할 노드를 찾는다.

자식 노드가 없는 경우: 단순히 노드를 삭제한다.
자식 노드가 하나인 경우: 해당 자식 노드로 대체한다.
자식 노드가 둘인 경우: 오른쪽 서브트리의 최솟값(또는 왼쪽 서브트리의 최댓값)으로 대체하고, 대체된 값을 가진 노드를 삭제한다. (Inorder Successor 또는 Inorder Predecessor).

4. 코드 예제

python

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):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return

        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = new_node
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = new_node
                    return
                current = current.right

    def search(self, value):
        current = self.root
        while current:
            if value == current.value:
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        return False

    def delete(self, value):
        # 구현은 생략 (복잡도 때문에)
        pass

5. 시간 복잡도 또는 성능 특성

검색, 삽입, 삭제 (평균): O(log n)
검색, 삽입, 삭제 (최악): O(n) - 트리가 한쪽으로 치우쳐진 경우 (Linked List와 유사한 형태)
최소/최대값 탐색: O(log n)
공간 복잡도: O(n)

이진 탐색 트리의 성능은 트리의 균형에 크게 의존한다. 트리가 균형을 이루지 못하고 한쪽으로 치우쳐지면 성능이 저하될 수 있다. 이를 해결하기 위해 AVL 트리, Red-Black 트리 등 균형 이진 탐색 트리를 사용하기도 한다.

6. 실무 사용 사례

데이터베이스 인덱스: 데이터베이스 시스템에서 특정 컬럼을 기준으로 데이터를 빠르게 검색하기 위해 이진 탐색 트리를 기반으로 하는 인덱스를 사용한다.
사전: 단어의 철자를 기준으로 빠르게 검색하기 위해 이진 탐색 트리를 사용할 수 있다.
컴파일러: 변수 이름과 해당 정보를 관리하기 위해 사용된다.

7. 주의할 점

불균형 문제: 트리가 한쪽으로 치우쳐지면 성능이 저하될 수 있다. 균형을 유지하기 위한 추가적인 알고리즘(AVL 트리, Red-Black 트리 등)을 고려해야 한다.
삭제 연산의 복잡도: 자식 노드가 둘인 노드를 삭제하는 경우, 대체 노드를 찾고 삭제하는 과정이 복잡할 수 있다.
메모리 사용량: 각 노드는 데이터와 자식 노드에 대한 포인터를 저장하므로, 메모리 사용량이 증가할 수 있다.

8. 핵심 정리

이진 탐색 트리는 정렬된 데이터를 효율적으로 관리하고 탐색하기 위한 강력한 자료구조이다. 평균적으로 O(log n)의 시간 복잡도를 제공하지만, 트리의 균형을 유지하는 것이 중요하다. 데이터베이스 인덱스, 사전 등 다양한 분야에서 활용될 수 있다.