[정글 베이직 21] 이진 검색 트리(BST)

BST는 이진 트리에 정렬 규칙이 추가된 구조입니다. 이 규칙 덕분에 원하는 값을 훨씬 빠르게 찾을 수 있습니다.

BST란?

BST(Binary Search Tree)는 각 노드에 대해 다음 규칙을 만족하는 트리입니다.

왼쪽 서브트리의 모든 값

현재 노드 값보다 작다.

현재 노드 값

비교의 기준이 되는 값

오른쪽 서브트리의 모든 값

현재 노드 값보다 크다.

예제 BST 구조

5

／ ＼

3

／ ＼

2

4

7

이 구조를 BST라고 부를 수 있는 이유

5의 왼쪽에는 3, 2, 4처럼 5보다 작은 값들만 있습니다.

5의 오른쪽에는 7처럼 5보다 큰 값만 있습니다.

노드 3을 기준으로 봐도 왼쪽은 2, 오른쪽은 4로 같은 규칙을 만족합니다.

검색 아이디어

BST 검색은 현재 노드 값과 target을 비교하면서 진행합니다.

비교 결과	동작
target == root.value	찾았으므로 True
target < root.value	왼쪽 서브트리로 이동
target > root.value	오른쪽 서브트리로 이동

예시로 따라가 보기: 값 4 검색

1단계

현재 노드 5와 비교합니다.

4 < 5 → 왼쪽으로 이동

2단계

현재 노드 3과 비교합니다.

4 > 3 → 오른쪽으로 이동

3단계

현재 노드 4와 비교합니다.

4 == 4 → 찾음 → True

풀이 포인트

일반 이진 트리는 어디에 값이 있는지 몰라서 전체를 다 볼 수도 있지만, BST는 대소 비교로 탐색 범위를 절반씩 줄여갈 수 있다는 점이 가장 중요합니다.

정답 코드

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

def search_bst(root, target):
    """
    BST에서 값 검색
    """
    if root is None:
        return False

    if target == root.value:
        return True
    elif target < root.value:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

# 테스트 케이스
if __name__ == "__main__":
    # BST 생성:
    #       5
    #      / \
    #     3   7
    #    / \
    #   2   4
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)

    print("=== 이진 검색 트리 ===")
    print("트리 구조: 5를 루트로 하는 BST")

    test_values = [2, 4, 5, 6, 7]
    for val in test_values:
        result = search_bst(root, val)
        print(f"값 {val} 검색: {result}")

한 줄 요약

BST 검색은 작으면 왼쪽, 크면 오른쪽만 기억하면 됩니다.