[ModusPwnens]

So I am implementing a binary search tree for one of my classes. I got all the functionality down (we were provided with a test file) and the only problem I am having now is memory leakage. Additionally, I have uninitialized memory read, which doesn't make sense to me because everything seems initialized.

A related question is, when should you use new to create objects, and what is the difference? I was able to stop 20 out of the 100 bytes I had leaking previously simply by removing the new operator when I was creating objects. Furthermore, this seemed to have no effect on my test cases at all, which is curious, because I thought when you don't use new to create objects, they go out of scope when the method returns.

Also, here is what I am doing to insert nodes into the BST:

  BSTNode<Data>* nodeInsert(BSTNode<Data>* node, const Data& item) const
  {
    if(item == node->data)
      return 0;
    else if(item > node->data)
    {
      if(node->right != 0)
        return nodeInsert(node->right, item);
      else 
      {
        BSTNode<Data>* newNode = new BSTNode<Data>(item); 
        node->right = newNode;
        newNode->parent = node; 
        return newNode; 
      }
    }
    else if(item < node->data)
    {
      if(node->left != 0)
        return nodeInsert(node->left, item);
      else
      {
        BSTNode<Data>* newNode = new BSTNode<Data>(item); 
        node->left = newNode;
        newNode->parent = node; 
        return newNode; 
      }
    }
  }

And here is what I am doing in my destructor which should free all of the nodes I created:

 void deleteNode(BSTNode<Data>* node)
  {
    if(node->left != 0)
    {
      deleteNode(node->left);
      node->left = 0;
      delete node->left;
    }
    else if(node->right != 0)
    {
      deleteNode(node->right);
      node->right = 0;
      delete node->right;
    }
    else 
    {
      node->parent = 0;
      delete node; 
    }
  }

Both of those are helper functions that are called from another function, if that makes a difference.

This post has been edited by ModusPwnens: 08 October 2010 - 11:31 AM

[Banfa]

Imagine a node that has both a right tree and a left tree but both the nodes of right tree and left tree have no right tree or left tree (i.e. a tree shaped like this /\). Now manually step through your delete node function and see what happens when you delete the top node. Which bits get delete which bits don't.

And btw this

     node->right = 0;
     delete node->right;

is equivalent to

     node->right = 0;
     delete 0;

i.e. you clear the pointer immediately before calling delete making the delete pointless (note the C++ standard specifically states that delete 0; shall work). Of course the setting the pointer to 0 is the only thing that stops your code deleting the same memory block twice (again step through the code and work it out).

[ModusPwnens]

Banfa, on 08 October 2010 - 11:39 AM, said:

Imagine a node that has both a right tree and a left tree but both the nodes of right tree and left tree have no right tree or left tree (i.e. a tree shaped like this /\). Now manually step through your delete node function and see what happens when you delete the top node. Which bits get delete which bits don't.

And btw this

     node->right = 0;
     delete node->right;

is equivalent to

     node->right = 0;
     delete 0;

i.e. you clear the pointer immediately before calling delete making the delete pointless (note the C++ standard specifically states that delete 0; shall work). Of course the setting the pointer to 0 is the only thing that stops your code deleting the same memory block twice (again step through the code and work it out).

Hmm so:

1. The root has a left child, so it calls deleteNode(node->left)
2. This node does not have a left child or a right child, so it just sets the parent to 0 (is this necessary even?) and deletes itself
3. then it sets the left child to 0, and deletes it (but shouldn't this have already been deleted anyways?)
4. The root has a right child, so it calls deleteNode(node->right)
5. This node does not have a left child or a right child, so it just sets the parent to 0 and deletes itself.
6. Then it sets the right child to 0 and deletes it
7. Then the root sets its parent to 0 (which should already be 0) and deletes itself.

Is that correct?

[Munawwar]

Quote

1. The root has a left child, so it calls deleteNode(node->left)
2. This node does not have a left child or a right child, so it just sets the parent to 0 (is this necessary even?) and deletes itself

No don't set the parent to zero.
All you have to do is, for any node - if not NULL - traverse to the left and right nodes and then delete itself.

void deleteNode(BSTNode<Data>* node)
{
   if(node==NULL)
      return;
   deleteNode(node->left);
   deleteNode(node->right);

   delete node;  //First delete...
   node=NULL;   //..then set to NULL
}

[ModusPwnens]

Munawwar, on 08 October 2010 - 12:13 PM, said:

Quote

1. The root has a left child, so it calls deleteNode(node->left)
2. This node does not have a left child or a right child, so it just sets the parent to 0 (is this necessary even?) and deletes itself

No don't set the parent to zero.
All you have to do is, for any node - if not NULL - traverse to the left and right nodes and then delete itself.

void deleteNode(BSTNode<Data>* node)
{
   if(node==NULL)
      return;
   deleteNode(node->left);
   deleteNode(node->right);

   delete node;  //First delete...
   node=NULL;   //..then set to NULL
}

Ah! That makes sense! With the way I was doing it before, some nodes must not have been deleted because of me setting different things to null.

Ok, and now I have one last question:

I have some uninitialized memory read apparently, which is pretty self-explanatory. Anyways, purify is saying that a UMR is occuring here:

  virtual BSTNode<Data>* newNode(Data item) {
    if(isize == 0)
    {
      BSTNode<Data>* newNode = new BSTNode<Data>(item); 
      isize++;
      root = newNode;
    }
    else
    {
      BSTNode<Data> *newNode = 0;
      newNode = nodeInsert(root, item);
      if(newNode != 0)
        isize++;
      return newNode; <---- Here is where it says it is happening. 
    }

nodeInsert is the helper function shown above. This sort of confuses me because it doesn't look like there is anything that is not initialized...

This post has been edited by ModusPwnens: 08 October 2010 - 01:27 PM

[Munawwar]

That shouldn't be happening. Have you initialized parent,right and left to NULL in BSTNode's constructor?
Post the entire code, so we can have a look.

[ModusPwnens]

Munawwar, on 08 October 2010 - 12:58 PM, said:

That shouldn't be happening. Have you initialized parent,right and left to NULL in BSTNode's constructor?
Post the entire code, so we can have a look.

Here is the constructor:

  BSTNode(const Data & d): data(d) {
    left = right = parent = 0;
  }

I could post all the other code, but it spans 3 files and some of it doesn't seem like it would be relevant.

[baavgai]

This is still bugging me...

These are the kind of operations that really belong to an object. Having just raw nodes floating about, assuming the rest of the program will keep track of the root, is messy. Also, parent is not needed and adds extra issues.

I would prefer to see a BST class with the node nice and private.

e.g.

template<class Data>
class Bst {
public:
	Bst();
	~Bst();
	bool isEmpty() const;
	void add(const Data&);
	void clear();
	bool contains(const Data&) const;
	void print(std::ostream &) const;

private:
	struct Node {
		Data data;
		struct Node *left, *right;
		Node(const Data &d) : data(d), left(NULL), right(NULL) {}
	} *root;
	void add(Node *, const Data&);
	void clear(Node *);
	bool contains(Node *, const Data&) const;
	void print(Node *, std::ostream &) const;
};

Now cleanup is implicit, your destructor will take care of it. You needn't worry about starting at the root; you always start at the root. Your user can easily use your BST without worrying about the details. This is what OOP buys you and for ugly abstract data types like this, it makes for much cleaner programs.