1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0

#### AVL Tree Insert

Hey,
I have this code for AVL tree insert that works fine!

Code:
```#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;
}```
But, I dont want the insert function to return structure pointer as I'm planning to make it return error codes. So here's what I did.

Code:
```#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;
}```
But it gives me a warning that
warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.

and it doesnt give output also