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