WAP to Implement All Operation of AVL Tree

Algorithm


1. Input A tree rooted at root.
2. Output Tree after insertion of node.
3. Complexity O(logn)
4.
5. AVL Insertion
6. AVL insert (root)
7. if item 8. AVL insert(left[root])
9. else AVL insert(right[root])
10. if (root = null)
11. Temp[info]=item;
12. Temp =root;
13. if (left[root]=null and right[root]=null) then
14. Root [info]=item;
15. if (item 16. Left [root] =temp;
17. if (item >info [root] ) then
18. Right [root]=temp;
19. AVL rotation (x, p[x] , p[p[x]] );
20.
21. AVL deletion
22. Input A tree rooted at root.
23. Output Tree after deletion of node.
24. Complexity O(logn).
25.
26. AVL delete (item, p)
27. If (item=info[root]) then
28. if (right[root] != null) then
29. q=successor(root);
30. info[root]=q;
31. AVL delete(q);
32. else if(left[root] !=null) then
33. q=predecessor(root)
34. info[root]=q;
35. AVL delete(q);
36. else AVL delete(p);
37. else
38. if (item 39. AVL delete(left[p]);
40. else
41. AVL delete(right[p]);
42. AVL rotate(p, pr[p] , sib[p]);

Input A tree rooted at root.
Output Tree after insertion of node.
Complexity O(logn)

AVL Insertion
AVL insert (root)
if item AVL insert(left[root])
else AVL insert(right[root])
if (root = null)
Temp[info]=item;
Temp =root;
if (left[root]=null and right[root]=null) then
Root [info]=item;
if (item Left [root] =temp;
if (item >info [root] ) then
Right [root]=temp;
AVL rotation (x, p[x] , p[p[x]] );

AVL deletion
Input A tree rooted at root.
Output Tree after deletion of node.
Complexity O(logn).

AVL delete (item, p)
If (item=info[root]) then
if (right[root] != null) then
q=successor(root);
info[root]=q;
AVL delete(q);
else if(left[root] !=null) then
q=predecessor(root)
info[root]=q;
AVL delete(q);
else AVL delete(p);
else
if (item AVL delete(left[p]);
else
AVL delete(right[p]);
AVL rotate(p, pr[p] , sib[p]);


Algorithm Description

Notations:
Info [root] : Item stored at root node.
Left[root]: left child of root;
Right[root]: right child of root;
P[x]=parent of node x;



#include
#include
#include


typedef struct node1
{
int data;
int bf;
struct node1 *left;
struct node1 *right;
} node;


void insert_node(node **, int);
void delete_node(node **, int);
int find_height(node *);
void delete_tree(node **);
node *findmax(node *);
void traverse_inorder(node *);


int main()
{
int choice; /* variable to store choice of user */
int element; /* variable to store data of node entered bu user */
node *root = NULL; /* intialising root node */
while (1)
{
printf("\n\t MENU\n");
printf("\t--------\n");
printf(" 1. Insert node\n");
printf(" 2. Delete node\n");
printf(" 3. Height of Tree\n");
printf(" 4. Traverse inorder\n");
printf(" 5. Exit\n\n");
printf("Enter your choice (1-5) ::");
scanf("%d", &choice);
switch (choice)
{
case 1: printf("\n Enter the element to be inserted::");
scanf("%d", &element);
insert_node(&root, element);
break;
case 2: printf("\n Enter the element to be deleted ::");
scanf("%d", &element);
delete_node(&root, element);
break;
case 3: printf("Height of AVL Tree = %d", find_height(root));
break;
case 4: printf("\n\n In-Order Traversal is\n");
traverse_inorder(root);
break;
case 5: delete_tree(&root);
return;
}
}
}

void insert_node(node ** root, int element)
{
node *ptr1;
node *ptr2;
/* checking if there is no elemnt in th tree */
if(NULL == *root)
{
*root = (node *) malloc (sizeof(node)); /* allocating memory */
(*root)->data = element;
(*root)->left = NULL;
(*root)->right = NULL;
(*root)->bf = 0; /* allocating balance factor to root */
}
/* element is less than root than */
else if(element < (*root)->data)
{
insert_node(&((*root)->left), element);
switch((*root)->bf)
{
case 1: ptr1 = (*root)->left;
if(1 == ptr1->bf)
{
/* right rotation */
(*root)->left = ptr1->right;
ptr1->right = *root;
(*root)->bf = 0;
*root = ptr1;
}
else
{
ptr2 = ptr1->right;
ptr1->right = ptr2->left;
ptr2->left = ptr1;
(*root)->left = ptr2->right;
ptr2->right = *root;
(*root)->bf = ptr2->bf == 1 ? -1 : 0;
ptr1->bf = ptr2->bf == -1 ? 1 : 0;
*root = ptr2;
}
break;
case 0: (*root)->bf = 1;
break;
case -1: (*root)->bf = 0;
break;
}
}
else
{
insert_node(&(*root)->right, element);
switch((*root)->bf)
{
case 1: (*root)->bf = 0;
break;
case 0: (*root)->bf = -1;
break;
case -1: ptr1 = (*root)->right;
if(ptr1->bf == -1)
{
/* left rotation */
(*root)->right = ptr1->left;
ptr1->left = *root;
(*root)->bf = 0;
*root = ptr1;
}
else
{
/* double rotation ,right left */
ptr2 = ptr1->left;
ptr1->left = ptr2->right;
ptr2->right = ptr1;
(*root)->right = ptr2->left;
ptr2->left = (*root);
(*root)->bf = ptr2->bf == -1 ? 1 : 0;
ptr1->bf = ptr2->bf == 1 ? -1 : 0;
*root = ptr2;
}
}
}
}

int find_height (node *tree)
{
int height_of_left_subtree;
int height_of_right_subtree;
int height;
if (NULL == tree)
{
height = 0;
}
else
{
height_of_left_subtree = find_height(tree->left);
height_of_right_subtree = find_height(tree->right);
if(height_of_left_subtree > height_of_right_subtree)
height = height_of_left_subtree + 1;
else
height = height_of_right_subtree + 1;
}
return height;
}

void delete_node (node **h, int element)
{
node *temp; /* variable to store node which has to be freed */
node *ptr1;
node *ptr2;
if (NULL == *h)
{
printf("Element %d not found in the AVL tree\n", element);
printf("press any key to continue....");
getch();
}
else if(element < (*h)->data)
{
delete_node(&(*h)->left, element);
switch((*h)->bf)
{
case 1: (*h)->bf = 0;
break;
case 0: (*h)->bf = -1;
break;
case -1: ptr1 = (*h)->right;
if(ptr1->bf == -1)
{
/* left rotation */
(*h)->right = ptr1->left;
ptr1->left = *h;
(*h)->bf = 0;
*h = ptr1;
}
else
{
ptr2 = ptr1->left;
ptr1->left = ptr2->right;
ptr2->right = ptr1;
(*h)->right = ptr2->left;
ptr2->left = *h;
(*h)->bf = ptr2->bf == -1 ? 1 : 0;
ptr1->bf = ptr2->bf == 1 ? -1 : 0;
*h = ptr2;
}
}
}
else if (element > (*h)->data)
{
delete_node (&(*h)->right, element);
switch ((*h)->bf)
{
case 1: ptr1 = (*h)->left;
if(ptr1->bf == 1)
{
/* right rotation */
(*h)->left = ptr1->right;
ptr1->right = *h;
(*h)->bf = 0;
*h = ptr1;
}
else
{
/* double rotation , left-right */
ptr2 = ptr1->right;
ptr1->right = ptr2->left;
ptr2->left = ptr1;
(*h)->left = ptr2->right;
(*h)->bf = ptr2->bf == 1 ? -1 : 0;
ptr1->bf = ptr2->bf == -1 ? 1 : 0;
*h = ptr2;
}
break;
case 0: (*h)->bf = 1;
break;
case -1: (*h)->bf = 0;
break;
}
}
/* when element found and it has both the child than find predecessor */
else if( (*h)->left && (*h)->right)
{
temp = findmax((*h)->left); /* find predecessor */
(*h)->data = temp->data; /* replace node with predecessor */
delete_node(&(*h)->left, temp->data); /* delete predecessor */
}
else
{
temp = *h;
if(((*h)->left == NULL) && ((*h)->right == NULL)) /* terminal node */
*h = NULL;
else if ((*h)->right == NULL) /* left child only */
*h = (*h)->left;
else
*h = (*h)->right; /* right child only */
free(temp);
}
}

node * findmax(node *root)
{
if((NULL == root) || (NULL == root->right))
{
return root;
}
else
return findmax(root->right);
}

void traverse_inorder(node *root)
{
if(NULL != root)
{
traverse_inorder(root->left);
printf("%d, ", root->data);
traverse_inorder(root->right);
}
}
void delete_tree(node **root)
{
if (NULL != *root)
{
delete_tree(&((*root)->left));
delete_tree(&((*root)->right));
free(root);
}
}

Source AlgoGuru