Logo 
Search:

C Programming Articles

Submit Article
Home » Articles » C Programming » Data File StructureRSS Feeds

Program to maintain an AVL tree

Posted By: Adela Fischer     Category: C Programming     Views: 19935

Program to maintain an AVL tree.

Code for Program to maintain an AVL tree in C Programming

#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 ) ; }
  
Share: 


Didn't find what you were looking for? Find more on Program to maintain an AVL tree Or get search suggestion and latest updates.

Adela Fischer
Adela Fischer author of Program to maintain an AVL tree is from Frankfurt, Germany.
 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!