[CS] 이진 탐색 트리

khj·2024년 12월 5일

Computer Science

목록 보기

11/25

이진 탐색 트리(Binary Search Tree, 이하 BST)는 이진 트리의 한 종류로, 각 노드가 최대 두 개의 자식을 가지며, 특정한 규칙을 따라 정렬된 트리입니다. BST는 빠른 탐색, 삽입, 삭제가 가능하여 다양한 알고리즘과 데이터 구조에서 자주 사용됩니다.

1. 이진 탐색 트리의 특징

BST는 다음 규칙을 따르는 트리입니다:

왼쪽 자식 노드: 현재 노드보다 작은 값을 가짐.
오른쪽 자식 노드: 현재 노드보다 큰 값을 가짐.
이 규칙은 모든 하위 트리에서도 재귀적으로 적용됩니다.

예시: 루트 노드가 15일 때, 왼쪽 자식은 10보다 작고, 오른쪽 자식은 20보다 큽니다.

2. 주요 연산 및 Python 코드

2.1 탐색(Search)

루트 노드에서 시작하여 찾고자 하는 값과 비교합니다.

찾는 값이 현재 노드보다 작으면 왼쪽 서브트리로 이동.
크면 오른쪽 서브트리로 이동.
값이 일치하면 탐색 종료.

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

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

# 예시 실행
root = Node(15)
root.left = Node(10)
root.right = Node(20)
print(search(root, 10))  # 출력: True
print(search(root, 25))  # 출력: False

2.2 삽입(Insertion)

적절한 위치를 찾아 재귀적으로 탐색한 후 새 노드를 삽입합니다.

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.value:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

# 예시 실행
root = insert(None, 15)
insert(root, 10)
insert(root, 20)
insert(root, 25)

(3) 삭제(Deletion)

삭제는 세 가지 경우로 나뉩니다:

자식이 없는 노드 삭제.
자식이 하나인 노드 삭제.
자식이 둘인 노드는 오른쪽 서브트리에서 가장 작은 값으로 대체합니다.

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

def delete(node, key):
    if node is None:
        return node
    if key < node.value:
        node.left = delete(node.left, key)
    elif key > node.value:
        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.value = temp.value
        node.right = delete(node.right, temp.value)
    return node

# 예시 실행
root = insert(None, 15)
insert(root, 10)
insert(root, 20)
root = delete(root, 15)