이진 탐색 트리(BST) 삭제 로직 (3가지 케이스)

이진 탐색 트리(Binary Search Tree, BST)에서 데이터를 검색(Search)하거나 삽입(Insert)하는 과정은 비교적 직관적입니다. 하지만 기존 데이터를 삭제(Delete)하는 연산은 훨씬 복잡하고 까다롭습니다. 그 이유는 노드를 단순히 제거하는 것에 그치지 않고, 삭제 후에도 '모든 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다'는 BST의 고유한 구조적 속성을 유지하기 위해 트리를 재정렬해야 하기 때문입니다. 이 글에서는 BST 삭제 시 발생할 수 있는 3가지 상황(Case)을 분석하고, 각 상황에 맞는 알고리즘 처리 방식을 코드로 구현해 봅니다.

1. 삭제할 노드의 3가지 케이스 분석

삭제 로직을 설계할 때는 삭제하려는 노드가 자식 노드를 몇 개 가지고 있느냐에 따라 접근 방식을 달리해야 합니다.

1-1. Case 1: 자식 노드가 없는 경우 (Leaf Node)

가장 단순한 상황입니다. 삭제할 노드가 트리의 말단(Leaf)에 위치해 있다면, 부모 노드와의 연결을 끊기만 하면 됩니다.

처리 방법: 부모 노드에게 해당 자식의 위치를 NULL(또는 None)로 업데이트하도록 요청하고, 해당 노드를 메모리에서 해제합니다.

1-2. Case 2: 자식 노드가 1개인 경우

삭제할 노드가 왼쪽이나 오른쪽 중 하나의 자식만 가지고 있는 상황입니다. 이 경우 삭제되는 노드의 자리를 자식 노드가 그대로 물려받으면 됩니다.

처리 방법: 삭제할 노드의 부모 노드가 삭제할 노드의 유일한 자식을 직접 가리키도록 포인터를 연결합니다. (마치 연결 리스트에서 중간 노드를 삭제하는 것과 유사합니다.)

1-3. Case 3: 자식 노드가 2개인 경우 (핵심)

가장 복잡한 상황입니다. 자식이 둘 다 있기 때문에 단순히 노드를 지우면 자식 노드들이 고아가 되고 트리의 구조가 깨집니다. 따라서 삭제할 노드를 대체할 후계자(Successor)를 찾아 그 값을 복사해와야 합니다.

후계자 선정 기준: 삭제할 노드보다 '바로 다음으로 큰 값'을 찾아야 합니다. 이는 오른쪽 서브 트리에서 가장 작은 값(Minimum Value)에 해당합니다. (또는 왼쪽 서브 트리에서 가장 큰 값을 선택할 수도 있습니다.)
처리 방법:
1. 오른쪽 서브 트리에서 최솟값을 가진 노드(Successor)를 찾습니다.
2. 삭제할 노드의 값을 Successor의 값으로 덮어씁니다.
3. Successor 노드(원래 위치)를 삭제합니다. (Successor는 항상 자식이 없거나 하나뿐이므로 Case 1이나 2로 처리됩니다.)

2. 파이썬(Python)으로 구현한 삭제 알고리즘

위의 3가지 케이스를 재귀 함수를 이용해 하나의 로직으로 통합한 코드입니다. 특히 Case 3에서 _min_value_node 함수를 활용하는 부분을 주목하십시오.


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

def min_value_node(node):
    """오른쪽 서브 트리에서 가장 작은 값을 찾는 헬퍼 함수"""
    current = node
    # 가장 왼쪽 끝으로 이동
    while current.left is not None:
        current = current.left
    return current

def delete_node(root, key):
    # 1. Base Case: 트리가 비어있거나 키를 찾지 못한 경우
    if root is None:
        return root

    # 2. 삭제할 키를 찾아 트리 탐색
    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    
    # 3. 삭제할 노드를 찾은 경우 (root.key == key)
    else:
        # Case 1 & 2: 자식이 없거나 하나만 있는 경우
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # Case 3: 자식이 둘 다 있는 경우
        # 오른쪽 서브 트리에서 가장 작은 노드(후계자)를 찾음
        temp = min_value_node(root.right)

        # 후계자의 값을 현재 노드로 복사 (값만 교체)
        root.key = temp.key

        # 후계자 노드를 원래 위치에서 삭제 (재귀 호출)
        root.right = delete_node(root.right, temp.key)

    return root

3. 성능 분석 및 주의사항

BST 삭제 연산의 시간 복잡도는 트리의 높이($h$)에 비례하므로 $O(h)$입니다. 균형 잡힌 트리라면 $O(\log n)$이지만, 편향된 트리라면 $O(n)$까지 성능이 저하될 수 있습니다. 따라서 실무에서는 삭제 후에도 균형을 자동으로 맞추는 AVL 트리나 레드-블랙 트리를 사용하는 것이 일반적입니다.

[핵심 요약 : BST 삭제 로직]
1. Leaf Node: 자식이 없으면 쿨하게 삭제합니다. (Pointer -> NULL)
2. One Child: 자식이 하나면 부모와 자식을 직접 연결하여 중간을 건너뜁니다.
3. Two Children: 오른쪽 서브 트리의 최솟값(Successor)을 찾아 값을 복사한 뒤, 해당 최솟값 노드를 삭제하여 구조를 유지합니다.

kguidebook0001 님의 블로그