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