AVL Tree Insert

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

typedef struct node
{
    int *key;
    struct node *left;
    struct node *right;
    int height;
}node ,*nodeptr;
 int CompareIntegerDefault(int *data1,int * data2)
{
	
	if(*data1>*data2)
		return (1);
	else if(*data1==*data2)
		return (0);
	else 
		return (-1);
}
// A utility function to get maximum of two integers
int max1(int a, int b);
 
// A utility function to get height of the tree
int height(struct node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// A utility function to get maximum of two integers
int max1(int a, int b)
{
	if(a>b)
		return a;
	else
		return b;
   // return (a > b)? a : b;
}
 
/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct node* newNode(int *key)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

typedef struct ContainerHandle
{
	struct node * root;
	
}ContainerHandle;
 
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max1(height(y->left), height(y->right))+1;
    x->height = max1(height(x->left), height(x->right))+1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max1(height(x->left), height(x->right))+1;
    y->height = max1(height(y->left), height(y->right))+1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
struct node* insert(struct node* node, void *key)
{
    /* 1.  Perform the normal BST rotation */
    int balance;
	if (node == NULL)
        return(newNode(key));
 
    if (CompareIntegerDefault(key , node->key)<0)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);
 
    /* 2. Update height of this ancestor node */
    node->height = max1(height(node->left), height(node->right)) + 1;
 
    /* 3. Get the balance factor of this ancestor node to check whether
       this node became unbalanced */
    balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && CompareIntegerDefault(key , node->left->key)<0)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && CompareIntegerDefault(key , node->right->key)>0)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && CompareIntegerDefault(key , node->left->key)>0)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && CompareIntegerDefault(key , node->right->key)<0)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}

void preOrder(struct node *root)
{
    if(root != NULL)
    {
        printf("%d ",*(int *)(root->key));
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
	ContainerHandle *hdl;
    /* Constructing tree given in the above figure */
	int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;
    hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));
  
	hdl->root=NULL;
	a=9;
	hdl->root=insert(hdl->root, &a);
	b=5;
    hdl->root=insert(hdl->root, &b);
    c=10;
	hdl->root=insert(hdl->root, &c);
    d=0;
	hdl->root=insert(hdl->root, &d);
    e=6;
	hdl->root=insert(hdl->root, &e);
    f=11;
	hdl->root=insert(hdl->root, &f);
    g=-1;
	hdl->root=insert(hdl->root, &g);
    i=1;
	hdl->root=insert(hdl->root, &i);
    j=2;
	hdl->root=insert(hdl->root, &j);
 
    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */
 
    printf("Pre order traversal of the constructed AVL tree is \n");
    preOrder(hdl->root);
	
    return 0;
}
 

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

typedef struct node
{
    int *key;
    struct node *left;
    struct node *right;
    int height;
}node ,*nodeptr;
 int CompareIntegerDefault(int *data1,int * data2)
{
	
	if(*data1>*data2)
		return (1);
	else if(*data1==*data2)
		return (0);
	else 
		return (-1);
}
// A utility function to get maximum of two integers
int max1(int a, int b);
 
// A utility function to get height of the tree
int height(struct node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// A utility function to get maximum of two integers
int max1(int a, int b)
{
	if(a>b)
		return a;
	else
		return b;
   // return (a > b)? a : b;
}
 
/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct node* newNode(int *key)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

typedef struct ContainerHandle
{
	struct node * root;
	
}ContainerHandle;
 
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max1(height(y->left), height(y->right))+1;
    x->height = max1(height(x->left), height(x->right))+1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max1(height(x->left), height(x->right))+1;
    y->height = max1(height(y->left), height(y->right))+1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
struct node* insert(struct node* node, void *key)
{
    /* 1.  Perform the normal BST rotation */
    int balance;
	if (node == NULL)
        return(newNode(key));
 
    if (CompareIntegerDefault(key , node->key)<0)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);
 
    /* 2. Update height of this ancestor node */
    node->height = max1(height(node->left), height(node->right)) + 1;
 
    /* 3. Get the balance factor of this ancestor node to check whether
       this node became unbalanced */
    balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && CompareIntegerDefault(key , node->left->key)<0)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && CompareIntegerDefault(key , node->right->key)>0)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && CompareIntegerDefault(key , node->left->key)>0)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && CompareIntegerDefault(key , node->right->key)<0)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}

void preOrder(struct node *root)
{
    if(root != NULL)
    {
        printf("%d ",*(int *)(root->key));
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
	ContainerHandle *hdl;
    /* Constructing tree given in the above figure */
	int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;
    hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));
  
	hdl->root=NULL;
	a=9;
	hdl->root=insert(hdl->root, &a);
	b=5;
    hdl->root=insert(hdl->root, &b);
    c=10;
	hdl->root=insert(hdl->root, &c);
    d=0;
	hdl->root=insert(hdl->root, &d);
    e=6;
	hdl->root=insert(hdl->root, &e);
    f=11;
	hdl->root=insert(hdl->root, &f);
    g=-1;
	hdl->root=insert(hdl->root, &g);
    i=1;
	hdl->root=insert(hdl->root, &i);
    j=2;
	hdl->root=insert(hdl->root, &j);
 
    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */
 
    printf("Pre order traversal of the constructed AVL tree is \n");
    preOrder(hdl->root);
	
    return 0;
}