I made a Binary Search Tree (node) class:
class BstNode {
public:
BstNode(int value);
~BstNode();
BstNode* Delete(int value);
// more methods
private:
int value_;
BstNode* left_;
BstNode* right_;
};
With a destructor that looks like this:
BstNode::~BstNode() {
delete left_;
delete right_;
}
And a Delete function:
BstNode* BstNode::Delete(int value) {
// If the value to be deleted is smaller than the root's key,
// then it lies in the left subtree.
if (value < value_) {
if (left_ == nullptr) return nullptr;
else left_ = left_->Delete(value);
}
// If the value to be deleted is larger than the root's key,
// then it lies in the right subtree.
else if (value > value_) {
if (right_ == nullptr) return nullptr;
else right_ = right_->Delete(value);
}
// If the key to be deleted is the same as root's key, then *this*
// is the node to be deleted.
else {
// If this node has no children, then we can just delete it.
if (left_ == nullptr && right_ == nullptr) {
delete this;
return nullptr;
}
// If this node has one child, then we can just set this node to
// that child and delete this node afterwards.
else if (left_ == nullptr) {
BstNode* temp = right_;
delete this;
return temp;
}
else if (right_ == nullptr) {
BstNode* temp = left_;
delete this;
return temp;
}
// If this node has two children, then we have to get the "in-order successor"
// (the smallest node in the right subtree).
else {
BstNode *temp = right_->Smallest();
// Copy that node's value to this node
value_ = temp->value_;
// Then delete that value from the right subtree
right_ = right_->Delete(value_);
}
}
return this;
}
What I'm confused about is this snippet:
else if (left_ == nullptr) {
BstNode* temp = right_;
delete this;
return temp;
}
else if (right_ == nullptr) {
BstNode* temp = left_;
delete this;
return temp;
}
If the call to delete calls the class's destructor, wouldn't I end up deleting the entire sub-tree (right or left)? However, when testing, it looks like the tree is doing exactly the thing I want it to do: delete a node, and "move up" the child sub-tree to where "this" is - with the sub-trees still intact.
Doing BstNode* temp = this;, to my knowledge, would just copy the pointers to left_ and right_, then the delete this call should destroy the data behind them.
Am I missing something about delete this?
this->left_andthis->right_tonullptrbefore deletingthis- would this be the way to fix it?BstNodeeven have a destructor that destroys the left and right tree? What if you want to remove just that one node? It's just simpler to do this the "classical" way, where you traverse to the node you want to delete, isolate that one node, go through the algorithm to splice the existing branch onto where the node to delete would go, and just delete the node you isolated previously. Then you don't have to worry about trying to avoid the "cascading delete" calls.BstNode::Deletefunction is meant to delete just one node instead of the entire subtree -- which is why I was a little confused when I tried my code and it worked. Like @1201ProgramAlarm said, it turns out that you'd get dangling pointers -- which is "fine" (not really), until you re-use that memory location later (I think?). I think I like the method of settingleft_andright_tonullptrfirst before deletingthis, just because that way I keep preventing memory leaks.