C++ の二分探索木からノードを削除する
この記事では、二分探索木データ構造 C++ でノードを削除する関数を実装する方法について説明します。
C++ の二分探索木のノードを削除する
二分探索木は、各ノードにキー値を格納する二分木の一種です。このキーは、各ノードのキーが左側のサブツリーのすべてのキーよりも大きく、右側のサブツリーのキーよりも小さくなるように、順序付けられたツリーを構築するために使用されます。
通常、すべてのノードには left ノードと right ノードへの 2つのポインターが含まれますが、remove メンバー関数の実装が簡単なため、親ノードを示す別のポインターも追加しました。
次の二分探索木の実装には、ノードの削除操作を示すための最低限のメンバー関数のみが含まれていることに注意してください。
BinSearchTree クラスは、キー値として int タイプのみを格納できます。remove を除くほとんどの関数は再帰を利用するため、内部で呼び出される対応する private メンバー関数を提供します。一般に、ツリーからノードを削除することは、複数のシナリオを伴うため、挿入や検索よりも複雑な操作です。
最初の最も単純なシナリオは、子のないノード（したがってリーフノードと呼ばれる）を削除する必要がある場合です。リーフノードの割り当てを解除し、親の対応するポインタに nullptr を割り当てることができます。
2 番目のケースは、子が 1つしかないノードを削除することです。後者は、ターゲットの親をその子に接続することで解決でき、その後、関連するメモリの割り当てを解除できます。
#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;
最も複雑なシナリオは、ターゲットノードに 2つの子がある場合です。この場合、ノードを正しく接続し、バイナリ検索ツリー構造で指定されている要素の順序を保持する必要があります。ターゲットノードを最小のキーとターゲットの右側のサブツリーの一部に置き換える必要があります。
キーが最小のノードが左端にあります。したがって、このノードに到達するまで、右側のサブツリーをトラバースする必要があります。ノードが見つかったら、そのキーをターゲットノードに割り当てて、子が 1つあるノードであるかのように前のノードを削除しようとします。後者は、このノードが特定のサブツリーの左端にあるという事実によって暗示されます。したがって、正しい子のみを持つことも、子をまったく持たないこともできます。
これらの 3つのシナリオは、remove メンバー関数の個別の if...else ブロックに実装されていますが、要素がツリーに見つからない場合や最後のノードが削除された場合など、いくつかのコーナーケースをチェックするための追加コードも含まれています。remove 関数は再帰的に実装することもできることに注意してください。
