Eliminar un nodo del árbol binario de búsqueda en C++
Este artículo explicará cómo implementar una función para eliminar un nodo en la estructura de datos del árbol binario de búsqueda C++.
Eliminar nodo en el árbol binario de búsqueda en C++
Un árbol de búsqueda binario es un tipo de árbol binario que almacena un valor clave en cada nodo. Esta clave se utiliza para construir un árbol ordenado de modo que la clave de cada nodo sea mayor que todas las claves en su subárbol izquierdo y menor que las claves en su subárbol derecho.
Cada nodo generalmente incluye dos punteros a los nodos left y right, pero también agregamos otro puntero para denotar el nodo padre, ya que es más fácil implementar la función de miembro remove.
Tenga en cuenta que la siguiente implementación del árbol binario de búsqueda solo incluye el mínimo básico de las funciones miembro para demostrar una operación de eliminación de nodos.
La clase BinSearchTree es capaz de almacenar sólo tipos int como valores clave. La mayoría de las funciones, excepto remove, utilizan la recursividad, por lo que proporcionamos las funciones miembro private correspondientes que se invocan internamente. Generalmente, eliminar un nodo del árbol es una operación más compleja que la inserción y la búsqueda, ya que implica múltiples escenarios.
El primer escenario y el más simple es cuando necesitamos eliminar un nodo sin hijos (en consecuencia, denominado nodo hoja). Los nodos hoja se pueden desasignar y asignar nullptr al puntero correspondiente de su padre.
El segundo caso es eliminar el nodo con un solo hijo. Este último se puede resolver conectando el padre del objetivo con su hijo, y luego podemos desasignar la memoria asociada.
#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;
El escenario más complicado es cuando el nodo de destino tiene dos hijos. En este caso, necesitamos conectar correctamente los nodos y mantener el orden de los elementos como se especifica para la estructura del árbol binario de búsqueda. Necesitamos reemplazar el nodo objetivo con la clave más pequeña y parte del subárbol derecho del objetivo.
El nodo con la clave más pequeña se encuentra en el lugar más a la izquierda. Por lo tanto, debemos atravesar el subárbol derecho hasta llegar a este nodo. Una vez que se encuentra el nodo, podemos asignar su clave al nodo de destino y luego intentar eliminar el anterior como si fuera un nodo con un solo hijo. Esto último está implícito en el hecho de que este nodo es el más a la izquierda en el subárbol dado. Por lo tanto, sólo puede tener un hijo right o ningún hijo en absoluto.
Estos tres escenarios se implementan en un bloque if...else separado en la función de miembro remove, pero también incluimos código adicional para verificar algunos casos de esquina, como cuando el elemento no se encuentra en el árbol o se elimina el último nodo. Tenga en cuenta que la función remove también se puede implementar de forma recursiva.
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