C++

Forum

 
Binary tree remove function

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;
        }
    }
}
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?
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.

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.
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
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
MiiNiPaa (8886)
Well, it is okay way to handle that.
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
MiiNiPaa (8886)
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
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.
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.
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;
}
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.