[C++ - TIL] 이진 탐색 트리(BST) 삭제 알고리즘의 완성 - 모든 케이스 구현

🎮 주제 : 이진 탐색 트리(BST) 삭제 알고리즘의 완성 - 모든 케이스 구현

태그 : #C++ #자료구조 #이진탐색트리 #BST #노드삭제 #중위후속자 #메모리관리

---

📌 학습 요약

• BST 삭제의 완전한 체계 : 리프 노드, 자식이 하나인 노드, 그리고 자식이 둘인 노드까지의 모든 삭제 시나리오를 분석하고 분기 처리 로직 구축
• 중위 후속자(In-order Successor) 활용 : 자식이 둘인 노드 삭제 시, 트리 구조를 유지하기 위해 오른쪽 서브트리의 최솟값을 찾아 데이터를 교체하는 전략 숙지
• 동적 메모리의 안전한 전이 : 자식이 하나인 노드 삭제 시 부모 노드와 자식 노드를 직접 연결하여 계층 구조를 보존하고 기존 노드를 해제하는 프로세스 정립
• 데이터 교체 방식의 효율성 : 자식이 둘일 때 노드 자체를 물리적으로 삭제하고 재배치하는 대신, 후속자의 데이터만 복사하고 후속자 노드를 삭제하는 최적화 기법 이해

---

🛠 주요 코드 및 구현 상세

1. 자식이 둘인 노드 삭제 (중위 후속자 로직)

// [Case 3] 자식이 두 개인 경우
else {
    // 1. 오른쪽 서브트리에서 가장 작은 노드(후속자) 탐색
    Node* successor = currentNode->right;
    Node* successorParent = currentNode;

    while (successor->left != nullptr) {
        successorParent = successor;
        successor = successor->left;
    }

    // 2. 현재 노드에 후속자의 데이터를 복사 (노드 삭제 대신 값 교체)
    currentNode->data = successor->data;

    // 3. 후속자 노드를 트리에서 분리 (후속자는 절대 왼쪽 자식이 있을 수 없음)
    if (successorParent->left == successor)
        successorParent->left = successor->right;
    else
        successorParent->right = successor->right;

    // 4. 후속자 노드 메모리 해제
    delete successor;
}

2. 자식이 하나인 노드 삭제

// [Case 2] 자식이 하나만 있는 경우
else if (currentNode->left == nullptr || currentNode->right == nullptr) {
    Node* child = (currentNode->left != nullptr) ? currentNode->left : currentNode->right;

    if (currentNode == root) {
        root = child;
    } else if (parentNode->left == currentNode) {
        parentNode->left = child;
    } else {
        parentNode->right = child;
    }

    delete currentNode;
}

---

✅ 주요 문법 및 개념 정리

구분 리프 노드 삭제 자식 1개 삭제 자식 2개 삭제

핵심 동작	부모 링크 nullptr	부모-자식 직접 연결	데이터 교체 + 후속자 삭제
난이도	낮음	중간	높음
특징	트리 높이 변화 적음	자식이 부모 자리 승계	중위 후속자 탐색 필수
메모리 해제	대상 노드 즉시 삭제	대상 노드 즉시 삭제	후속자 노드를 삭제

💡 주의 : 중위 후속자의 조건

• 중위 후속자는 **"나보다 큰 값들 중 가장 작은 값"**입니다.
• 오른쪽 자식으로 이동한 뒤 계속해서 left로 내려가서 찾습니다.
• 후속자는 가장 왼쪽에 있는 노드이므로, 왼쪽 자식을 절대 가질 수 없다는 성질을 이용해 삭제 로직을 단순화할 수 있습니다.

---

✨ 느낀 점

• 삭제 로직이 생각보다 복잡하여 단순히 delete를 호출하는 것이 아니라 부모-자식 간의 연결 관계를 정리하는 디버깅에 공을 많이 들임
• 자식이 2개일 때 노드를 물리적으로 삭제하지 않고 데이터만 바꾸는 방식이 트리 구조의 파괴를 최소화하는 핵심임을 분명히 이해함
• "메모리 해제는 대상이 명확해야 한다"는 교훈을 통해 포인터 조작 시 주소값 추적의 중요성을 다시 한번 깨달음
• 자료구조 구현은 단순한 코드 작성을 넘어 전체적인 흐름과 예외 상황을 설계하는 능력이 필수적임을 체감함