binary digital search tree problems. can't free it up correctly

[binaryDigit]

i've been working on this for about a week. i can't seem to write anything that works. so i'm asking for help.
i can't get the functions that delete a node in the tree to work. the problem is either i seg fault or the program hangs because it starts to look for something that doesn't exist anymore.
i need to be able to delete a node on the tree without completely destroying the search path to the rest of the nodes in the tree. as long as the rest of the nodes stay generally in the search path the program will work. i just can't seem to get it done.
i know the code is sloppy and the variable names suck, but i'm just sick of dealing with this.
please help me......... please.


#include <stdio.h>
#include <stdlib.h>

typedef struct _node { struct _node *l, *r; int k; }_node;
typedef struct _search { _node *p, *c; }_search;

int add_node(_node *, int);
void put_node(_node *, _node *, int);
_search find_node(_node *, int);
int del_node(_node *, int);
void kill_node(_node **);

int
add_node(_node *root, int key) {

_node *new;

if(root == NULL) return 0; /* root should already be allocated */

if(find_node(root, key).c != NULL) return 0; /* duplicate item */

/* allocate space and check for failure of malloc */
if((new = (struct _node *) malloc(sizeof(_node))) == NULL) exit(EXIT_FAILURE);

/* set defaults */
new -> l = NULL; new -> r = NULL; new -> k = key;

/* find a place for new space */
put_node(root, new, 1);

/* a bit of an assumption */
return 1;

} /* end of add_node() */

void
put_node(_node *root, _node *new, int level) {

/* first check the path for the new key */
/*
* first block we go to the right. when we find
* a place for the new item we stop
*/
if((new -> k & level) == level) {
if(root -> r == NULL) root -> r = new;
else { level <<= 1; put_node(root -> r, new, level); }
}
/* path is to the left */
else {
if(root -> l == NULL) root -> l = new;
else { level <<= 1; put_node(root -> l, new, level); }
}

} /* end of put_node() */

_search
find_node(_node *root, int key) {

_search locate;
int level = 1;

/* set up initial search pair */
locate.p = NULL;
locate.c = root;

/* nothing to look for */
if(locate.c == NULL) return locate;

while(locate.c != NULL) {
/* found the item. */
if(locate.c -> k == key) break;
/* search right */
else if((key & level) == level) {
locate.p = locate.c;
locate.c = locate.c -> r;
level <<= 1;
}
/* search left */
else {
locate.p = locate.c;
locate.c = locate.c -> l;
level <<= 1;
}
}

return locate;

} /* end of find() */

int
del_node(_node *root, int key) {

_search locate;

locate = find_node(root, key);

/* item wasn't found or nothing to delete */
if(locate.c == NULL) return 0;

/* node to kill is root node */
if(locate.p == NULL) { kill_node(&root); return 1; }
/* node to kill is left child of parent node */
else if(locate.p -> l == locate.c) {
kill_node(&locate.p -> l);
return 1;
}
/* node to kill is right child of parent node */
else {
kill_node(&locate.p -> r);
return 1;
}

} /* end of del_node */

/* ------------------------*
* this is where i'm stuck *
* *
*-------------------------*/
void
kill_node(_node **n) {

_node *tmp;

if((*n) -> l == NULL) {
tmp = *n;
*n = (*n) -> r;
free(tmp);
}
else if((*n) -> r == NULL) {
tmp = *n;
*n = (*n) -> l;
free(tmp);
}
else {
tmp = (*n) -> l;
while((tmp -> l != NULL) || (tmp -> r != NULL)) {
if(tmp -> l != NULL) tmp = tmp -> l;
else if(tmp -> r != NULL) tmp = tmp -> r;
else break;
}
tmp -> r = (*n) -> r;
tmp -> l = (*n) -> l;
tmp = *n;
free(tmp);
}
tmp = NULL;

} /* end of kill_node() */

int
main(void) {

int i = 0, max = 100, size = 0;
_node *root;

root = (struct _node *) malloc(sizeof(_node));

root -> r = NULL; root -> l = NULL; root -> k = -1;
size = 1;

for(i = 0; i < max; i++) {
if(add_node(root, i) == 0) printf("\nfailed add of %d\n", i);
else size++;
}
printf("\nsize = %d after add loop\n", size);
for(i = 0; i < max; i++) {
if(del_node(root, i) == 0) printf("\nfailed delete of %d\n", i);
else size--;
}

printf("\nsize = %d before delete of root\n", size);
free(root);
size--;
printf("\nsize = %d after delete of root\n", size);


return 0;

}

[sans-hubris]

Is this an assignment due a few days from now? Monday perhaps? Or something for work perhaps?

I went through the code with ddd and I don't know what to tell you but after the second node deletion it looks like the tree breaks down. It would go into the third iteration in the second loop, try to search it and segfault. Beyond that, the code is really hard to follow. I would start over.

[ 06 May 2001: Message edited by: ndogg.cpp ]

[ 06 May 2001: Message edited by: ndogg.cpp ]

[binaryDigit]

ok. i re-did the delete function and eliminated the seg faults.
no this isn't for school. i wish it was but i'm learning this on my own.
i cleaned up the code a bit. hopefully enough to be easier to follow.
i apologize for posting such ugly code earlier and code that isn't much better now.
frustration is setting in and i'm about to give up completely.

