AVL Tree Implementation
AIM:
To perform various operations i.e. ,insertions and deletions on AVL trees
Description:
In this program, AVL Tree is implemented with various operations.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* createNode(int data)
{
struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = NULL;
temp->right= NULL;
temp->height = 1;
return temp;
}
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insertNode(struct Node* node, int data)
{
if (node == NULL)
return(createNode(data));
if (data< node->data)
node->left = insertNode(node->left,data);
else if (data > node->data)
node->right = insertNode(node->right,data);
else
return node;
node->height = 1 + max(height(node->left),height(node->right));
int balance = getBalance(node);
if (balance > 1 && data < node->left->data)
return rightRotate(node);
if (balance < -1 && data > node->right->data)
return leftRotate(node);
if (balance > 1 && data > node->left->data)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
struct Node* minValueNode(struct Node* node)
{
struct Node* cur=node;
while(cur->left!=NULL)
cur=cur->left;
return cur;
}
struct Node* deleteNode(struct Node* node, int key)
{
if (node == NULL)
return node;
if (key<node->data)
node->left = deleteNode(node->left, key);
else if (key>node->data)
node->right = deleteNode(node->right, key);
else if(key==node->data)
{
if (node->left==NULL)
{
struct Node* temp=node->right;
free(node);
return temp;
}
else if (node->right==NULL)
{
struct Node* temp=node->left;
free(node);
return temp;
}
struct Node* temp = minValueNode(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
}
else
{
printf("\n Node Not Found!!!!\n");
}
if (node==NULL)
return node;
node->height = 1 + max(height(node->left),height(node->right));
int balance = getBalance(node);
if (balance > 1 && getBalance(node->left) >= 0)
return rightRotate(node);
if (balance > 1 && getBalance(node->left) < 0)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && getBalance(node->right) <= 0)
return leftRotate(node);
if (balance < -1 && getBalance(node->right) > 0)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
int HeightAVL(struct Node* node)
{
if (node == NULL)
return 0;
else
{
int lDepth = HeightAVL(node->left);
int rDepth = HeightAVL(node->right);
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf(" %d", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(struct Node* root)
{
if(root != NULL)
{
inOrder(root->left);
printf(" %d", root->data);
inOrder(root->right);
}
}
void postOrder(struct Node* root)
{
if(root != NULL)
{
postOrder(root->left);
postOrder(root->right);
printf(" %d", root->data);
}
}
int main()
{
struct Node *root=NULL;
int i,info,N,cho;
printf("\n Select Operation : ");
printf("\n 1. Insertion");
printf("\t 2. Deletion");
printf("\t 3. Height of AVL Tree");
printf("\n 4. Pre-Order Traversal");
printf("\t 5. In-Oder Traversal");
printf("\t 6. Post-Order Traversal");
printf("\t 7. Exit");
do
{
printf("\n Enter Your Choice : ");
scanf("%d",&cho);
switch(cho)
{
case 1:
printf("\n Enter Element : ");
scanf("%d",&info);
root=insertNode(root,info);
printf("\n Element %d Inserted!!!\n",info);
break;
case 2:
printf("\n Enter Element : ");
scanf("%d",&info);
root=deleteNode(root,info);
printf("\n Element %d Deleted!!!\n",info);
break;
case 3:
printf("\n Height of AVL Tree = %d\n",HeightAVL(root));
break;
case 4:
printf("\n Pre-Order Traversal : \n");
preOrder(root);
printf("\n");
break;
case 5:
printf("\n In-Order Traversal : \n");
inOrder(root);
printf("\n");
break;
case 6:
printf("\n Post-Order Traversal : \n");
postOrder(root);
printf("\n");
break;
case 7:
printf("\n Done!!!\n");
break;
default:
printf("\n Invalid Choice!!!\n");
}
}while(cho!=7);
return 0;
}
OUTPUT
Select Operation :
1. Insertion 2. Deletion 3. Height of AVL Tree
4. Pre-Order Traversal 5. In-Oder Traversal 6. Post-Order Traversal 7. Exit
Enter Your Choice : 1
Enter Element : 50
Element 50 Inserted!!!
Enter Your Choice : 1
Enter Element : 30
Element 30 Inserted!!!
Enter Your Choice : 1
Enter Element : 20
Element 20 Inserted!!!
Enter Your Choice : 1
Enter Element : 40
Element 40 Inserted!!!
Enter Your Choice : 1
Enter Element : 70
Element 70 Inserted!!!
Enter Your Choice : 1
Enter Element : 60
Element 60 Inserted!!!
Enter Your Choice : 1
Enter Element : 80
Element 80 Inserted!!!
Enter Your Choice : 5
In-Order Traversal :
20 30 40 50 60 70 80
Enter Your Choice : 3
Height of AVL Tree = 3
Enter Your Choice : 2
Enter Element : 20
Element 20 Deleted!!!
Enter Your Choice : 4
Pre-Order Traversal :
50 30 40 70 60 80
Enter Your Choice : 2
Enter Element : 30
Element 30 Deleted!!!
Enter Your Choice : 6
Post-Order Traversal :
40 60 80 70 50
Enter Your Choice : 2
Enter Element : 50
Element 50 Deleted!!!
Enter Your Choice : 5
In-Order Traversal :
40 60 70 80
Enter Your Choice : 3
Height of AVL Tree = 3
Enter Your Choice : 7
Done!!!
--------------------------------
Process exited after 2.236 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment