BST node deletion help!

This is a discussion on BST node deletion help! within the C Programming forums, part of the General Programming Boards category; this is my code snippet: Code: void deletenodebst(bst **rootptr,bst *node) { bst *ptr, *ptr1; if(node->left==NULL || node->right==NULL){ ptr = node; ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    25

    BST node deletion help!

    this is my code snippet:

    Code:
    void deletenodebst(bst **rootptr,bst *node) {
    bst *ptr, *ptr1;
    	
    	if(node->left==NULL || node->right==NULL){
    	ptr = node;
    	}else ptr = successorbst(node);
    	
    	if(ptr != NULL){
    		if(ptr->left!=NULL){
    		ptr1 = ptr->left;
    		}
    		else{
    		ptr1 = ptr->right;
    		}
    	
    		if(ptr->parent==NULL){
    		*rootptr = ptr1;
    		}
    		else{
    			if(ptr == ptr->parent->left){
    			ptr->parent->left = ptr1;
    			}
    			else{
    			ptr->parent->right = ptr1;
    			}
    		}
    	}
    	
    	if(ptr!=node) node->value = ptr->value;
    	free(ptr);
    	
    }
    "bst *node" is the node to be deleted..

    my problem is that when I try to perform this sequence:

    Code:
    insert 6
    insert 20
    insert 3
    insert 2
    insert 10
    insert 100
    insert 4
    delete 20
    delete 6
    insert 16
    insert 8
    delete 8
    delete 3
    delete 16
    delete 8
    delete 4
    delete 2
    delete 10
    delete 100
    a "dumping stack trace" error occurs on the delete 2 part.. help please? thanks..

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You set parent to point at ptr1, but you never set ptr1's parent back upwards (it will point at ptr, still, which is going to go away).

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    25
    sorry for the late reply..

    are you pertaining to this part?

    Code:
    else{
    			if(ptr == ptr->parent->left){
    			ptr->parent->left = ptr1;
                            //should I insert something here...
    			}
    			else{
    			ptr->parent->right = ptr1;
                            //...or here?
    			}
    		}
    can you explain it more? i'm sorry but i'm really having difficulty in getting this...

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    I don't see that it could be any clearer than what tabstop posted already, unless we posted the exact line of code required. You do understand the code you posted right?
    I would not put more code in the places you've guessed as you'd then need to put it in 3 places. One line just inside the end of the large if-block to set the parent of ptr1 is what you need.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    25
    i get it. thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21