Supprimer un nœud de l'arborescence de recherche binaire en C++
Cet article explique comment implémenter une fonction pour supprimer un nœud dans la structure de données de l’arborescence de recherche binaire C++.
Supprimer le nœud dans l’arbre de recherche binaire en C++
Un arbre de recherche binaire est un type d’arbre binaire qui stocke une valeur clé dans chaque nœud. Cette clé est utilisée pour construire un arbre ordonné de sorte que la clé de chaque nœud soit supérieure à toutes les clés de son sous-arbre gauche et inférieure aux clés de son sous-arbre droit.
Chaque nœud comprend généralement deux pointeurs vers les nœuds left et right, mais nous avons également ajouté un autre pointeur pour désigner le nœud parent car il est plus facile d’implémenter la fonction de membre remove.
Notez que l’implémentation d’arbre de recherche binaire suivante n’inclut que le strict minimum des fonctions membres pour démontrer une opération de suppression de nœud.
La classe BinSearchTree est capable de stocker uniquement des types int comme valeurs de clé. La plupart des fonctions, à l’exception de remove, utilisent la récursivité, nous fournissons donc des fonctions membres private correspondantes qui sont appelées en interne. Généralement, la suppression d’un nœud de l’arborescence est une opération plus complexe que l’insertion et la recherche, car elle implique plusieurs scénarios.
Le premier et le plus simple des scénarios est celui où nous devons supprimer un nœud sans enfant (par conséquent appelé nœud feuille). Les nœuds feuilles peuvent être désalloués et nullptr assignés au pointeur correspondant de son parent.
Le deuxième cas consiste à supprimer le nœud avec un seul enfant. Ce dernier peut être résolu en connectant le parent de la cible à son enfant, puis on peut désallouer la mémoire associée.
#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;
Le scénario le plus compliqué est lorsque le nœud cible a deux enfants. Dans ce cas, nous devons connecter correctement les nœuds et conserver l’ordre des éléments tel que spécifié pour la structure arborescente de recherche binaire. Nous devons remplacer le nœud cible par la plus petite clé et une partie du sous-arbre droit de la cible.
Le nœud avec la plus petite clé se trouve à l’endroit le plus à gauche. Ainsi, nous devons traverser le sous-arbre de droite jusqu’à ce que nous atteignions ce nœud. Une fois le nœud trouvé, nous pouvons affecter sa clé au nœud cible, puis essayer de supprimer l’ancien comme s’il s’agissait d’un nœud avec un seul enfant. Ce dernier est impliqué par le fait que ce nœud est le plus à gauche dans le sous-arbre donné. Ainsi, il ne peut avoir qu’un enfant right ou pas d’enfant du tout.
Ces trois scénarios sont implémentés dans un bloc if...else séparé dans la fonction membre remove, mais nous incluons également du code supplémentaire pour vérifier certains cas particuliers, comme lorsque l’élément n’est pas trouvé dans l’arborescence ou que le dernier nœud est supprimé. Notez que la fonction remove peut également être implémentée de manière récursive.
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 FacebookArticle connexe - C++ Data Structure
- Empiler la structure de données à l'aide d'une liste chaînée en C++
- Implémenter Inorder Traversal pour l'arbre de recherche binaire en C++
- Implémenter un tableau circulaire en C++
- Implémenter une structure de données de file d'attente à l'aide d'une liste chaînée en C++
- Insertion d'arbre de recherche binaire en C++
- Liste circulaire doublement chaînée en C++