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

int main()
{
    struct tree _tree;
    struct tree* d = &_tree;
    insert(d,4);
    printf("%d",find(d,4));
    return 0;
}



#ifndef AVL_TREE_H_INCLUDED
#define AVL_TREE_H_INCLUDED
#define LEFT 0
#define RIGHT 1
struct node
{
    int data;
    int balance;
    struct node *leaf[2];
};
struct tree
{
    struct node *root;
};
struct node* single_rotation(struct node *root, int direction);
struct node* double_rotation(struct node *root, int direction);
void adjust_balance(struct node *root, int direction, int balance);
struct node* insert_balance(struct node *root, int direction);
struct node* insert_r(struct node *root, int data, int *done);
struct node* make_node(int data);
int insert(struct tree *_tree, int data);
struct node* remove_balance(struct node* root, int direction, int *done);
struct node* remove_r(struct node *root, int data, int *done);
int _remove(struct tree *_tree, int data);
int find(struct tree *_tree, int data);
int find_r(struct node *root, int data);
#endif // AVL_TREE_H_INCLUDED


#include "avl_tree.h"
#include <stdlib.h>

struct node* make_node(int data)
{
    struct node *rn = malloc(sizeof *rn);
    if(rn != NULL)
    {
        rn->data = data;
        rn->leaf[LEFT] = rn->leaf[RIGHT] = NULL;
    }
    return rn;
}
struct node* single_rotation(struct node *root, int direction)
{
    struct node *save = root->leaf[!direction];
    root->leaf[!direction] = save->leaf[direction];
    save->leaf[direction] = root;
    return save;
}

struct node* double_rotation(struct node *root, int direction)
{
    struct node *save = root->leaf[!direction]->leaf[direction];
    root->leaf[!direction]->leaf[direction] = save->leaf[!direction];
    save->leaf[!direction] = root->leaf[!direction];
    root->leaf[!direction] = save;

    save = root->leaf[!direction];
    root->leaf[!direction] = save->leaf[direction];
    save->leaf[direction] = root;
    return save;
}

void adjust_balance(struct node *root, int direction, int balance)
{
    struct node *n = root->leaf[direction];
    struct node *nn = root->leaf[!direction];

    if(nn->balance == 0)
    {
        root->balance = n->balance = 0;
    }
    else if (nn->balance == balance)
    {
        root->balance = -balance;
        n->balance = 0;
    }
    else if(nn->balance == -balance)
    {
        root->balance = 0;
        n->balance = balance;
    }
    nn->balance = 0;
}

struct node *insert_balance(struct node *root, int direction)
{
    struct node *n = root->leaf[direction];
    int balance;
    if(direction == 0)
    {
        balance = -1;
    }
    else
    {
        balance = +1;
    }
    if(n->balance == balance)
    {
        root->balance = n->balance = 0;
        root = single_rotation(root, !direction);
    }
    else
    {
        adjust_balance(root, direction, balance);
        root = double_rotation(root, !direction);
    }
    return root;
}

struct node* insert_r(struct node *root, int data, int *done)
{
    if(root == NULL)
    {
        root = make_node(data);
    }
    else
    {
        int direction = root->data < data;
        root->leaf[direction] = insert_r(root->leaf[direction], data, done);
        if(!*done)
        {
            if(direction == 0)
            {
                root->balance--;
            }
            else
            {
                root->balance++;
            }
            if(root->balance == 0)
            {
                *done = 1;
            }
            else if(abs(root->balance) > 1)
            {
                root = insert_balance(root,direction);
                *done = 1;
            }
        }
    }
    return root;
}

int insert(struct tree *_tree, int data)
{
    int done = 0;
    _tree->root = insert_r(_tree->root, data, &done);
    return 1;
}

struct node* remove_balance(struct node* root, int direction, int *done)
{
    struct node *n = root->leaf[!direction];
    int balance = direction == 0 ? -1 : +1;
    if(n->balance == -balance)
    {
        root->balance = n->balance = 0;
        root = single_rotation(root,direction);
    }
    else if(n->balance == balance)
    {
        adjust_balance(root, !direction, -balance);
        root = double_rotation(root,direction);
    }
    else if(n->balance == 0)
    {
        root->balance = -balance;
        n->balance = balance;
        root = single_rotation(root,direction);
        *done = 1;
    }
    return root;
}

struct node* remove_r(struct node *root, int data, int *done)
{
    if(root != NULL)
    {
        int direction;
        if(root->data == data)
        {

            if(root->leaf[LEFT] == NULL || root->leaf[1] == NULL)
            {
                struct node *save;
                direction = root->leaf[LEFT] == NULL;
                save = root->leaf[direction];
                free(root);
                return save;
            }
            else
            {
                struct node *heir = root->leaf[LEFT];
                while(heir->leaf[RIGHT] != NULL)
                {
                    heir = heir->leaf[RIGHT];
                }
                root->data = heir->data;
                data = heir->data;
            }
        }
        direction = root->data < data;
        root->leaf[direction] = remove_r(root->leaf[direction], data, done);
        if(!*done)
        {
            root->balance += direction != 0 ? -1 : +1;
            if(abs(root->balance) == 1)
            {
                *done = 1;
            }
            else if(abs(root->balance) > 1)
            {
                root = remove_balance(root,direction,done);
            }
        }
    }
    return root;
}

int _remove(struct tree *_tree, int data)
{
    int done = 0;
    _tree->root = remove_r(_tree->root, data, &done);
    return 1;
}

int find_r(struct node *root, int data)
{
    if(root == NULL)
    {
        return 0-1;
    }
    else if(root->data == data)
    {
        return data;
    }
    else
    {
       int direction = root->data < data;
       return find_r(root->leaf[direction], data);
    }
}

int find(struct tree *_tree, int data)
{
    return find_r(_tree->root, data);
}