2

Good evening. I get an access violation exception error when trying to destroy my BST. There have been posts about this before and I copied their accepted answer's reply and still didn't get the expected result. So I have this binary search tree implementation. Everything works well, until my code reaches the "return 0" from my int main() function.

I'll leave some code for you. 

PQBST::~PQBST()
{
    destroy();
}

inline void PQBST::destroy()
{
    if (root)
        destroy(root);
}

void PQBST::destroy(Node* node)
{
    if (node->left) // this is where it gives me and access violation exception 0xDDDDDDDD
        destroy(node->left);
    if (node->right)
        destroy(node->right);
    delete node;
}

I know that this kind of error is thrown when you try to delete something that had been already deallocated, but I can't figure out why it would try to destroy my BST twice when I call the destroy function just once in my application (when I'm done with it). I commented the part where I manually destroy my BST, and after reaching "return 0", it gives me again 

Unhandled exception thrown: read access violation.
node was 0xFF12C6AB

so it is not 0xDDDDDDDD but still an error . :|

My nodes look like this:

struct Node
{
    Human info;
    Node * left;
    Node * right;
    Node() {};
    Node(Human value)
        : info(value), left(NULL), right(NULL)
    {

    }
};

My BST class only has Node* root . I hope I gave you enough information. Thank you.

Edit: My nodes look like this now: 

    struct Node
{
    Human info;
    Node * left;
    Node * right;
    Node() { left = NULL, right = NULL;  }
    Node(Human value): info(value), left(NULL), right(NULL){}
    Node(Human value, Node* left, Node* right) : info(value), left(left), right(right) {}
    Node& operator=(const Node& n)
    {
        info = n.info;
        left = n.left;
        right = n.right;

        return *this;
    }

    Human getInfo() const { return info; }
    Node* getLeft() { return left; }
    Node* getRight() { return right;  }
    ~Node() { };
};

My PQBST:

class PQBST
{
private:
    Node * root;
    int m; //spaceship size - given by the user

public:
    PQBST() { root = NULL; }
    PQBST(int m) : root(NULL), m(m) {}
    PQBST(Node* root, int m);
    ~PQBST();

PQBST::PQBST(Node * root, int m)
{
    this->root = root;
    this->m = m;
}
Bryuki HK
  • 41
  • 4
  • Nothing in `void PQBST::destroy(Node* node)` checks for non-`NULL` before dereferencing and accessing members. – user4581301 Jun 01 '18 at 23:14
  • `Node() {};` leaves `left` and `right` uninitialized. Lots of potential for an ill doom. – user4581301 Jun 01 '18 at 23:17
  • According to [the big list of magic numbers at Wikipedia](https://en.wikipedia.org/wiki/Magic_number_(programming)), 0xDDDDDDDD is memory that has already been freed. Make certain you have correctly implemented [the Rule of Three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) – user4581301 Jun 01 '18 at 23:20
  • Too many open bug possibilities. Voting to close. Recommend narrowing the problem down with a [mcve]. – user4581301 Jun 01 '18 at 23:20
  • Alright, I'll try looking up what you said. Thank you! *sorry for not having a minimal enough example, I didn't know what else to add. – Bryuki HK Jun 01 '18 at 23:22
  • It's not the minimal you have to watch out for, it the combination of minimal and complete, targeting one and only one bug. The true beauty of the MCVE is as you reduce the code down to One bug and nothing but that one bug you almost always find the problem yourself. It's one of the most effective debugging techniques out there, if a little slow. – user4581301 Jun 01 '18 at 23:38
  • Whoever voted to close this is completely off-base. This is in no way off-topic, and it's a good question. And, just randomly picking a close reason when your opinion doesn't match one of the given options isn't in line with the spirit, or rules, of the site. – 3Dave Jun 02 '18 at 00:01
  • Update your question to include the constructor for `PQBST`, including where your are initializing `root`. At the very least, the ctor for `PQBST` should set `root = nullptr;` – 3Dave Jun 02 '18 at 00:03
  • Another issue is that your assignment overload is doing a shallow copy, which will definitely be an issue if you're making copies of your `PQBST` or any `Node` at any point. – 3Dave Jun 02 '18 at 00:10
  • in ::destroy(), set root to null after you've destroyed it. also, make sure root is set to null in the constructor. – thang Jun 02 '18 at 00:11

2 Answers2

2

If you are going do delete your BST I suggest doing a post order traversal. This would visit the left, right recursively and then the delete the node. This would work provided the tree was constructed correctly.

void PQBST::destroy(Node* node)
{
    if (!node) return;
    destroy(node->left);
    destroy(node->right);
    delete node;
}

Having said that, I would suggest moving away from trying to manually manage memory and use std::unique_ptr<T> where T is your node type. I would define them in your BST as std::unique_ptr<Node> left, right;. This avoids the problem altogether.

Samer Tufail
  • 1,835
  • 15
  • 25
  • the `if(!node) return` is really what's missing. At some point, OP is releasing a PQBST that doesn't have a valid `root`. Good call. – 3Dave Jun 02 '18 at 00:01
  • 1
    So, I tried everything you guys said. I also debugged the return 0 and apparently it goes through all the "~PQBST" methods (I don't know why) and it crashes at :inline void PQBST::destroy() { if (root) destroy(root); } . Since my root isn't NULL (but contains some junk stuff) it keeps going and hits another junk node->left . – Bryuki HK Jun 02 '18 at 00:04
  • I would move away from managing the memory altogether and use unique_ptr. – Samer Tufail Jun 02 '18 at 00:04
  • Unfortunately this is a structures and data algorithms class project (a priority queue implemented on BST) and I'm not allowed to use things that would make life easier... – Bryuki HK Jun 02 '18 at 00:06
  • 1
    @BryukiHK now in your `~PQBST()` you don't need `delete(root)` all you need is to call the function `destroy(root);` that's it. – Samer Tufail Jun 02 '18 at 00:06
  • @BryukiHK At the risk of starting a discussion in comments: any time an object goes out of scope - you can google that,and you really, really should if you don't understand it - its destructor gets called. Also, whenever you do a `delete` on a member, set its value to `null` or `nullptr` immediately afterward. Race conditions are evil. – 3Dave Jun 02 '18 at 00:08
  • I see. I didn't know that , thank you. Also, I added node = NULL; after the delete node in my destroy method. Still getting some access violation error. – Bryuki HK Jun 02 '18 at 00:16
0

I know that this kind of error is thrown when you try to delete something that had been already deallocated, but I can't figure out why it would try to destroy my BST twice when I call the destroy function just once in my application (when I'm done with it).

Not sure if I interpret what you said above (in bold) correctly, but aren't you calling PQBST::destroy() already in PQBST::~PQBST()? If you call PQBST::destroy() also manually, would it be called twice when the destructor is called?

Edy
  • 462
  • 3
  • 9