Program to maintain an AVL tree.

i want to insert this functions inside the programCode:#include <stdio.h> #include <conio.h> #include <alloc.h> #define FALSE 0 #define TRUE 1 struct AVLNode { int data ; int balfact ; struct AVLNode *left ; struct AVLNode *right ; } ; struct AVLNode * buildtree ( struct AVLNode *, int, int * ) ; struct AVLNode * deldata ( struct AVLNode *, int, int * ) ; struct AVLNode * del ( struct AVLNode *, struct AVLNode *, int * ) ; struct AVLNode * balright ( struct AVLNode *, int * ) ; struct AVLNode * balleft ( struct AVLNode *, int * ) ; void display ( struct AVLNode * ) ; void deltree ( struct AVLNode * ) ; void main( ) { struct AVLNode *avl = NULL ; int h ; clrscr( ) ; avl = buildtree ( avl, 20, &h ) ; avl = buildtree ( avl, 6, &h ) ; avl = buildtree ( avl, 29, &h ) ; avl = buildtree ( avl, 5, &h ) ; avl = buildtree ( avl, 12, &h ) ; avl = buildtree ( avl, 25, &h ) ; avl = buildtree ( avl, 32, &h ) ; avl = buildtree ( avl, 10, &h ) ; avl = buildtree ( avl, 15, &h ) ; avl = buildtree ( avl, 27, &h ) ; avl = buildtree ( avl, 13, &h ) ; printf ( "\nAVL tree:\n" ) ; display ( avl ) ; avl = deldata ( avl, 20, &h ) ; avl = deldata ( avl, 12, &h ) ; printf ( "\nAVL tree after deletion of a node:\n" ) ; display ( avl ) ; deltree ( avl ) ; getch( ) ; } /* inserts an element into tree */ struct AVLNode * buildtree ( struct AVLNode *root, int data, int *h ) { struct AVLNode *node1, *node2 ; if ( !root ) { root = ( struct AVLNode * ) malloc ( sizeof ( struct AVLNode ) ) ; root -> data = data ; root -> left = NULL ; root -> right = NULL ; root -> balfact = 0 ; *h = TRUE ; return ( root ) ; } if ( data < root -> data ) { root -> left = buildtree ( root -> left, data, h ) ; /* If left subtree is higher */ if ( *h ) { switch ( root -> balfact ) { case 1: node1 = root -> left ; if ( node1 -> balfact == 1 ) { printf ( "\nRight rotation along %d.", root -> data ) ; root -> left = node1 -> right ; node1 -> right = root ; root -> balfact = 0 ; root = node1 ; } else { printf ( "\nDouble rotation, left along %d", node1 -> data ) ; node2 = node1 -> right ; node1 -> right = node2 -> left ; printf ( " then right along %d.\n", root -> data ) ; node2 -> left = node1 ; root -> left = node2 -> right ; node2 -> right = root ; if ( node2 -> balfact == 1 ) root -> balfact = -1 ; else root -> balfact = 0 ; if ( node2 -> balfact == -1 ) node1 -> balfact = 1 ; else node1 -> balfact = 0 ; root = node2 ; } root -> balfact = 0 ; *h = FALSE ; break ; case 0: root -> balfact = 1 ; break ; case -1: root -> balfact = 0 ; *h = FALSE ; } } } if ( data > root -> data ) { root -> right = buildtree ( root -> right, data, h ) ; /* If the right subtree is higher */ if ( *h ) { switch ( root -> balfact ) { case 1: root -> balfact = 0 ; *h = FALSE ; break ; case 0: root -> balfact = -1 ; break; case -1: node1 = root -> right ; if ( node1 -> balfact == -1 ) { printf ( "\nLeft rotation along %d.", root -> data ) ; root -> right = node1 -> left ; node1 -> left = root ; root -> balfact = 0 ; root = node1 ; } else { printf ( "\nDouble rotation, right along %d", node1 -> data ) ; node2 = node1 -> left ; node1 -> left = node2 -> right ; node2 -> right = node1 ; printf ( " then left along %d.\n", root -> data ) ; root -> right = node2 -> left ; node2 -> left = root ; if ( node2 -> balfact == -1 ) root -> balfact = 1 ; else root -> balfact = 0 ; if ( node2 -> balfact == 1 ) node1 -> balfact = -1 ; else node1 -> balfact = 0 ; root = node2 ; } root -> balfact = 0 ; *h = FALSE ; } } } return ( root ) ; } /* deletes an item from the tree */ struct AVLNode * deldata ( struct AVLNode *root, int data, int *h ) { struct AVLNode *node ; if ( !root ) { printf ( "\nNo such data." ) ; return ( root ) ; } else { if ( data < root -> data ) { root -> left = deldata ( root -> left, data, h ) ; if ( *h ) root = balright ( root, h ) ; } else { if ( data > root -> data ) { root -> right = deldata ( root -> right, data, h ) ; if ( *h ) root = balleft ( root, h ) ; } else { node = root ; if ( node -> right == NULL ) { root = node -> left ; *h = TRUE ; free ( node ) ; } else { if ( node -> left == NULL ) { root = node -> right ; *h = TRUE ; free ( node ) ; } else { node -> right = del ( node -> right, node, h ) ; if ( *h ) root = balleft ( root, h ) ; } } } } } return ( root ) ; } struct AVLNode * del ( struct AVLNode *succ, struct AVLNode *node, int *h ) { struct AVLNode *temp = succ ; if ( succ -> left != NULL ) { succ -> left = del ( succ -> left, node, h ) ; if ( *h ) succ = balright ( succ, h ) ; } else { temp = succ ; node -> data = succ -> data ; succ = succ -> right ; free ( temp ) ; *h = TRUE ; } return ( succ ) ; } /* balances the tree, if right sub-tree is higher */ struct AVLNode * balright ( struct AVLNode *root, int *h ) { struct AVLNode *node1, *node2 ; switch ( root -> balfact ) { case 1: root -> balfact = 0 ; break; case 0: root -> balfact = -1 ; *h = FALSE ; break; case -1: node1 = root -> right ; if ( node1 -> balfact <= 0 ) { printf ( "\nLeft rotation along %d.", root -> data ) ; root -> right = node1 -> left ; node1 -> left = root ; if ( node1 -> balfact == 0 ) { root -> balfact = -1 ; node1 -> balfact = 1 ; *h = FALSE ; } else { root -> balfact = node1 -> balfact = 0 ; } root = node1 ; } else { printf ( "\nDouble rotation, right along %d", node1 -> data ); node2 = node1 -> left ; node1 -> left = node2 -> right ; node2 -> right = node1 ; printf ( " then left along %d.\n", root -> data ); root -> right = node2 -> left ; node2 -> left = root ; if ( node2 -> balfact == -1 ) root -> balfact = 1 ; else root -> balfact = 0 ; if ( node2 -> balfact == 1 ) node1 -> balfact = -1 ; else node1 -> balfact = 0 ; root = node2 ; node2 -> balfact = 0 ; } } return ( root ) ; } /* balances the tree, if left sub-tree is higher */ struct AVLNode * balleft ( struct AVLNode *root, int *h ) { struct AVLNode *node1, *node2 ; switch ( root -> balfact ) { case -1: root -> balfact = 0 ; break ; case 0: root -> balfact = 1 ; *h = FALSE ; break ; case 1: node1 = root -> left ; if ( node1 -> balfact >= 0 ) { printf ( "\nRight rotation along %d.", root -> data ) ; root -> left = node1 -> right ; node1 -> right = root ; if ( node1 -> balfact == 0 ) { root -> balfact = 1 ; node1 -> balfact = -1 ; *h = FALSE ; } else { root -> balfact = node1 -> balfact = 0 ; } root = node1 ; } else { printf ( "\nDouble rotation, left along %d", node1 -> data ) ; node2 = node1 -> right ; node1 -> right = node2 -> left ; node2 -> left = node1 ; printf ( " then right along %d.\n", root -> data ) ; root -> left = node2 -> right ; node2 -> right = root ; if ( node2 -> balfact == 1 ) root -> balfact = -1 ; else root -> balfact = 0 ; if ( node2-> balfact == -1 ) node1 -> balfact = 1 ; else node1 -> balfact = 0 ; root = node2 ; node2 -> balfact = 0 ; } } return ( root ) ; } /* displays the tree in-order */ void display ( struct AVLNode *root ) { if ( root != NULL ) { display ( root -> left ) ; printf ( "%d\t", root -> data ) ; display ( root -> right ) ; } } /* deletes the tree */ void deltree ( struct AVLNode *root ) { if ( root != NULL ) { deltree ( root -> left ) ; deltree ( root -> right ) ; } free ( root ) ; }

