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