Help Debugging my AVL tree program.

Nextstopearth · 04-03-2009, 11:24 PM

I almost feel bad posting such a horrible looking and long piece of code, but IF anybody feels like flexing their programming muscles a little and helping me out, I would really appreciate it. This is an assignment for a college course which is already late and not worth very many points, but I'd like to get it completely working anyway.

I posted an early version of part of this before because I was getting a segmentation fault, which I was able to fix thanks to the help of some members of the forum, so thanks to the people who helped in that thread.

I believe the second use of the insert function produces the seg fault, so the problem must be in that function, or in the getheight() or one of the rotate functions. I realize there are some trivial things wrong with my program that don't really cause a problem(some functions not used(I didn't include those definitions in this post) or no return values), and I'm not worried about those.

So I appreciate any response, even if it's just to say that it's to much of a mess and to start or over something.

Code:

#include <stdio.h>

	typedef struct node{
		struct node * left;
		struct node * right;
		int value;
	} NODE;

	typedef struct tree{
		NODE * root;
	} TREE;

/*Function declarations*/
	void insert(NODE * node, NODE * root);
	int getheight(NODE * node);
	NODE * find(int value, NODE * treeroot);
	NODE * findmin(NODE * root);
	NODE * findmax(NODE * root);
	void removenode(NODE * node, NODE * root);
	void traverse(NODE * treeroot);
	NODE * singleRotateWithRightChild(NODE * node);
	NODE * singleRotateWithLeftChild(NODE * node);
	NODE * doubleRotateWithRightChild(NODE * node);
	NODE * doubleRotateWithLeftChild(NODE * node);


int main(void){
	/*Create Avl Tree*/
	TREE tree;
	/*create nodes*/
	NODE rt = {NULL, NULL, 3};
	NODE nd1 = {NULL, NULL, 2};
	NODE nd2 = {NULL, NULL, 1};
	NODE nd3 = {NULL, NULL, 4};
	NODE nd4 = {NULL, NULL, 5};
	NODE nd5 = {NULL, NULL, 6};
	NODE nd6 = {NULL, NULL, 7};
	NODE nd7 = {NULL, NULL, 16};
	NODE nd8 = {NULL, NULL, 15};
	NODE nd9 = {NULL, NULL, 14};
	NODE nd10 = {NULL, NULL, 13};
	NODE nd11 = {NULL, NULL, 12};
	NODE nd12 = {NULL, NULL, 11};
	NODE nd13 = {NULL, NULL, 10};
	NODE nd14 = {NULL, NULL, 8};
	NODE nd15 = {NULL, NULL, 9};

	/*Mark the initial root of the AVL tree*/
	tree.root = &rt;
	tree.root->value = 3;
	/*put nodes in tree*/
	insert(&nd1, tree.root);
	insert(&nd2, tree.root);
	insert(&nd3, tree.root);
	insert(&nd4, tree.root);
	insert(&nd5, tree.root);
	insert(&nd6, tree.root);
	insert(&nd7, tree.root);
	insert(&nd8, tree.root);
	insert(&nd9, tree.root);
	insert(&nd10, tree.root);
	insert(&nd11, tree.root);
	insert(&nd12, tree.root);
	insert(&nd13, tree.root);
	insert(&nd14, tree.root);
	insert(&nd15, tree.root);

	/*print out tree values in-order*/
	traverse(tree.root);
	
	removenode(find(9, tree.root), tree.root);
	removenode(find(6, tree.root), tree.root);
	removenode(find(1, tree.root), tree.root);
	removenode(find(3, tree.root), tree.root);
	/*print out tree values in-order*/
	traverse(tree.root);
	return 0;
}


/**********INSERT************/
void insert(NODE * node, NODE * root){
	if ( node->value > root->value && root->right == NULL)
	{
		root->right = node;
	}
	else if( node->value > root->value && root->right != NULL)
	{
		insert(node, root->right);
		if(getheight(root->right) - getheight(root->left) == 2){
			if(node->value > root->right->value){
				singleRotateWithRightChild(root);
			}
			else
				doubleRotateWithRightChild(root);
		}
	}else if ( node->value < root->value && root->left == NULL ){
		root->left = node;	
	}else if ( node->value < root->value && root->left != NULL ){
		insert(node, root->left);
		if (getheight(root->left) - getheight(root->right) == 2){
		if (node->value < root->left->value)
			singleRotateWithLeftChild(root);
		else
			doubleRotateWithLeftChild(root);
		}
	}
}


/**********GETHEIGHT************/
int getheight(NODE * node){
	if ( node->left == NULL && node->right == NULL){
		return 0;
}
	if (node->left == NULL && node->right != NULL){
		return (getheight(node->right) + 1);
}
	if (node->right == NULL && node->left != NULL){
		return (getheight(node->left) + 1);
}
	if (getheight(node->left) > getheight(node->right)){
		return getheight(node->left) + 1;
}
	if (getheight(node->right) < getheight(node->left)){
		return getheight(node->right) + 1;
}
return 123;
}


