C++의 이진 검색 트리에서 노드 삭제
이 기사에서는 이진 검색 트리 데이터 구조 C++에서 노드를 삭제하는 함수를 구현하는 방법을 설명합니다.
C++의 이진 검색 트리에서 노드 삭제
이진 탐색 트리는 각 노드에 키 값을 저장하는 일종의 이진 트리입니다. 이 키는 각 노드의 키가 왼쪽 하위 트리의 모든 키보다 크고 오른쪽 하위 트리의 키보다 작도록 정렬된 트리를 구성하는 데 사용됩니다.
모든 노드는 일반적으로 left 및 right 노드에 대한 두 개의 포인터를 포함하지만 remove 멤버 함수를 구현하는 것이 더 쉽기 때문에 상위 노드를 나타내는 또 다른 포인터도 추가했습니다.
다음 이진 검색 트리 구현에는 노드 제거 작업을 보여주기 위한 최소한의 멤버 함수만 포함되어 있습니다.
BinSearchTree 클래스는 int 유형만 키 값으로 저장할 수 있습니다. remove를 제외한 대부분의 함수는 재귀를 사용하므로 내부적으로 호출되는 해당 private 멤버 함수를 제공합니다. 일반적으로 트리에서 노드를 제거하는 것은 여러 시나리오를 수반하므로 삽입 및 검색보다 더 복잡한 작업입니다.
가장 간단한 첫 번째 시나리오는 자식이 없는 노드(결과적으로 리프 노드라고 함)를 제거해야 하는 경우입니다. 리프 노드를 할당 해제하고 부모의 해당 포인터에 nullptr을 할당할 수 있습니다.
두 번째 경우는 자식이 하나만 있는 노드를 제거하는 것입니다. 후자는 대상의 부모를 자식에 연결하여 해결할 수 있으며 연결된 메모리를 할당 해제할 수 있습니다.
#include <iostream>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
struct BSTreeNode {
int key{};
BSTreeNode *parent{};
BSTreeNode *left{};
BSTreeNode *right{};
} typedef BSTreeNode;
class BinSearchTree {
public:
BinSearchTree() {
root = nullptr;
size = 0;
};
BinSearchTree(std::initializer_list<int> list);
void insert(int k);
BSTreeNode *find(int k);
int remove(int k);
void print();
size_t getSize() const;
~BinSearchTree();
private:
BSTreeNode *root;
size_t size;
void freeNodes(BSTreeNode *&rnode);
void printTree(BSTreeNode *node);
void insertNode(BSTreeNode *&rnode, int k, BSTreeNode *pnode);
BSTreeNode **findNode(BSTreeNode *&rnode, int k);
};
BinSearchTree::BinSearchTree(std::initializer_list<int> list) {
root = nullptr;
size = 0;
for (const auto &item : list) {
insertNode(root, item, nullptr);
}
}
BinSearchTree::~BinSearchTree() { freeNodes(root); }
void BinSearchTree::freeNodes(BSTreeNode *&rnode) {
if (rnode != nullptr) {
freeNodes(rnode->left);
freeNodes(rnode->right);
delete rnode;
}
}
BSTreeNode *BinSearchTree::find(const int k) { return *findNode(root, k); }
BSTreeNode **BinSearchTree::findNode(BSTreeNode *&rnode, const int k) {
if (rnode == nullptr) return nullptr;
if (k == rnode->key) return &rnode;
if (k < rnode->key)
return findNode(rnode->left, k);
else
return findNode(rnode->right, k);
}
void BinSearchTree::print() {
if (size > 0)
printTree(root);
else
cout << "tree is empty!" << endl;
}
void BinSearchTree::printTree(BSTreeNode *rnode) {
if (rnode != nullptr) {
printTree(rnode->left);
cout << rnode->key << "; ";
printTree(rnode->right);
}
}
void BinSearchTree::insert(const int k) { insertNode(root, k, nullptr); }
void BinSearchTree::insertNode(BSTreeNode *&rnode, const int k,
BSTreeNode *pnode) {
if (rnode == nullptr) {
rnode = new BSTreeNode;
rnode->key = k;
rnode->parent = pnode;
rnode->left = nullptr;
rnode->right = nullptr;
size++;
} else {
if (k < rnode->key)
insertNode(rnode->left, k, rnode);
else if (k == rnode->key)
return;
else
insertNode(rnode->right, k, rnode);
}
}
size_t BinSearchTree::getSize() const { return size; }
int BinSearchTree::remove(const int k) {
auto ret = findNode(root, k);
if (ret == nullptr) return -1;
if (size == 1) {
auto tmp = root;
root = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left == nullptr && (*ret)->right == nullptr) {
auto tmp = *ret;
if ((*ret)->key < (*ret)->parent->key)
(*ret)->parent->left = nullptr;
else
(*ret)->parent->right = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left != nullptr && (*ret)->right != nullptr) {
auto leftmost = (*ret)->right;
while (leftmost && leftmost->left != nullptr) leftmost = leftmost->left;
(*ret)->key = leftmost->key;
if (leftmost->right != nullptr) {
leftmost->right->parent = leftmost->parent;
auto tmp = leftmost->right;
*leftmost = *leftmost->right;
leftmost->parent->left = leftmost;
delete tmp;
} else {
leftmost->parent->right = nullptr;
delete leftmost;
}
size--;
return 0;
} else {
if ((*ret)->left != nullptr) {
auto tmp = *ret;
*ret = (*ret)->left;
(*ret)->parent = tmp->parent;
delete tmp;
} else {
auto tmp = *ret;
*ret = (*ret)->right;
(*ret)->parent = tmp->parent;
delete tmp;
}
size--;
return 0;
}
}
int main() {
BinSearchTree bst = {6, 5, 11, 3, 2, 10, 12, 4, 9};
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.insert(7);
bst.insert(8);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.remove(6);
bst.remove(2);
bst.remove(12);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
return EXIT_SUCCESS;
}
size of bst = 9
2; 3; 4; 5; 6; 9; 10; 11; 12;
size of bst = 11
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12;
size of bst = 8
3; 4; 5; 7; 8; 9; 10; 11;
가장 복잡한 시나리오는 대상 노드에 두 개의 자식이 있는 경우입니다. 이 경우 이진 검색 트리 구조에 지정된 대로 노드를 올바르게 연결하고 요소 순서를 유지해야 합니다. 대상 노드를 가장 작은 키와 대상 오른쪽 하위 트리의 일부로 교체해야 합니다.
가장 작은 키를 가진 노드는 가장 왼쪽에 있습니다. 따라서 이 노드에 도달할 때까지 오른쪽 하위 트리를 탐색해야 합니다. 노드를 찾으면 해당 키를 대상 노드에 할당한 다음 마치 단일 자식이 있는 노드인 것처럼 전자를 제거하려고 시도할 수 있습니다. 후자는 이 노드가 주어진 하위 트리에서 가장 왼쪽에 있다는 사실에 의해 암시됩니다. 따라서 right 자식만 가질 수 있거나 자식이 전혀 없을 수 있습니다.
이 세 가지 시나리오는 remove 멤버 함수의 별도 if...else 블록에서 구현되지만 요소가 트리에서 발견되지 않거나 마지막 노드가 제거되는 경우와 같은 일부 모서리 경우를 확인하기 위한 추가 코드도 포함되어 있습니다. remove 기능은 재귀적 방식으로도 구현할 수 있습니다.
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook