Thread: How would you improve this binary tree delete function?

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    158

    How would you improve this binary tree delete function?

    Hi,

    Last year I posted on this forum about a binary tree delete function, but I gave up on what I was doing (it was for university) but now I'm at it again. I tried to understand my last year's code and I came to the conclusion that it was very buggy and it was not deleting the nodes correctly.

    I just finished a new implementation of the delete function (with a simpler data structure just so I don't confuse things-- just an int instead of a couple of strings-- which I believe is working fine. I tested every case I remember and it seemed to fix all the pointers correctly.

    But I'm looking for opinions on how to improve this code. And I know the code can be improved in a number of ways but I'm looking for improvements given some restrictions I want to impose. Maybe some of them don't make much sense to you, but I know why I want do it that way, don't worry about it.

    Here's what I "don't care" to improve on this code:
    • This version is iterative, someone already suggested me to do it recursively but I don't want to. I prefer iterative as I find the code easier to understand, I also avoid stack problems like this.
    • I'm not looking for syntax improvements but more like "remove a piece of a code and replace it by a different one" type of thing, maybe it does the same thing but with less code or maybe with more simplified code.
    • I'm using the inorder successor when deleting a node with 2 children to use as replacement for the node to be deleted. I know this can produce an unbalanced tree but I'm doing one thing at the time. Right now, I'm simply doing a binary tree and not AVL tree.
    • The tree structure is not subject to change. If possible, the function signatures should not be changed too, unless it really simplifies the code (in a way I can understand it lol).


    That's it, here's the relevant code:

    Code:
    typedef int TreeElement;
    
    typedef struct sTree {
       TreeElement item;
       
       struct sTree *left;
       struct sTree *right;
    } Tree;
    
    Tree *extractMin(Tree **tree) {
    	if(!tree) return NULL;
    	
    	Tree *prevPtr = NULL;
    	Tree *currPtr = *tree;
    	
    	while(currPtr->left) {
    		prevPtr = currPtr;
    		currPtr = currPtr->left;
    	}
    	
    	if(prevPtr) prevPtr->left = currPtr->right;
    	else *tree = NULL;
    	
    	// inorder successor
    	return currPtr;
    }
    
    int delete(Tree **tree, TreeElement item) {
    	if(!*tree) return 1;
    	
    	Tree *prevPtr = NULL, *tempPtr = NULL;
    	Tree *currPtr = *tree;
    
    	// loops through the nodes until it finds the one to delete
    	while(currPtr) {
    		// go to the left, right or was the element to delete found?
    		if(item < currPtr->item) {
    			prevPtr = currPtr;
    			currPtr = currPtr->left;
    		} else if(item > currPtr->item) {
    			prevPtr = currPtr;
    			currPtr = currPtr->right;
    		} else {
    			// handles node with no children or with one child
    			if(!currPtr->left || !currPtr->right) {
    				/* get the child to replace the deleted node with
    				   it will be null if there are no children */
    				tempPtr = currPtr->left ? currPtr->left : currPtr->right;
    				
    				// fix the tree root or a different node?
    				if(!prevPtr) {
    					*tree = tempPtr;
    				} else {
    					// fix the left or right pointer in the parent node?
    					if(prevPtr->left == currPtr) prevPtr->left = tempPtr;
    					else prevPtr->right = tempPtr;
    				}
    			}
    			// handles node with two children
    			else if(currPtr->left && currPtr->right) {
    				// extract inorder successor
    				tempPtr = extractMin(&(currPtr->right));
    				
    				// fix the successor left pointer
    				tempPtr->left = currPtr->left;
    				
    				// fix the successor right pointer
    				if(currPtr->right != tempPtr) tempPtr->right = currPtr->right;
    				else tempPtr->right = NULL;
    				
    				// fix the left or right pointer in the parent node?
    				if(prevPtr->left == currPtr) prevPtr->left = tempPtr;
    				else prevPtr->right = tempPtr;
    			}
    			
    			free(currPtr);
    			
    			return 0;
    		}
    	}
    	
    	return 1;
    }
    Last edited by Nazgulled; 02-19-2010 at 05:22 PM.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    So... Is the code fine then? :P

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. 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
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM