I have a problem with the cancelation of a node in my binary search tree. The method I implemented for eliminate a node of the tree, eliminates all nodes instead and I don't understand why. This is the Node class:
#include <iostream>
using namespace std;
template <class T>
class Nodo {
private:
T val;
Nodo<T> *sx;
Nodo<T> *dx;
Nodo<T> *padre;
public:
explicit Nodo(T x) {
this->val = x;
}
void setVal(T y) {
this->val = y;
}
T getVal() {return this->val;}
void setPadre(Nodo<T> *x) {
this->padre = x;
}
Nodo<T> *getPadre() {
return this->padre;
}
void setSx(Nodo<T> *n) {
this->sx = n;
}
void setDx(Nodo<T> *n) {
this->dx = n;
}
Nodo *getSx() {return this->sx;}
Nodo *getDx() {return this->dx;}
};
There is the BST class with all the method:
template <typename T>
class BinarySearchTree {
private:
Nodo<T> *radice;
public:
BinarySearchTree() {
radice = nullptr;
}
void insert(T x) {
Nodo<T>* tmp = new Nodo<T>(x);
Nodo<T> *supp = nullptr;
Nodo<T> *radix = radice;
tmp->setSx(nullptr);
tmp->setDx(nullptr);
while (radix != nullptr) {
supp = radix;
if (x < radix->getVal()) {
radix = radix->getSx();
} else {
radix = radix->getDx();
}
}
tmp->setPadre(supp);
if (supp == nullptr) {
radice = tmp;
} else if(x < supp->getVal()) {
supp->setSx(tmp);
} else {
supp->setDx(tmp);
}
}
void _inorder(Nodo<T> *prova) {
if (prova != nullptr) {
_inorder(prova->getSx());
cout << prova->getVal() << " ";
_inorder(prova->getDx());
}
}
void inorder() {
_inorder(radice);
cout << "----" << endl;
}
Nodo<T> *minimum(Nodo<T>* x) {
Nodo<T> *min = x;
while (min->getSx() != nullptr)
min = min->getSx();
return min;
}
Nodo<T> *search(T x) {
Nodo<T> *iter = radice;
if (x < iter->getVal()) {
while (iter->getVal() != x)
iter = iter->getSx();
return iter;
} else {
while (iter->getVal() != x)
iter = iter->getDx();
return iter;
}
}
void transplant(Nodo<T> *u, Nodo<T> *v) {
if (u->getPadre() == nullptr) {
radice = v;
} else if (u == u->getPadre()->getSx()) {
u->getPadre()->setSx(v);
} else {
u->getPadre()->setDx(v);
}
if (v != nullptr)
v->setPadre(u->getPadre());
}
void delTree(T x) {
Nodo<T> *tmp = search(x);
Nodo<T> *supp = nullptr;
if (tmp->getSx() == nullptr)
transplant(tmp, tmp->getDx());
else if (tmp->getDx() == nullptr)
transplant(tmp, tmp->getSx());
else {
supp = minimum(tmp->getDx());
if (supp->getPadre() != tmp) {
transplant(supp, supp->getDx());
supp->setDx(tmp->getDx());
supp->getDx()->setPadre(supp) ;
}
transplant(tmp, supp);
supp->setSx(tmp->getSx());
supp->getSx()->setPadre(supp);
}
}
};
int main() {
BinarySearchTree<int> bst;
bst.insert(30);
bst.insert(10);
bst.insert(50);
bst.insert(2);
bst.inorder();
bst.delTree(2);
bst.inorder();
}
Now, when I call the delTree method with any node, it eliminates all nodes. Can anyone help me to understand where is the error in the code? Thank you!
Edit: I add the search() method in BST class and modified the tmp assignment in delTree() method and now it works fine!
With the edits you have made, your function delTree is looking good. Problems with function search, however caused it to crash, when I ran the following example.
void example() {
BinarySearchTree<int> bst;
bst.insert(0);
bst.insert(2);
bst.insert(1);
bst.insert(3);
bst.inorder();
bst.delTree(1);
bst.inorder();
bst.delTree(100);
bst.inorder();
}
Exception thrown at 0x00007FF733062C47 in StackOverflow.exe: 0xC0000005: Access violation reading location 0x0000000000000000.
The exception was thrown when executing in the second loop of the search routine.
Nodo<T>* search(T x) {
Nodo<T>* iter = radice;
if (x < iter->getVal()) {
while (iter->getVal() != x)
iter = iter->getSx();
return iter;
}
else {
while (iter->getVal() != x)
iter = iter->getDx(); // <--------------- Access violation
return iter;
}
}
Evidently, variable iter had the value nullptr, and was then dereferenced.
Looking at the code you can see what happened. The loop chains down the right side of the tree, looking for x, and when it fails to find it, iter gets the nullptr.
And that's the other problem. When x lies on the left half of the tree, search only checks the left child of each node. Similarly, when x is in the right half of the tree, search only scans the right child nodes.
You can fix both problems by using a recursive search.
Nodo<T>* search(T const x)
{
// Search the tree for a node with the value `x`.
// If found, return a pointer to the node.
// If `x` is not in the tree, return `nullptr`.
return search(x, radice);
}
Nodo<T>* search(T const x, Nodo<T>* const ptr)
{
if (!ptr) return nullptr;
if (x == ptr->getVal()) return ptr;
if (x < ptr->getVal()) return search(x, ptr->getSx());
return search(x, ptr->getDx());
}
When function search fails, because x is not in the tree, it returns nullptr. You need to check for this at the top of function delTree.
void delTree(T x) {
Nodo<T>* tmp = search(x);
if (tmp == nullptr) return;
//...
}
After removing a node from the tree, you should call operator delete on it. Otherwise, your program will leak memory. I've added the call right at the end of function delTree.
void delTree(T x) {
// ...
transplant(tmp, supp);
supp->setSx(tmp->getSx());
supp->getSx()->setPadre(supp);
}
delete tmp; <-------------- Avoid memory leaks
}
When you get your class working, you should add some "Rule of Five" functions, so that that you can copy, move, and assign trees without leaking memory or triggering double-deletes.