Thread: Help Debugging my AVL tree program.

  1. #1
    Registered User
    Join Date
    Aug 2008
    Posts
    55

    Help Debugging my AVL tree program.

    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*/

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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

    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program Plan
    By Programmer_P in forum C++ Programming
    Replies: 0
    Last Post: 05-11-2009, 01:42 AM
  2. help debugging my program
    By kenyi in forum C Programming
    Replies: 2
    Last Post: 08-04-2007, 11:26 PM
  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. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  5. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM