C++

Forum

 
Memory leak after removing word from binary tree.

Bram van Velzen (7)
I've made a binary tree for which I have written a function to remove a word. I change the pointers in such a way that the tree is sorted again correctly but I don't succeed at removing the branch itself.

From one cpp-file.
1
2
3
4
5
6
7
8
9
10
 

void tree::remove(string word)
{
	if (!_root)
		return; // If there is no tree, do nothing

    branch* dead_branch = _root->remove(word, &_root);
    if (dead_branch)
        delete dead_branch;  // delete the branch if it was extracted.
}


From the other cpp-file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
branch* branch::remove(string word, branch** ptr_to_branch_ptr)
	{
		if (word.compare(_word)<0)
		{
			if(_left)
				_left->remove(word, &_left);
		}

		if (word.compare(_word)>0)
		{
			if (_right)
				_right->remove(word, &_right);
		}

		if (word.compare(_word) == 0)
		{
			if (_left)
			{
				branch* point;
				point = _left->find_branch_with_largest_word();
				point->_right = _right;
				*ptr_to_branch_ptr = _left;
			}
			else
				*ptr_to_branch_ptr = _right;

 			_left = 0;
			_right = 0;
			return this;
		}
		return 0;
}



branch* branch::find_branch_with_largest_word()
{
    if (_right)
        return _right->find_branch_with_largest_word();
    else
        return this;
}
Last edited on
Bram van Velzen (7)
No answer yet, it must have been busy at this forum.
I found the answer on my own, it turns out to be pretty simple but given that this is only the second time that I use this concept it is hard to think about it. I simply had to return after each call and not only when the word was found. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
branch* branch::remove(string word, branch** ptr_to_branch_ptr)
	{
		if (word.compare(_word)<0)
		{
			if(_left)
				return _left->remove(word, &_left);
		}

		if (word.compare(_word)>0)
		{
			if (_right)
				return _right->remove(word, &_right);
		}

		if (word.compare(_word) == 0)
		{
			if (_left)
			{
				branch* point;
				point = _left->find_branch_with_largest_word();
				point->_right = _right;
				*ptr_to_branch_ptr = _left;
			}
			else
				*ptr_to_branch_ptr = _right;

 			_left = 0;
			_right = 0;
			return this;
		}
		return 0;
}



branch* branch::find_branch_with_largest_word()
{
    if (_right)
        return _right->find_branch_with_largest_word();
    else
        return this;
}
Topic archived. No new replies allowed.