[C++ - TIL] 이진 탐색 트리(BST) 노드 삭제의 기초 - 리프 노드 제거 로직

🎮 주제 : 이진 탐색 트리(BST) 노드 삭제의 기초 - 리프 노드 제거 로직

태그 : #C++ #자료구조 #이진탐색트리 #BST #노드삭제 #포인터 #메모리관리

---

📌 학습 요약

• BST 삭제의 케이스 분류 : 노드가 가진 자식의 수(0개, 1개, 2개)에 따라 달라지는 삭제 메커니즘을 파악하고 그중 가장 기초인 리프 노드(자식 0개) 삭제 프로세스 정립
• 대상 노드 탐색 로직 : 루트부터 시작하여 데이터의 크기를 비교하며 하향 이동하고, 삭제 대상뿐만 아니라 그 부모 노드(parentNode)의 주소까지 추적하는 탐색 코드 구현
• 메모리 해제와 연결 끊기 : 단순히 delete를 통해 메모리를 해제하는 것에 그치지 않고, 부모 노드의 포인터를 nullptr로 명시적으로 갱신하여 댕글링 포인터 발생 방지
• 루트 예외 처리 : 부모 노드가 존재하지 않는 루트 노드를 삭제할 때 발생할 수 있는 참조 오류를 방지하기 위한 별도의 조건 분기 로직 습득

---

🛠 주요 코드 및 구현 상세

1. 자식이 없는 노드(Leaf Node) 삭제 구현

// [Case 1] 자식 노드가 하나도 없는 경우
if (currentNode->left == nullptr && currentNode->right == nullptr) {
    // 1. 루트 노드인 경우 (부모가 없음)
    if (currentNode == root) {
        delete root;
        root = nullptr;
    }
    // 2. 부모의 왼쪽 자식인 경우
    else if (parentNode->left == currentNode) {
        delete currentNode;
        parentNode->left = nullptr; // 연결 끊기
    }
    // 3. 부모의 오른쪽 자식인 경우
    else if (parentNode->right == currentNode) {
        delete currentNode;
        parentNode->right = nullptr; // 연결 끊기
    }
    return; 
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

탐색 조건	currentNode != nullptr를 앞세운 단락 평가	nullptr인 상태에서 data 접근 시 크래시 발생
delete	힙 메모리에 할당된 객체를 수동 해제	해제 후 반드시 해당 포인터를 nullptr로 관리
parentNode	삭제 노드의 부모 주소를 저장	트리의 재연결(Re-link)을 위해 반드시 필요
리프 노드	트리 구조의 말단 노드 (자식 없음)	트리 균형에 영향을 주지 않고 즉시 삭제 가능

💡 주의 : 삭제 로직의 순서

• 실수 : delete currentNode;를 먼저 수행하고 parentNode->left = nullptr;를 시도함
  • delete된 주소값을 여전히 부모가 들고 있으면 잘못된 메모리 접근의 위험이 있으므로, 논리적으로 삭제와 연결 끊기가 원자적으로 이루어져야 함

---

느낀 점

• 단순한 "값 삭제"라도 BST에서는 여러 경우의 수를 따져야 한다는 점이 흥미로웠음
• 삭제 로직을 구현하려면 단순히 delete만 해서는 안 되고, 트리 구조를 어떻게 이어줄지도 함께 고민해야 함을 깨달음
• 처음에는 실수로 delete 호출 순서나 루트 복귀 로직에서 문제가 있었으나, 디버깅을 통해 개선하며 포인터 조작의 정밀함을 익힘
• 조건 분기를 더 명확히 하기 위해 변수명을 신중히 정하고, 중복된 코드를 제거할 필요성을 느낌