[try Beta version]
Not logged in

 
Binary tree remove function

Jul 8, 2015 at 3:44pm
cppnoob25 (165)
Why do I get a segmentation fault here?

Where do I violate memory access?

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
 
void BTree::del(int x)
{
    del(&root, x);
}

void BTree::del(Node ** n, int x)
{
    if(root == nullptr)
    {
        cout << "Tree is empty" << endl;
    }
    else
    {
        Node * current = *n;
        Node * temp;

        while(current -> data != x)
        {
            temp = current;

            if(current->data < x)
            {
                current = current->right;
            }
            else if(current->data > x)
            {
                current = current->left;
            }
        }

        //case 1 no left or right child
        if(current->left == nullptr && current->right == nullptr)
        {
            delete current;
            current = nullptr;
            cout << " Node has been deleted " << endl;
        }
    }
}
Jul 8, 2015 at 3:51pm
MiiNiPaa (8886)
while(current -> data != x) What if there is no x in your tree?

delete current;What about node which points to current?

And what if there is left or right child in node containing x?
Jul 8, 2015 at 4:00pm
cppnoob25 (165)
Hey MiiNiPaa so my delete current is causing this problem?

And for right now I'm just taking this a step at a time. I will handle that case and also the case where it has both a left and right child after I work out this first case.

I did not think about not having x in my tree though I will fix that one.

Jul 8, 2015 at 4:27pm
MiiNiPaa (8886)
Yes, delete current; will delete this node, but will leave pointer to it in its parent untouched. Now it is pointing to invalid data.
Jul 8, 2015 at 4:38pm
cppnoob25 (165)
I made this change and it compiled. Thanks MiiNiPaa.

An inorder traversal shows that the nodes gone too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
        if(current->left == nullptr && current->right == nullptr)
        {
            if(temp->right == current)
            {
                temp->right = nullptr;

            }
            else
            {
                temp->left = nullptr;
            }
            delete current;
            cout << "Node has been deleted " << endl;
        }


Last edited on Jul 8, 2015 at 4:40pm
Jul 8, 2015 at 4:50pm
cppnoob25 (165)
Hey MiiNiPaa, this handles the case where x doesn't exist but is this a good way to handle that?

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
        void BTree::del(Node ** n, int x)
{
    if(root == nullptr)
    {
        cout << "Tree is empty" << endl;
    }
    else
    {
        Node * current = *n;
        Node * temp;

        while(current -> data != x)
        {
            temp = current;

            if(current->data < x)
            {
                if(current->right == nullptr)
                {
                    current = nullptr;
                    break;
                }
                current = current->right;
            }
            else if(current->data > x)
            {
                if(current->left == nullptr)
                {
                    current = nullptr;
                    break;
                }
                current = current->left;
            }
        }

        if(current == nullptr)
        {
            cout << "Data does not exist in tree" << endl;
        }
        //case 1 no left or right child
        else if(current->left == nullptr && current->right == nullptr)
        {
            if(temp->right == current)
            {
                temp->right = nullptr;

            }
            else
            {
                temp->left = nullptr;
            }
            delete current;
            cout << "Node has been deleted " << endl;
        }
        //case 2 has at least one child node.
        //else if()
    }
}
Last edited on Jul 8, 2015 at 4:51pm
Jul 8, 2015 at 4:51pm
MiiNiPaa (8886)
Well, it is okay way to handle that.
Jul 8, 2015 at 6:07pm
cppnoob25 (165)
This is what I came up with. I just have no idea how to handle deleting the root node.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
void BTree::del(Node ** n, int x)
{
    if(root == nullptr)
    {
        cout << "Tree is empty" << endl;
    }
    else
    {
        Node * current = *n;
        Node * temp;
        Node * t = nullptr;

        while(current -> data != x)
        {
            temp = current;

            if(current->data < x)
            {
                if(current->right == nullptr)
                {
                    current = nullptr;
                    break;
                }
                current = current->right;
            }
            else if(current->data > x)
            {
                if(current->left == nullptr)
                {
                    current = nullptr;
                    break;
                }
                current = current->left;
            }
        }

        if(current == nullptr)
        {
            cout << "Data does not exist in tree" << endl;
        }
        //case 1 no left or right child
        else if(current->left == nullptr && current->right == nullptr)
        {
            if(temp->right == current)
            {
                temp->right = nullptr;
            }
            else
            {
                temp->left = nullptr;
            }
            delete current;
            cout << "Node has been deleted " << endl;
        }
        //case 2 has at least one child node.
        else if((current->right == nullptr && current->left != nullptr)||
                (current->left == nullptr && current->right != nullptr))
        {
            if(current->right == nullptr)
            {
                if(current->left->data < temp->data)
                {
                    temp->left = current->left;
                }
                else
                {
                    temp->right = current->right;
                }
                cout << current->data <<" has been deleted." << endl;
                delete current;
            }
            else
            {
                if(current->right->data < temp->data)
                {
                    temp->left = current->right;
                }
                else
                {
                    temp->right = current->left;
                }
                cout << current->data <<" has been deleted." << endl;
                delete current;
            }
        }
        //case 3 Node has 2 children
        else if(current->left != nullptr && current->right != nullptr)
        {
            current->data = current->right->data;
            temp = current->right;
            current->right = temp->right;

            if(temp->left != nullptr)
            {
                t = temp->left;
            }

            delete temp;
            temp = current->right;

            while(temp != nullptr)
            {
                temp = temp->left;
            }

            if(t != nullptr)
            {
                temp->left = t;
            }
        }
         delete t;
    }
}
Last edited on Jul 8, 2015 at 6:09pm
Jul 8, 2015 at 6:19pm
MiiNiPaa (8886)
Jul 8, 2015 at 8:12pm
cppnoob25 (165)
Lets say I insert 15 , 10 ,5 , 12 in that order.