Make Empty

This operation is for mainly intialization and can be used to destroy entire search tree also.

i want to insert this functions inside the programCode:Tree *make_empty(Tree *t) { if (t != NULL) { make_empty(t->left); make_empty(t->right); free(t); t = NULL; } return NULL; }

Height

Finds height of the tree

i want to insert this functions inside the programCode:int height(Tree *t) { if (t == NULL) { return -1; } else { return t->height; } }

Find

This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.

We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the

element stored in the tree node

i want to insert this functions inside the programCode:Tree *find(int elem, Tree *t) { if (t == NULL) { return NULL; } if (elem < t->element) { return find(elem, t->left); } else if (elem > t->element) { return find(elem, t->right); } else { return t; } }

FindMin

This operation returns the smallest element node in the tree, i.e. left most element of the tree

Code:Tree *find_min(Tree *t) { if (t == NULL) { return NULL; } else if (t->left == NULL) { return t; } else { return find_min(t->left); } }FindMax

This operation returns the biggest element node in the tree, i.e. right most element of the tree

Code:Tree *find_max(Tree *t) { if (t == NULL) { return NULL; } else if (t->right == NULL) { return t; } else { return find_max(t->right); } }Insert

This operation applies a Find operation on the tree, if its found, does nothing., otherwise,

