문제 개요
이진 탐색 트리(Binary Search Tree, BST)가 주어져 있다고 가정해 보겠습니다. 하나의 키 k를 입력받아 BST에서 해당 키를 가진 노드를 삭제한 뒤, 갱신된 BST를 반환하는 것이 목표입니다.
예를 들어 다음과 같은 트리가 있고,
삭제할 키가 k = 3이라면, 최종 출력 트리는 다음과 같습니다.
해결 접근 방법
이 문제는 크게 두 단계로 나누어 해결할 수 있습니다. 먼저 루트 노드를 삭제하는 헬퍼 함수를 정의하고, 이를 활용해 트리 내부의 목표 노드를 찾아 삭제하는 방식입니다.
1단계: deleteRoot() 메서드 정의
루트 노드를 삭제하는 deleteRoot() 메서드는 다음 순서로 동작합니다.
- 루트가
null이면null을 반환합니다. - 루트에 오른쪽 서브트리가 존재하지 않으면, 루트의 왼쪽 자식을 반환합니다.
- x를 루트의 중위 순회(inorder) 후속 노드(successor)로 설정합니다. 즉, 오른쪽 서브트리에서 가장 왼쪽에 있는 노드를 찾습니다.
- x의 왼쪽 자식을 기존 루트의 왼쪽 자식과 연결합니다.
- 루트의 오른쪽 자식을 새로운 루트로 반환합니다.
이 방식의 핵심은 삭제된 노드의 왼쪽 서브트리를 중위 순회 후속 노드 아래에 붙여, BST의 속성(왼쪽 자식 < 부모 < 오른쪽 자식)을 그대로 유지한다는 점입니다.
2단계: deleteNode() 메서드 구현
- 루트가
null이거나 루트의 값이 key와 같으면deleteRoot(root)를 호출해 결과를 반환합니다. - curr을 루트로 초기화한 뒤, 무한 루프를 돌며 다음을 수행합니다.
- x := 현재 노드(curr)의 값
- key < x인 경우: curr의 왼쪽 자식이
null이거나 그 값이 key라면, curr의 왼쪽 자식을deleteRoot()의 결과로 교체하고 루프를 종료합니다. 그렇지 않으면 curr을 왼쪽 자식으로 이동합니다. - key ≥ x인 경우: curr의 오른쪽 자식이
null이거나 그 값이 key라면, curr의 오른쪽 자식을deleteRoot()의 결과로 교체하고 루프를 종료합니다. 그렇지 않으면 curr을 오른쪽 자식으로 이동합니다.
- 모든 처리가 끝나면 루트를 반환합니다.
이제 전체 구현 코드를 통해 더 자세히 이해해 보겠습니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
}
else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == NULL || root->val == key) return deleteRoot(root);
TreeNode* curr = root;
while(1) {
int x = curr->val;
if(key < x){
if(curr->left == NULL || curr->left->val == key){
curr->left = deleteRoot(curr->left);
break;
}
curr = curr->left;
} else {
if(curr->right == NULL || curr->right->val == key){
curr->right = deleteRoot(curr->right);
break;
}
curr = curr->right;
}
}
return root;
}
TreeNode* deleteRoot(TreeNode* root){
if(!root || root->val == 0)return NULL;
if(root->right == NULL) return root->left;
TreeNode* x = root->right;
while(x->left)x = x->left;
x->left = root->left;
return root->right;
}
};
main(){
vector<int> v = {5,3,6,2,4,NULL,7};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.deleteNode(root, 3));
}입력
[5,3,6,2,4,null,7] 3
출력
[5, 4, 6, 2, null, 7]
정리
BST에서 노드를 삭제할 때는 세 가지 경우를 고려해야 합니다. 자식이 없는 리프 노드, 자식이 하나뿐인 노드, 그리고 자식이 둘인 노드입니다. 위 알고리즘은 중위 순회 후속 노드를 활용해 자식이 둘인 경우도 자연스럽게 처리하며, BST의 정렬 속성을 유지한 채 노드를 안전하게 제거할 수 있습니다. 시간 복잡도는 균형 잡힌 트리 기준으로 O(log n), 최악의 경우(편향 트리) O(n)입니다.