after changing some of the stuff in the kill_node() function i eliminated the seg faults.
but something wierd is happening. on just a few items the code works fine.
however with more items the code becomes stuck in the while loop. it seems it's searching through
nodes that shouldn't be there any longer.
i'm not going to be able to figure this out....



#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
struct _node *left;
struct _node *right;
int key;
}_node;

typedef struct _search {
_node *parent;
_node *child;
}_search;

int add_node(_node *, int);
void put_node(_node *, _node *, int);
_search find_node(_node *, int);
int del_node(_node *, int);
void kill_node(_node **);

int
add_node(_node *root, int new_key) {

_node *new;

if(root == NULL) return 0; /* root should already be allocated */

/* use find_node() to look for a duplicate item. */
if(find_node(root, new_key).child != NULL) return 0;

/* allocate space and check for failure of malloc */
if((new = (struct _node *) malloc(sizeof(_node))) == NULL) exit(EXIT_FAILURE);

/* set defaults */
new -> left = NULL;
new -> right = NULL;
new -> key = new_key;

/* look through the tree and find the first NULL item in the search path */
put_node(root, new, 1);

/* a bit of an assumption */
return 1;

} /* end of add_node() */

void
put_node(_node *root, _node *new, int level) {

/* first check the path for the new key */
/*
* first block we go to the right. when we find
* a place for the new item we stop
*/
if((new -> key & level) == level) {
if(root -> right == NULL) root -> right = new;
else {
level <<= 1;
put_node(root -> right, new, level);
}
}
/* path is to the left */
else {
if(root -> left == NULL) root -> left = new;
else {
level <<= 1;
put_node(root -> left, new, level);
}
}

} /* end of put_node() */

_search
find_node(_node *root, int search_key) {

_search locate;
int level = 1;

/* set up initial search pair */
locate.parent = NULL;
locate.child = root;

/* nothing to look for */
if(locate.child == NULL) return locate;

while(locate.child != NULL) {
/* found the item. */
if(locate.child -> key == search_key) break;
/* search right */
else if((search_key & level) == level) {
locate.parent = locate.child;
locate.child = locate.child -> right;
level <<= 1;
}
/* search left */
else {
locate.parent = locate.child;
locate.child = locate.child -> left;
level <<= 1;
}
}

/* we return the entire search pair structure. if the .child pointer is NULL
* it means we didn't find it */
return locate;

} /* end of find() */

int
del_node(_node *root, int delete_key) {

_search locate;

/* look for the item to delete */
locate = find_node(root, delete_key);

/* item wasn't found or nothing to delete */
if(locate.child == NULL) return 0;

/* we are going to kill the root node in main this shouldn't have happened */
if(locate.parent == NULL) return 0;

/* node to kill is left child of parent node */
else if(locate.parent -> left == locate.child) {
kill_node(&locate.parent -> left);
return 1;
}
/* node to kill is right child of parent node */
else {
kill_node(&locate.parent -> right);
return 1;
}

} /* end of del_node */

void
kill_node(_node **p_node) {

_node *tmp;

/* this is the function where i'm stuck. */


if((*p_node) -> left == NULL) {
tmp = *p_node;
*p_node = (*p_node) -> right;
free(tmp);
}
else if((*p_node) -> right == NULL) {
tmp = *p_node;
*p_node = (*p_node) -> left;
free(tmp);
}
else {
/* move p_node down the tree until we find a node with NULL left and right
* pointers. then we can set the left and right pointers equal to the left
* and right pointers of the items to be deleted
*/
tmp = *p_node;
*p_node = (*p_node) -> left;
while(((*p_node) -> left != NULL) || ((*p_node) -> right != NULL)) {
if((*p_node) -> left != NULL)
*p_node = (*p_node) -> left;
else if((*p_node) -> right != NULL)
*p_node = (*p_node) -> right;
else break;
}
/* adding the if else statements seems to have stopped the seg faults */
if(tmp -> right != *p_node)
(*p_node) -> right = tmp -> right;
else
(*p_node) -> right = NULL;
if(tmp -> left != *p_node)
(*p_node) -> left = tmp -> left;
else
(*p_node) -> left = NULL;
free(tmp);
}

} /* end of kill_node() */

int
main(void) {

int i = 0, max = 100, size = 0;
_node *root;

/* going to control the root node in main. user will not have access to
* this node */
root = (struct _node *) malloc(sizeof(_node));

root -> right = NULL;
root -> left = NULL;
root -> key = -1;
size = 1;

/* add items */
for(i = 0; i < max; i++) {
if(add_node(root, i) == 0) printf("\nfailed add of %d\n", i);
else size++;
}
printf("\nsize = %d after add loop\n", size);
/* delete items */
for(i = 0; i < max; i++) {
if(del_node(root, i) == 0) printf("\nfailed delete of %d\n", i);
else size--;
}

printf("\nsize = %d before delete of root\n", size);
/* free up root item */
free(root);
size--;
printf("\nsize = %d after delete of root\n", size);


return 0;

}

[binaryDigit]

well i figured it out. may still have a bug, but i'm pretty sure i know why. amazing what stepping away from the computer and riding your skateboard will do for you.
also taking ndogg's advice and starting over helped too.

anyways. don't bother looking at my code. and if you already have i'm sorry.. :)