이번 튜토리얼에서는 C++를 사용해 이진 트리(Binary Tree)에서 특정 노드를 삭제하는 방법을 알아보겠습니다.
이진 탐색 트리(BST)와 달리 일반 이진 트리의 노드들은 특정한 순서를 따르지 않습니다. 그렇다면 노드를 삭제한 후 나머지 노드들은 어떻게 배치해야 할까요?
가장 일반적인 해결 방법은 다음과 같습니다.
- 삭제할 노드를 찾습니다.
- 트리에서 가장 깊은(deepest) 노드를 찾아 삭제할 노드의 자리에 값을 복사합니다.
- 그런 다음 가장 깊은 노드를 실제로 제거합니다.
이 방식을 사용하면 트리의 구조가 크게 흐트러지지 않으면서도 간단하게 노드를 삭제할 수 있습니다.
문제 해결 절차
전체적인 구현 흐름은 다음과 같습니다.
- 이진 트리 노드 구조체(struct)를 정의하여 트리를 초기화합니다.
- 트리의 노드를 출력하기 위한 순회 함수(중위 순회 등)를 작성합니다.
- 노드를 삭제하는 함수를 작성합니다.
- 트리를 순회하기 위해 큐(queue)를 초기화합니다.
- 큐가 빌 때까지 반복하며 트리를 탐색합니다.
- 삭제하려는 키(key)와 일치하는 노드를 찾아 변수에 저장합니다.
- 탐색이 끝난 후 마지막으로 방문한 노드가 곧 가장 깊은 노드입니다.
- 별도의 함수를 사용해 가장 깊은 노드를 삭제합니다.
- 큐로 트리를 다시 순회합니다.
- 가장 깊은 노드를 발견하면 부모 노드와의 연결을 끊고 메모리를 해제한 뒤 반환합니다.
- 트리를 출력하여 노드가 정상적으로 삭제되었는지 확인합니다.
C++ 구현 예제
이제 전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* node) {
if (node == NULL) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp == deleting_node) {
temp = NULL;
delete (deleting_node);
return;
}
if (temp->right) {
if (temp->right == deleting_node) {
temp->right = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->right);
}
}
if (temp->left) {
if (temp->left == deleting_node) {
temp->left = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->left);
}
}
}
}
Node* deleteNode(struct Node* root, int key) {
if (root == NULL){
return NULL;
}
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
return NULL;
}
else {
return root;
}
}
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
struct Node* key_node = NULL;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp->data == key) {
key_node = temp;
}
if (temp->left) {
nodes.push(temp->left);
}
if (temp->right) {
nodes.push(temp->right);
}
}
if (key_node != NULL) {
int deepest_node_data = temp->data;
deleteDeepestNode(root, temp);
key_node->data = deepest_node_data;
}
return root;
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << "Tree before deleting key: ";
inorder(root);
int key = 5;
root = deleteNode(root, key);
cout << "\nTree after deleting key: ";
inorder(root);
cout << endl;
return 0;
}코드 핵심 로직 설명
- deleteNode 함수: 레벨 순회(Level Order Traversal)를 수행하면서 삭제할 키를 가진 노드를 추적하고, 동시에 마지막으로 방문한 노드(가장 깊은 노드)를 기억합니다.
- deleteDeepestNode 함수: 가장 깊은 노드를 트리에서 분리하고 메모리를 해제합니다. 부모 노드의 left 또는 right 포인터를 NULL로 설정하는 것이 핵심입니다.
- 값 복사: 가장 깊은 노드의 데이터를 삭제 대상 노드에 복사한 후, 가장 깊은 노드만 제거함으로써 트리 구조를 유지합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Tree before deleting key: 3 2 4 1 8 6 9 5 7 Tree after deleting key: 3 2 4 1 8 6 9 7
키 값 5를 가진 노드가 삭제되고, 가장 깊은 노드였던 7의 값이 해당 위치로 이동한 것을 중위 순회 결과를 통해 확인할 수 있습니다.
마무리
이처럼 이진 트리에서 노드를 삭제할 때는 '가장 깊은 노드로 대체'하는 전략이 널리 사용됩니다. 시간 복잡도는 트리를 두 번 순회하므로 O(N)입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요!