Scribd
Upload
95 views

AVL Tree Program in C

The document contains a C program to insert nodes into an AVL tree. It defines struct nodes with left, right, and height pointers. Functions include getting a node, rotating the tree left or right, calculating balance factors, finding height, and inserting a node. The main function allows the user to insert nodes or view the inorder traversal and exits the program.

Uploaded by

danieldanny7116
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
95 views

AVL Tree Program in C

The document contains a C program to insert nodes into an AVL tree. It defines struct nodes with left, right, and height pointers. Functions include getting a node, rotating the tree left or right, calculating balance factors, finding height, and inserting a node. The main function allows the user to insert nodes or view the inorder traversal and exits the program.

Uploaded by

danieldanny7116
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Module 4:

Lab program
Write a C program to insert node AVL tree

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

struct node
{
int data;
struct node* left;
struct node* right;
int ht;
};

struct node* root = NULL;

struct node* getnode(int data)


{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("\nMemory can't be allocated\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

struct node* rotate_left(struct node* root)


{
struct node* ptr = root->right;
root->right = ptr->left;
ptr->left = root;

// update the heights of the nodes


root->ht = height(root);
ptr->ht = height(ptr);
return ptr;
}

// rotates to the right


struct node* rotate_right(struct node* root)
{
struct node* ptr = root->left;
root->left = ptr->right;
ptr->right = root;

// update the heights of the nodes


root->ht = height(root);
ptr->ht = height(ptr);

1
// return the new node after rotation
return ptr;
}

int balance_factor(struct node* root)


{
int lh, rh;
if (root == NULL)
return 0;
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
return lh - rh;
}

int height(struct node* root)


{
int lh, rh;
if (root == NULL)
{
return 0;
}
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;

if (lh > rh)


return (lh);
return (rh);
}

struct node* insert(struct node* root, int data)


{
if (root == NULL)
{
struct node* new_node = getnode(data);
if (new_node == NULL)
{
return NULL;
}
root = new_node;
}
else if (data > root->data)
{
2
root->right = insert(root->right, data);

// tree is unbalanced, then rotate it


if (balance_factor(root) == -2)
{
if (data > root->right->data)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
root->left = insert(root->left, data);

// tree is unbalanced, then rotate it


if (balance_factor(root) == 2)
{
if (data < root->left->data)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
// update the heights of the nodes
root->ht = height(root);
return root;
}

void inorder(struct node* root)


{
if (root == NULL)
{
return;
}

inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

int main()
{
int user_choice, data;
3
char user_continue;
while (1)
{
printf("\n\n------- AVL TREE --------\n");
printf("\n1. Insert");
printf("\n2. Inorder");
printf("\n3. EXIT");
printf("\n\nEnter Your Choice: ");
scanf("%d", &user_choice);

switch (user_choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
inorder(root);
break;
case 3:
printf("\n\tProgram Terminated\n");
return 0;
default:
printf("\n\tInvalid Choice\n");
}
}

return 0;
}

------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 42
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 6
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


4
Enter data: 54
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 62
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 88
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 50
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 22
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 32
------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice:


1
Enter data: 12
------- AVL TREE --------

1. Insert
5
2. Inorder
3. EXIT

Enter Your Choice: 1


Enter data: 33------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice: 2


6 12 22 32 33 42 50 54 62 88

------- AVL TREE --------

1. Insert
2. Inorder
3. EXIT

Enter Your Choice:

You might also like