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