C ++ Destructor, EXC_BAD_ACCESS, Can't access memory
I am planning on using a sorted array to build a balanced binary search tree. Everything worked until the end of the program. It seems that the binary search tree destructor has some problems.
Error information:
Software received signal EXC_BAD_ACCESS, Unable to access memory. Reason: KERN_PROTECTION_FAILURE at address: 0x00007fff5f3ffff8 0x0000000100002857 at BST_Node :: ~ BST_Node (this = 0x100100920) at BST_Node.h: 18 ~ BST_Node () {delete parent; remove the left one; Remove the right;}
#ifndef BST_NODE_H
#define BST_NODE_H
#include <cstddef>
class BST_Node {
public:
BST_Node(int k) : key(k), parent(NULL), left(NULL), right(NULL) {}
~BST_Node() {if (parent!=NULL) delete parent;if (left!=NULL) delete left;if (right!=NULL) delete right;}
// data member
int key;
BST_Node* parent;
BST_Node* left;
BST_Node* right;
};
#endif
#include <iostream>
#include <vector>
#include "BST_Tree.h"
#include "BST_Node.h"
using namespace std;
// use recursion to construct the tree. Find the mid of the array to be the root of the subtree. Use left part of the array to construct the left subtree and right part to construct the right subtree.
BST_Node* CreateTree(vector<int> &a, int start, int end) {
if (end<start) {
return NULL;
} else {
int mid = (start+end+1)/2;
BST_Node* p = new BST_Node(a[mid]);
BST_Node* l_tmp = CreateTree(a, start, mid-1);
if (l_tmp)
l_tmp->parent = p;
p->left = l_tmp;
BST_Node* r_tmp = CreateTree(a, mid+1, end);
if (r_tmp)
r_tmp->parent = p;
p->right = r_tmp;
return p;
}
}
int main() {
vector<int> a;
a.push_back(0);
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
a.push_back(6);
BST_Tree t;
t.root = CreateTree(a, 0, 6);
t.InOrderWalk(t.root);
return 0;
}
Many thanks!
source to share
Any ownership relationship (where an object is responsible for deleting another when that object is no longer needed) should not have cycles. In your case, you have parent nodes that their children own and vice versa.
When the root node is removed, the constructor will first remove the left child. The child's destructor will remove the parent that has already been removed.
A typical ownership relationship in a tree is that parent nodes own their children. Children have a pointer to a parent, which is not responsible. This pointer will remain valid for the lifetime of the child node, because the child will be removed as part of destroying the parent.
So, your destructor should simply do:
BST_Node::~BST_Node() {
delete left;
delete right;
}
Additional Notes:
- You don't need to check for NULL pointers - deleting a null pointer is safe and won't do anything.
- You should prevent copying of BST_Node objects. The implicitly defined copy constructor and copy assignment operator to another object that owns the same child nodes are also double deleting objects.
The best way to express the semantics of pointer ownership is to use an appropriate smart pointer class. In your case, the most appropriate declaration would be
class BST_Node {
public:
~BST_Node() = default; // you can simply omit this completely
// other things
BST_Node* parent; // no ownership
std::unique_ptr<BST_Node> left; // exclusive ownership
std::unique_ptr<BST_Node> right;
};
As a useful side effect of this, implicitly generated copy operations will be suppressed because std::unique_ptr<T>
they cannot be copied.
source to share
Just by running the code I see the problem in this segment
if (l_tmp)
l_tmp->parent = p;
p->left = l_tmp;
BST_Node* r_tmp = CreateTree(a, mid+1, end);
if (r_tmp)
r_tmp->parent = p;
p->right = r_tmp;
l_tmp->parent
and r_tmp->parent
both point to the same node p
. Hence, there is double deletion of node p, once when the l_tmp destructor is called and again when the r_tmp destructor is called. This may be the reason why you are seeing the error. As Andy suggested in a comment, this seems to be a good scenario for using smart pointers.
source to share