Excluir um nó da árvore binária de busca em C++
Este artigo irá explicar como implementar uma função para excluir um nó na estrutura de dados da árvore binária de busca C++.
Excluir nó na árvore binária de busca em C++
Uma árvore binária de busca é um tipo de árvore binária que armazena um valor-chave em cada nó. Essa chave é usada para construir uma árvore ordenada de forma que a chave de cada nó seja maior do que todas as chaves em sua subárvore esquerda e menor que as chaves em sua subárvore direita.
Cada nó geralmente inclui dois ponteiros para os nós left e right, mas também adicionamos outro ponteiro para denotar o nó pai, pois é mais fácil implementar a função de membro remove.
Observe que a implementação da árvore binária de busca a seguir inclui apenas o mínimo das funções de membro para demonstrar uma operação de remoção de nó.
A classe BinSearchTree é capaz de armazenar apenas tipos int como valores-chave. A maioria das funções, exceto remove, utiliza recursão, portanto, fornecemos funções-membro private correspondentes que são chamadas internamente. Geralmente, remover um nó da árvore é uma operação mais complexa do que inserir e pesquisar, pois envolve vários cenários.
O primeiro e mais simples cenário é quando precisamos remover um nó sem filhos (conseqüentemente referido como nó folha). Os nós folha podem ser desalocados e nullptr atribuído ao ponteiro correspondente de seu pai.
O segundo caso é remover o nó com apenas um filho. O último pode ser resolvido conectando o pai do alvo ao seu filho, e então podemos desalocar a memória associada.
#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;
O cenário mais complicado é quando o nó de destino tem dois filhos. Nesse caso, precisamos conectar corretamente os nós, bem como reter a ordem dos elementos conforme especificado para a estrutura da árvore binária de busca. Precisamos substituir o nó de destino pela menor chave e parte da subárvore direita do destino.
O nó com a menor chave é encontrado no lugar mais à esquerda. Portanto, devemos percorrer a subárvore direita até chegarmos a este nó. Assim que o nó for encontrado, podemos atribuir sua chave ao nó de destino e, em seguida, tentar remover a anterior como se fosse um nó com um único filho. O último está implícito no fato de que este nó é o mais à esquerda na subárvore fornecida. Assim, só pode ter um filho right ou nenhum filho.
Esses três cenários são implementados em bloco if...else separado na função de membro remove, mas também incluímos código adicional para verificar alguns casos esquivos, como quando o elemento não é encontrado na árvore ou o último nó é removido. Observe que a função remove também pode ser implementada de maneira 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