insert the element at the last spot on the path traversed. After insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition. We need to rebalance the tree to satisfy AVL property. A violation of the AVL property may occur in four cases: (N is a node to be rebalanced)

1) An insertion into the left subtree of the left child of the node N

2) An insertion into the right subtree of the left child of the node N

3) An insertion into the left subtree of the right child of the node N

4) An insertion into the right subtree of the right child of the node N

cases 1 & 4 can be fixed bysingle rotation

cases 2 & 3 can be fixed bydouble rotation

single and double rotation will be explained after explaing insert and delete operations.

//Insert i into the tree t, duplicate will be discarded

//Return a pointer to the resulting tree.

Code:Tree * insert(int value, Tree * t) { Tree * new_node; if (t == NULL) { new_node = (Tree *) malloc (sizeof (Tree)); if (new_node == NULL) { return t; } new_node->element = value; new_node->height = 0; new_node->left = new_node->right = NULL; return new_node; } else if (value < t->element) { t->left = insert(value, t->left); if (height(t->left) - height(t->right) == 2) { if (value < t->left->element) { t = single_rotation_with_left(t); } else { t = double_rotation_with_left(t); } } } else if (value > t->element) { t->right = insert(value, t->right); if (height(t->right) - height(t->left) == 2) { if (value > t->right->element) { t = single_rotation_with_right(t); } else { t = double_rotation_with_right(t); } } } //else duplicate, ignore it t->height = MAX(height(t->left), height(t->right)) + 1; return t; }

i had a hard time to find the COMPARE function ... which make this code incomplete! ...

if someone can insert the remaining functions that i listed above please help...

lastly ... can someone provide or add COMPARE function! ...

thanks in advance ... it gives me a headache with this project!

thank you!