So it looks like this:

   15
  /  \
10     NULL
/  \
5  12




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void BTree::rotate(Node ** n)
{
    Node * temp = *n;
    Node * current = nullptr;
    *n= temp->left;

    if(temp->right == nullptr)
    {
        if((*n)->right != nullptr)
        {
            current = (*n)->right;
            (*n)->right = temp;
            temp->left = current;
        }
        else
        {
            (*n)->right = temp;
        }
    }
}


After running this code the tree looks like this. Am I headed in the right direction with this? And because of this I caught errors in my 2nd case for delete.

   10
  /  \
5     15
    /
   12



I pass this inside the delete function 

1
2
3
4
 
        if((*n)->data == x)
        {
            rotate(n);
        }
Last edited on Jul 8, 2015 at 8:34pm
Jul 8, 2015 at 9:30pm
MiiNiPaa (8886)
I suggest to read second link too, it might be easier to understnd and implement.

If root has only one child, then deleting root is simple: just make that child new root.
If it has two children, implement swapping trick mentioned there.
Jul 8, 2015 at 10:43pm
cppnoob25 (165)
You're right. That is a lot easier. I will look through that link as well.

Thanks for the help MiiNiPaa my understanding on how to deal with deleting a node from a tree is better now.
Jul 12, 2015 at 1:09pm
johnny cash (3)
This is what I came up with.
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
 


void BinaryTree::remove(int item)  //public
{
    remove(root, item);
}

NodePtr BinaryTree::remove(NodePtr& node, int item)  //private
{
    if(node == NULL)
    {
        return;
    }
    else if(item < node->data)
    {
        remove(node->left, item);
    }
    else if(item > node->data)
    {
        remove(node->right, item);
    }
    else    //item == node->data
    {
       NodePtr temp = node;
       if(node->right == NULL)
       {
           node = node->left;
       }
       else if(node->left == NULL)
       {
           node = node->right;
       }
       else
       {
           int min_val = min(node->right);
           remove(node->right, min_val);
           node->data = min_val;
           return;
       }
       delete tmp;
    }
}


and 

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
 
#include <iostream>
#include <cstdio>
#include "Set.h"

using namespace std;

Set::Set()
{
    root = NULL;
    countNode = 0;
}

Set::~Set()
{
    removeAllPrivate(root);

}

void Set::removeAllPrivate(NodePtr node)
{
  if(node != NULL)
  {
      removeAllPrivate(node->left);
      removeAllPrivate(node->right);
      delete node;
  }
  countNode = 0;
}
Jul 12, 2015 at 3:59pm
johnny cash (3)
and min()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int BinaryTree::min()  //public
{
    return min(root);
}

int BinaryTree::min(NodePtr node)  //private
{
    if(node == NULL)
    {
        return INT_MIN;
    }
    if(node->left != NULL)
       {
        return min(node->left);
       }
    return node->data;
}
Topic archived. No new replies allowed.