[자료구조 트리] BST 삭제 완전 정복: Predecessor vs Successor (이진탐색트리)

[Algorithm] Binary Search Tree - Successor, Predecessor

BST, 즉 Binary Search Tree에서 root를 remove하는데에는 2가지 방법이 있습니다.

predecessor와 successor가 있는데 두 차이점과 어떻게 구한하는지를 적어보려 합니다.

 

BST 삭제가 어려운 이유

 

BST Delete가 어려운 근본적인 이유는 단순합니다. 삭제 후에도 BST의 핵심 성질을 반드시 지켜야 하기 때문입니다.

BST의 성질: Left 서브트리 < 현재 노드 < Right 서브트리

 

삽입은 이 규칙에 따라 내려가다가 빈 자리에 꽂으면 끝지만,  근데 삭제는 다릅니다. 노드를 없애면 그 자리가 비어버리고, 그 아래 연결된 서브트리들이 붕 뜨게 됩니다. 이걸 BST 성질을 깨지 않으면서 다시 연결해야 합니다.

 

---

BST 노드 삭제 과정은 크게 세 가지로 나뉩니다.

 

Case 1	자식이 없는 노드 (리프 노드)	그냥 지운다.
Case 2	자식이 1개인 노드	지운 자리에 자식 하나를 올린다.
Case 3	자식이 2개인 노드	Predecessor 또는 Successor를 사용.

---

아래와 같은 BST가 있다고 해봅시다.

 

        50
       /  \
      30   70
     / \   / \
    20  40 60  80

 

여기서 루트 노드 50을 삭제하려고 합니다.

 

50을 그냥 없애버리면 30과 70이 연결을 잃습니다. 둘 중 하나를 루트로 올리면 되지 않을까요? 예를 들어 70을 루트로 올리면?

        70
       /  \
      30   80
     / \   
    20  40 
         
    60은?? → 어디 갔지?

 

60이 사라집니다. BST 성질도 깨지고, 데이터도 잃습니다. 그래서 단순히 자식 중 하나를 올리는 방법은 쓸 수 없습니다.

핵심 질문: "50 자리에 들어올 수 있는 값은 어떤 값이어야 할까?"

 

50 자리에 오는 값은 왼쪽 서브트리(20, 30, 40)보다 크고, 오른쪽 서브트리(60, 70, 80)보다 작아야 합니다. 이 조건을 만족하는 값은 트리 안에 딱 두 개밖에 없어요. 바로 40(Predecessor) 과 60(Successor) 입니다.

---

BST Predecessor

Predecessor = 삭제할 노드보다 작은 값들 중에서 가장 큰 값

 

"왼쪽으로 한 번, 그 다음 오른쪽으로 끝까지"

 

왼쪽 서브트리에서 가장 오른쪽에 있는 노드가 Predecessor입니다.

위 예시에서 50의 Predecessor를 찾는 과정:

1. 왼쪽으로 이동 → 30
2. 오른쪽으로 끝까지 → 40 (40의 오른쪽 자식이 없으므로 멈춤)
3. Predecessor = 40

Predecessor의 특징:

• 왼쪽 서브트리의 최댓값이므로, 왼쪽 서브트리의 어떤 값보다도 큽니다.
• 삭제 노드보다 작으므로, 오른쪽 서브트리의 어떤 값보다도 작습니다.
• 그래서 삭제 노드 자리에 들어와도 BST 성질이 유지됩니다.

 

 

cpp

// C++ - Predecessor 찾기
Node* findPredecessor(Node* root) {
    Node* current = root->left;    // 왼쪽으로 한 번
    while (current && current->right)  // 오른쪽 끝까지
        current = current->right;
    return current;
}

---

BST Successor

Successor = 삭제할 노드보다 큰 값들 중에서 가장 작은 값

Predecessor의 반대 방향입니다.

"오른쪽으로 한 번, 그 다음 왼쪽으로 끝까지"

오른쪽 서브트리에서 가장 왼쪽에 있는 노드가 Successor입니다.

위 예시에서 50의 Successor를 찾는 과정:

1. 오른쪽으로 이동 → 70
2. 왼쪽으로 끝까지 → 60 (60의 왼쪽 자식이 없으므로 멈춤)
3. Successor = 60

 

cpp

// C++ - Successor 찾기
Node* findSuccessor(Node* root) {
    Node* current = root->right;   // 오른쪽으로 한 번
    while (current && current->left)  // 왼쪽 끝까지
        current = current->left;
    return current;
}

---

 

        50        ← 삭제 대상
       /  \
      30   70
     / \   / \
    20  40 60  80

• Predecessor = 40 (왼→오른쪽 끝)
• Successor = 60 (오른→왼쪽 끝)

---

 

두 방법의 차이 | O(N)

항목                                        Predecessor                                                    Successor

 

대체 노드 위치	왼쪽 서브트리의 최댓값	오른쪽 서브트리의 최솟값
탐색 방향	왼쪽 → 오른쪽 끝	오른쪽 → 왼쪽 끝
삭제 후 영향	왼쪽 서브트리 높이 감소 가능	오른쪽 서브트리 높이 감소 가능
BST 성질 유지	유지됨	유지됨
삭제 후 트리 모양	서로 다름	서로 다름
정답/오답	정답	정답

---

최선 (균형 잡힌 트리)	O(log n)	트리 높이가 log n
평균	O(log n)	랜덤 입력 기준
최악 (편향 트리)	O(n)	한쪽으로만 치우친 경우

BST 삭제 알고리즘 자체는 결국 트리 높이에 비례합니다. Predecessor나 Successor를 찾는 탐색이 트리 높이만큼 내려가기 때문입니다.

 

균형이 잡혀 있으면 O(log n), 최악의 경우(모든 노드가 한 방향으로 삽입된 경우)엔 O(n)이 됩니다. 

 

---

 

Predecessor: 왼→ 오른쪽 끝  (L → R_end)
Successor:   오→ 왼쪽 끝   (R → L_end)

 

더 쉽게 외우는 방법:

• Predecessor = Previous (이전) → 나보다 작은 것 중 최대 → 왼쪽 서브트리 최댓값
• Successor = Succeeding (다음) → 나보다 큰 것 중 최소 → 오른쪽 서브트리 최솟값

 (방향 기준):

P는 L-R: Predecessor → Left로 가서 Right 끝
S는 R-L: Successor → Right로 가서 Left 끝

이 두 문장만 외우고 시험장에 들어가면 BST 삭제 문제는 절대 틀리지 않습니다.

---

전체 C++ 코드

 

 

cpp

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Predecessor 왼쪽 → 오른쪽 끝
Node* findPredecessor(Node* node) {
    Node* current = node->left;
    while (current && current->right)
        current = current->right;
    return current;
}

// Successor  오른쪽 → 왼쪽 끝
Node* findSuccessor(Node* node) {
    Node* current = node->right;
    while (current && current->left)
        current = current->left;
    return current;
}

---