Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
December 7th, 2012, 12:46 AM
 sakura66
Registered User

Join Date: Nov 2012
Posts: 2
Time spent in forums: 4 m 50 sec
Reputation 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

#2
December 7th, 2012, 02:04 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 3,840
Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 21 m 53 sec
Reputation Power: 1774
Yet another selfish cross-poster

Particularly sections on choosing forums, and claiming urgency.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

 Viewing: Dev Shed Forums > Programming Languages > C Programming > AVL Tree Insert