/*********REMOVE************/
void removenode(NODE * node, NODE * root){
	if (node->value == root->right->value && root->right->right == NULL && root->right->left == NULL){
root->right = NULL;
return;
} 
	if (node->value == root->left->value && root->left->left == NULL && root->left->right == NULL){
root->left = NULL;
return;
}
	if (node->value == root->right->value){
		/*REMOVENODE RIGHT*/

		NODE * ptr = root->right->right;
		NODE * ptr2 = root->right->left;
		findmax(root->right->left)->right = ptr;//segfault here?
		root->right = ptr2;
	}
	else if(node->value == root->left->value){
		/*REMOVENODE LEFT*/
		
		NODE * ptr = root->left->right;
		NODE * ptr2 = root->left->left;
		findmin(root->left->right)->left = ptr2;
		root->left = ptr;
	}
	else if (node->value > root->value )
	{
		removenode( node, root->right );
	}
	else if (node->value < root->value)
	{
		removenode( node, root->left);
	}
}


/*********TRAVERSE*********/
void traverse(NODE * treeroot){

	if (treeroot->left != NULL){
		traverse(treeroot->left);
	}
	
	printf("%d ", treeroot->value);

	if (treeroot->right != NULL){
		traverse(treeroot->right);
	}

}


/**********SINGLEROTATERIGHT**********/
NODE * singleRotateWithRightChild(NODE * node){
if (node->right == NULL){return node;}
NODE * n2 = node->right; 
if (node->right->left != NULL)
{
	node->right = node->right->left;
	node->right->left = node;
	node = n2;
}
else if (node->right->left == NULL){
printf("Error\n");
}

return node;
}


/***********SINGLEROTATELEFT********/
NODE * singleRotateWithLeftChild(NODE * node){
if ( node->left == NULL) {return node;}
NODE * n1 = node->left;
if (node->left->right != NULL){
	node->left = n1;
	node->left->right = node;
	node = n1;
}
else if (node->left->right == NULL) {
printf("Error\n");
}
}


/*********DOUBLEROTATERIGHT***********/
NODE * doubleRotateWithRightChild(NODE * node){
NODE * ptr = node->right;
singleRotateWithLeftChild(ptr);
singleRotateWithRightChild(node);
}


/**********DOUBLEROTATELEFT***********/
NODE * doubleRotateWithLeftChild(NODE * node){
NODE * ptr = node->left;
singleRotateWithRightChild(ptr);
singleRotateWithLeftChild(node);
}
/*end of program*/

vart · 04-03-2009, 11:50 PM

if (getheight(root->left) - getheight(root->right)

root->right will be null after inserting only one node to left, so you can pass null pointer to the getheight. Which will crash on it.

Also check - what will happen if new value matches one of the present values in the tree

iMalc · 04-04-2009, 01:48 AM

This is where I'd start:
Make every function that takes a pointer work when the passed-in pointer is NULL. This simple change and possible mindshift will actually make your code a LOT clearer and shorter.
Your traverse function then becomes:

Code:

void traverse(NODE * treeroot) {
	if (treeroot != NULL) {
		traverse(treeroot->left);
		printf("%d ", treeroot->value);
		traverse(treeroot->right);
	}

}

Note that this simple example barely does this idea justice, in showing how much better it becomes.
Try it with your getheight function and you should get it down to only 3 lines in the function body! It currently has six NULL checks, but this change will bring it down to just one.
Once you've done that to all of your code, it should be so much shorter and easier to understand and manage that you may even be able to spot the error on your own.

Note that the return 123; might seem like you're just shutting up the compiler (in a humourous way), but have you considered that it can actually reach that line of code?!

04-03-2009, 11:50 PM	#2
vart CSharpener Join Date: Oct 2006 Posts: 5,242	if (getheight(root->left) - getheight(root->right) root->right will be null after inserting only one node to left, so you can pass null pointer to the getheight. Which will crash on it. Also check - what will happen if new value matches one of the present values in the tree __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is offline

04-04-2009, 01:48 AM	#3
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,476	This is where I'd start: Make every function that takes a pointer work when the passed-in pointer is NULL. This simple change and possible mindshift will actually make your code a LOT clearer and shorter. Your traverse function then becomes: Code: void traverse(NODE * treeroot) { if (treeroot != NULL) { traverse(treeroot->left); printf("%d ", treeroot->value); traverse(treeroot->right); } } Note that this simple example barely does this idea justice, in showing how much better it becomes. Try it with your getheight function and you should get it down to only 3 lines in the function body! It currently has six NULL checks, but this change will bring it down to just one. Once you've done that to all of your code, it should be so much shorter and easier to understand and manage that you may even be able to spot the error on your own. Note that the return 123; might seem like you're just shutting up the compiler (in a humourous way), but have you considered that it can actually reach that line of code?! __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Program Plan	Programmer_P	C++ Programming	0	05-11-2009 01:42 AM
help debugging my program	kenyi	C Programming	2	08-04-2007 11:26 PM
Binary Search Trees Part III	Prelude	A Brief History of Cprogramming.com	16	10-02-2004 03:00 PM
AVL tree balancing problem	sweets	C++ Programming	4	05-06-2004 12:17 PM
binary tree node structure	Kirsten	C Programming	2	04-26-2002 08:02 PM