#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int value;
    int balance;
    struct node *left, *right;
}node;

void allocation_check(void* ptr)
{
    if (!ptr)
    {
        printf("Greska pri alokaciji!\n");
        exit(1);
    }
}

node* create_node(int val)
{
    node *new_node = malloc(sizeof(node));

    allocation_check(new_node);

    new_node->value = val;
    new_node->balance = 0;
    new_node->left = NULL;
    new_node->right = NULL;

    return new_node;
}

void l_rotation(node **root)
{
    node *new_root = (*root)->right;
    node *old_root = *root;
    (*root)->right = new_root->left;    
    new_root->left = (*root);
    (*root) = new_root;   

    int old_root_balance = old_root->balance;     
    int new_root_balance = new_root->balance;

    old_root->balance = old_root_balance - 1 -
                    (new_root_balance > 0 ? new_root_balance : 0);
    new_root->balance = new_root_balance - 1 +
                        (old_root->balance < 0 ? old_root->balance : 0);

}

void r_rotation(node **root)
{
    node *new_root = (*root)->left;
    node *old_root = *root;
    (*root)->left = new_root->right;    
    new_root->right = (*root);
    (*root) = new_root;

    int old_root_balance = old_root->balance;     
    int new_root_balance = new_root->balance;

    old_root->balance = old_root_balance + 1 -
                        (new_root_balance < 0 ? new_root_balance : 0);
    new_root->balance = new_root_balance + 1 +
                        (old_root->balance > 0 ? old_root->balance : 0);
}

void rl_rotation(node **root)
{
    r_rotation(&(*root)->right);
    l_rotation(root);
}

void lr_rotation(node **root)
{
    l_rotation(&(*root)->left);
    r_rotation(root);
}

int node_height(node* root)
{
    if (root == NULL) return 0;
    int l_height = node_height(root->left);
    int r_height = node_height(root->right);
    return (l_height > r_height) ? l_height + 1 : r_height + 1;
}

int add_node(node **root, int value)
{   
    // Ako si dosao do NULL vrednosti, to je mesto za novi cvor
    if (*root == NULL)
    {
        // Napravi novi cvor sa datom vrednoscu
        *root = create_node(value);
        return 1;
    }
    // Ako je duplikat, odbaci ga
    if (value == (*root)->value) return 0;
    // Rekurzivno prolazi kroz stablo da nadjes poziciju u stablu na koju cvor treba da se doda
    int increment = 0;
    if (value < (*root)->value) 
    {
        increment = -add_node(&(*root)->left, value);
    }
    else 
    {
        increment = add_node(&(*root)->right, value);
    }
     
    // Pri povratku iz rekurzije updejtuj balans    
    (*root)->balance += increment;

    // Ako je balans narusen, proveri na koji nacin je narusen i napravi rotaciju
    if (increment != 0 && (*root)->balance != 0)
    {
        // Levi disbalans
        if ((*root)->balance < -1) 
        {
            if ((*root)->left->balance < 0)
            {
                // LL
                r_rotation(root);
            }
            else
            {
                // LR
                l_rotation(&(*root)->left);
                r_rotation(root);
            }
            return 0;
        }
        // Desni disbalans
        else if ((*root)->balance > 1)
        {
            if ((*root)->right->balance > 0)
            {
                // RR
                l_rotation(root);
            }
            else
            {
                // RL
                r_rotation(&(*root)->right);
                l_rotation(root);
            }
            return 0;
        }
        else
        {
            // Balans je 1 ili -1, nije bilo potrebe za rotacijom ali se visina povecala
            return 1;
        }
    }
    else
    {
        // Increment je 1 a balans 0, visina se nije povecala
        // Ili je increment 0 a balans je 1 ili -1 sto znaci da se visina nije menjala
        return 0;
    }
}

void create_avl(node **root,int* init_values, int n)
{
    for(int i=0; i<n; i++)
    {
        add_node(root,*(init_values+i));
    }
}

void free_avl(node **root)
{
    if (root == NULL || *root == NULL)
    {
        return;
    }

    free_avl(&(*root)->left);
    free_avl(&(*root)->right);

    free(*root);
    *root = NULL;
}

void visualize_avl(node* tree, int level)
{   
    if (tree == NULL) return;

    visualize_avl(tree->right, level + 1);
    
    for(int i = 0; i < level; i++) 
        printf("     ");
    printf("%3d(%+d)\n", tree->value, tree->balance);

    visualize_avl(tree->left, level + 1);
}

int main()
{
    node *root = NULL;
    int init_values [] = {10,20,30};

    // Napravi stablo
    create_avl(&root, init_values, sizeof(init_values)/sizeof(int));

    // Ispisi stablo
    visualize_avl(root, 1);
    printf("----------------------\n");
    // Dodaj nove elemente
    int val;
    while(scanf("%d",&val) == 1)
    {
        add_node(&root,val);
        visualize_avl(root, 1);
        printf("----------------------\n");
    }

    // Obrisi stablo
    free_avl(&root);

    return 0;
}