Below is C program for AVL Tree implementation.
#include<stdio.h> #include<malloc.h> typedef struct bst { int info; int height; struct bst *left; struct bst *right; }NODE; typedef NODE* ROOT; /********************************* for setting/updating the height of the tree at each node *************************************/ int set_height(ROOT r) { int left_h = -1; int right_h = -1; if(r->left) left_h = r->left->height; if(r->right) right_h = r->right->height; if(left_h >= right_h) r->height = left_h+1; else r->height = right_h+1; return r->height; } /********************************* return -1 if data1 is less than data2 return 1 if data1 is greater than data2 returns zero on equal *************************************/ int compare(int data1, int data2) { if(data1<data2) return -1; if(data1>data2) return 1; else return 0; } /******************************* Doing Left-Left rotation *******************************/ void rotate_LL(ROOT *r) { NODE *r1, *r2 = *r,*t1,*t2,*t3; r1 = r2->left; t1 = r1->left; t2 = r1->right; t3 = r2->right; //actual rotation happens here r1->right = r2; r2->left = t2; // update the r1 , r2 height set_height(r1); set_height(r2); *r = r1; } /******************************* Doing Right-Left rotation *******************************/ void rotate_RL(ROOT *r) { NODE *r1,*r2, *r3=*r,*t1,*t2,*t3,*t4; r1 = r3->left; r2 = r1->right; t2 = r2->left; t3 = r2->right; // actaul rotatiosn happens here r1->right = t2; r3->left = t3; r2->left = r1; r2->right = r3; //updte the new heihts for r1, r2, r3 set_height(r1); set_height(r2); set_height(r3); *r = r2; } /******************************* Doing Left-Right rotation *******************************/ void rotate_LR(ROOT *r) { NODE *r1=*r, *r2,*r3,*t1,*t2,*t3,*t4; r3 = r1->right; r2 = r3->left; t2 = r2->left; t3 = r2->right; // actaul rotatiosn happens here r1->right = t2; r3->left = t3; r2->left = r1; r2->right = r3; //updte the new heihts for r1, r2, r3 set_height(r1); set_height(r2); set_height(r3); *r = r2; } /******************************* Doing Right-Right rotation *******************************/ void rotate_RR(ROOT *r) { NODE *r1=*r,*r2,*t1,*t2,*t3; r2 = r1->right; t1 = r1->left; t2 = r2->left; t3 = r2->right; // actaul rotatiosn happens here r1->right = t2; r2->left = r1; set_height(r1); set_height(r2); *r = r2; } /******************************************** It will returns rotation type. 1. Left-Left (LL) 2. Right-Left(RL) 3. Left-Right(RL) 4. Right-Right(RR) ********************************************/ int find_rotation_type(int parent_data, int child_data, int data) { if(compare(data, parent_data)<0) // inserting left { if(compare(data, child_data)<0) return 1; else if(compare(data, child_data)==0) return 0; else return 2; } else //inserting right { if(compare(data, child_data)>0) return 4; else if(compare(data, child_data)==0) return 0; else return 3; } } /******************************************** Calling the corresponding AVL-rotation method ********************************************/ void do_rotation(ROOT *r, int rotation_type) { if(rotation_type == 1) rotate_LL(r); else if(rotation_type == 2) rotate_RL(r); else if(rotation_type == 3) rotate_LR(r); else if(rotation_type == 4) rotate_RR(r); else printf("invalid rotation type \n"); } /************************************************************ Try to insert the elements 50,25,10,5,7,3,30,20,8,15. This order will cover all four rotations ************************************************************/ int insert(ROOT *r, int data) { NODE *new_node, *root = *r; int left_h = -1, right_h = -1; int diff,rotation_type; //tree is empty if(root == NULL) { new_node = (NODE *)malloc(sizeof(NODE)); new_node->info = data; new_node->height = 0; new_node->left = new_node->right = NULL; *r = new_node; return 0; } if(root->left) left_h = root->left->height; if(root->right) right_h = root->right->height; if(compare(data, root->info)<0) { left_h = insert(&(root->left), data); rotation_type = find_rotation_type(root->info, root->left->info, data); } else if(compare(data, root->info)>0) { right_h = insert(&(root->right), data); rotation_type = find_rotation_type(root->info, root->right->info, data); } else { printf("Duplicate key!!\n"); return -1; } diff = left_h-right_h; if(diff>1 || diff<-1) { printf("Tree is Un-Balanced at node data %d ", root->info); if(rotation_type == 1) printf("need to do LL rotation\n"); if(rotation_type == 2) printf("need to do RL rotation\n"); if(rotation_type == 3) printf("need to do LR rotation\n"); if(rotation_type == 4) printf("need to do RR rotation\n"); //this call is for doing rotation do_rotation(r,rotation_type); printf("rotation done successfully\n"); root = *r; } //set the height for the node and return the height return set_height(root); } /************************************** Printing In-Order traversal of AVL Tree **************************************/ void print_inorder(NODE *root) { NODE *temp = root; if(temp) { print_inorder(temp->left); printf("%d ",temp->info); print_inorder(temp->right); } } /************************************** Printing Pre-Order traversal of AVL Tree **************************************/ void print_preorder(NODE *root) { NODE *temp = root; if(temp) { printf("%d ",temp->info); print_preorder(temp->left); print_preorder(temp->right); } } /************************************** Printing Post-Order traversal of AVL Tree **************************************/ void print_postorder(NODE *root) { NODE *temp = root; if(temp) { print_postorder(temp->left); print_postorder(temp->right); printf("%d ",temp->info); } } int main() { ROOT r = NULL; int i,num,data,choice; printf("enter the no. of elements\n"); scanf("%d",&num); printf("Enter the elements\n"); for(i=0;i<num;i++) { scanf("%d",&data); insert(&r,data); } printf("1. Insert\n2. In-order\n3. Pre-order\n4. Post-order\n5. Height of the tree\n other input for exit\n"); printf("Enter the choice\n"); scanf("%d",&choice); while(1) { switch(choice) { case 1: printf("Enter the element\n"); scanf("%d",&data); insert(&r,data); break; case 2: printf("Inorder is \n "); print_inorder(r); printf("\n"); break; case 3: printf("\nPreorder is \n "); print_preorder(r); printf("\n"); break; case 4: printf("\nPostorder is \n "); print_postorder(r); printf("\n"); break; case 5: //height of the root node height is heoght of the tree printf("\nHeight of the tree is %d\n",r->height); break; default: return 0; break; } printf("1. Insert\n2. In-order\n3. Pre-order\n4. Post-order\n5. Height of the tree\n other input for exit\n"); printf("Enter the choice\n"); scanf("%d",&choice); } }
3 comments:
Thank you so much!
Share market with certificate
Best Hire Mobile App Development Company in india.
Post a Comment