Remove from binary search tree

Question

Remove from binary search tree

Navigation

#1 by (3 votes)

3

Studying BST (binary search tree) I did not understand some parts of the code in the delete function of "mycodeschool".

This part of the code, more specifically:

// Case 1:  No child
    if(root->left == NULL && root->right == NULL) { 
        delete root;
        root = NULL;
    }
//Case 2: One child 
    else if(root->left == NULL) {
        struct Node *temp = root;
        root = root->right;
        delete temp;
    }

I do not understand why in "Case 1" as root can receive NULL after receiving the delete command. I could just put root=NULL and only?

And also in "Case 2" When deleting temp , root is also being deleted, is not it? since temp has the same root address.

And because in "Case 1" root=root->right comes before the main command delete and in "Case 2" root=NULL is after the main command delete ?

/ li>

c

asked by anonymous 14.11.2014 / 11:45

1 answer

Clock in Python does not update Web server that receives and sends parameters to C #, is it possible?

score 3 · Accepted Answer

1: No Case 1 you are removing a node that has no children of either the right or the left. Remove it from memory and arrow as null so that the root parent does not point to a memory location that has been 'deallocated';

2 and 3: No, temp has the address of 'old' root because root is now pointing to root->right . In% w / o% it performs the removal operation for nodes that have only 1 child on the right. When it removes% with% of memory, it is removing the old Case 2 since temp now points to the right node so root points to a node that is not in any position of the tree being unnecessary to leave it memory.

4: No root was answered in item 1.

In temp , it first takes the content reference where Case 1 is pointing and stores in Case 2 , causes root to point to the single child node that has the right and then removes temp because it no longer needs it allocated in the memory. That is, it takes the root reference before it points to a new location, and then removes the old contents of temp .

In this link has some images that will help you to better understand this process of deletion .