/***
    *
    * @author cin.ufpe.br/~vags
    * @since 01/09/16
    *
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct tree{
    int id, height, balance;
    struct tree *left, *right;
}Tree;

void addNode(Tree **node, Tree *new);
void rotateRight(Tree **node);
void rotateLeft(Tree **node);
void rebalanceTree(Tree **node);
int isBalancedTree(Tree *node);
int getTreeBalance(Tree *node);
int getHeight(Tree *node);
int maxValue(int a, int b);
void showTree(Tree *node);
int recalcAllHeights(Tree **node);
Tree *root = NULL, **unbalanced = NULL;

int main(int argc, char const *argv[]){
    int n;
    printf("----");
    while(scanf(" %d", &n) == 1){
            printf("\nAdicionando %d", n);
            Tree *new = malloc(sizeof(Tree));
            new->id = n;
            addNode(&root, new);
            recalcAllHeights(&root);
            if(unbalanced == NULL){
                printf("\nContinuou AVL...\n  ");
                showTree(root);
            }else{
                printf("\nAntes de ajustar balanceamento...\n  ");
                showTree(root);
                rebalanceTree(unbalanced);
                printf("\nDepois de ajustar balanceamento...\n  ");
                showTree(root);
            }
            recalcAllHeights(&root);
            printf("\n----");
    }
    return 0;
}
int maxValue(int a, int b){
    return a > b ? a : b;
}
int getHeight(Tree *node){
    return node == NULL ? 0 : node->height;
}
int getTreeBalance(Tree *node){
    if(node == NULL){
        return 0;
    }else{
        return node->balance = getHeight(node->right) - getHeight(node->left);
    }
}
int recalcAllHeights(Tree **node){
    if(*node == NULL){
        return 0;
    }else{
        (*node)->height = 1 + maxValue(recalcAllHeights(&(*node)->left), recalcAllHeights(&(*node)->right));
        (*node)->balance = getTreeBalance((*node));
        if(unbalanced == NULL && ((*node)->balance < -1 || 1 < (*node)->balance))
            unbalanced = node;
        return (*node)->height;
    }
}
void addNode(Tree **node, Tree *new){
    if((*node) == NULL){
        (*node) = new;
        new->left = new->right = NULL;
    }else if(new->id >= (*node)->id){
        //adding to right
        addNode(&((*node)->right), new);
    }else{
        //adding to left
        addNode(&((*node)->left), new);
    }
}
void rebalanceTree(Tree **node){
    if(getTreeBalance(*node) > 1){
        rotateLeft(node);
    }else if(getTreeBalance(*node) < -1){
        rotateRight(node);
    }
}
void showTree(Tree *node){
    if(node != NULL){
        printf(" ( %d ", node->id);
        showTree(node->left);
        showTree(node->right);
        printf(") ");
    }else{
        printf(" () ");
    }
}
void rotateRight(Tree **node){
    if(getTreeBalance((*node)->left) >= 1){//Duo rotation
        Tree *leftOfRoot = (*node)->left;
        Tree *newRoot = (*node)->left->right;
        leftOfRoot->right = (*node)->left->right->left;
        (*node)->left = newRoot->right;
        newRoot->left = leftOfRoot;
        newRoot->right = (*node);
        (*node) = newRoot;
    }else{//Simple rotation
        Tree *newRoot = (*node)->left;
        (*node)->left = (*node)->left->right;
        newRoot->right = (*node);
        (*node) = newRoot;
    }
    unbalanced = NULL;
}
void rotateLeft(Tree **node){
    if(getTreeBalance((*node)->right) <= -1){//Duo Rotation
        Tree *rightOfRoot = (*node)->right;
        Tree *newRoot = (*node)->right->left;
        rightOfRoot->left = (*node)->right->left->left;
        (*node)->right = newRoot->right;
        newRoot->right = rightOfRoot;
        newRoot->left = (*node);
        (*node) = newRoot;
    }else{//Simple rotation
        Tree *newRoot = (*node)->right;
        (*node)->right = (*node)->right->left;
        newRoot->left = (*node);
        (*node) = newRoot;
    }
    unbalanced = NULL;
}