CODEWITHSUNDEEP
c++memorytreeavl-tree
octavio
octavio

Reputation: 486

Binary tree, delete Node after removing it from the tree

I am implementing an AVL-Tree. Removing nodes from the tree is working as expected, e.g. if I remove the left leaf of a node, the nodes left child will point to nullptr.

However, since that (now removed) node was once created with the 'new'-keyword, is it necessary to somehow free the memory it takes up? My Node looks like this:

    struct Node {
       const int key;
       short balance = 0;
       Node* left = nullptr;
       Node* right = nullptr;

       Node(const int key);
       Node(const int key, Node *left, Node *right);
       ~Node();
    }

What I am saying is: even tho the removed node is not included in the tree anymore, e.g. nothing is pointing to it, does it go 'out of scope' and is removed from memory automatically? Or do I have to set it's right/left-pointers to nullptr?

Thanks!

Upvotes: 1

Views: 214

Answers (2)

Felix
Felix

Reputation: 2668

In short: Yes. You have to free the memory. To my knowledge C++ only automatically deallocates memory for objects that are declared without 'new'. They are deleted as the function returns. You could have the delete node function return the memory address of the deleted node, or just delete it inside the function once it's found.

And to clarify, no you don't have to free any memory, as it is free'd as the program exits, but memory leaks are a bad time once the program or its execution time grows.

Upvotes: 0

Drax
Drax

Reputation: 13278

However, since that (now removed) node was once created with the 'new'-> keyword, is it necessary to somehow free the memory it takes up?

It is not mandatory but if you want to avoid eating all your RAM at some point then yes you need to, and you do so with the delete keyword

What I am saying is: even tho the removed node is not included in the tree anymore, e.g. nothing is pointing to it, does it go 'out of scope' and is removed from memory automatically?

No, there is no garbage collector in c++

There are more "modern" ways to do what you are doing but i feel like it is more a learning exercise than something else, in which case matching your delete calls with your new calls manually is a good way to understand what's going on. If you want though you can search for "smart pointers".

Upvotes: 1

Related Questions