#include <iostream>
#include <conio.h>
using namespace std;

struct node{
        int val;
        int bf;
        node *left;
        node *right;
        node *up;
};

void lr(struct node *root,struct node *A){
        struct node *B=A->left;
        struct node *C=B->right;
        struct node *D=A->up;
        B->right=C->left;
        if(B->right)    B->right->up=B;
        A->left=C->right;
        if(A->left)     A->left->up=A;
        C->right=A;
        C->left=B;
        A->up=B->up=C;
        C->up=D;
        if(D){
                if(D->left==A)  D->left=C;
                else            D->right=C;
        }
        else root=C;
        if(C->bf==1)    A->bf=-1;
        else            A->bf=0;
        if(C->bf==-1)   B->bf=1;
        else            B->bf=0;
        C->bf=0;
        return;
}

void ll(struct node *root,struct node *A){
        struct node *B=A->left;
        struct node *C=A->up;
        A->left = B->right;
        if(A->left)     A->left->up=A;
        B->right=A;
        B->up=C;
        A->up=B;
        if(C){
                if(C->left==A)  C->left=B;
                else            C->right=B;
        }
        else root=B;
        if(B->bf == 1)  A->bf=B->bf=0;
        else{
                A->bf=1;
                B->bf=-1;
        }
        return;
}

void rl(struct node *root,struct node *A){
        struct node *B=A->right;
        struct node *C=B->left;
        struct node *D=A->up;
        B->left=C->right;
        if(B->left)     B->left->up=B;
        A->right=C->left;
        if(A->right)    A->right->up=A;
        C->left=A;
        C->right=B;
        A->up=B->up=C;
        C->up=D;
        if(D){
                if(D->left==A)  D->left=C;
                else            D->right=C;
        }
        else root=C;
        if(C->bf==-1)   A->bf=1;
        else            A->bf=0;
        if(C->bf==1)    B->bf=-1;
        else            B->bf=0;
        C->bf = 0;
        return;
}

void rr(struct node *root,struct node *A){
        struct node *B=A->right;
        struct node *C = A->up;
        A->right=B->left;
        if(A->right) A->right->up=A;
        B->left=A;
        B->up=C;
        A->up=B;
        if(C){
                if(C->left==A)  C->left=B;
                else            C->right=B;
        }
        else    root=B;
        if(B->bf==-1)   A->bf=B->bf=0;
        else{
                A->bf=-1;
                B->bf=1;
        }
        return;
}

void node_add(struct node *tree,int b){
        struct node *add=new struct node;
        struct node *tmp;
        struct node *root=tree;
        bool t;
        if(tree==NULL){
                tree=add;
                tree->left=NULL;
                tree->right=NULL;
                tree->up=NULL;
                tree->val=b;
                return;
        }
        while(true){
                if(b>=tree->val){
                        if(tree->right==NULL){
                                tree->right=add;
                                add->val=b;
                                add->left=NULL;
                                add->right=NULL;
                                add->bf=0;
                                add->up=tree;
                                break;
                        }
                        else    tree=tree->right;
                }
                else{
                        if(tree->left==NULL){
                                tree->left=add;
                                add->val=b;
                                add->left=NULL;
                                add->right=NULL;
                                add->bf=0;
                                add->up=tree;
                                break;
                        }
                        else    tree=tree->left;
                }
        }
        if(tree->bf)    tree->bf=0;
        else{
                if(tree->left==add)     tree->bf=1;
                else                    tree->bf=-1;
                tmp=tree->up;
                t=false;
                while(tmp){
                        if(tmp->bf){
                                t=true;
                                break;
                        }
                        if(tmp->left==tree)     tmp->bf=1;
                        else                    tmp->bf=-1;

                        tree=tmp;
                        tmp=tmp->up;
                }
                if(t){
                        if(tmp->bf==1){
                                if(tmp->right==tree)    tmp->bf = 0;
                                else if(tree->bf==-1)   lr(root,tmp);
                                else                    ll(root,tmp);
                        }
                        else{
                                if(tmp->left==tree)     tmp->bf=0;
                                else if(tree->bf==1)    rl(root,tmp);
                                else                    rr(root,tmp);
                        }
                }
        }
        return;
}

int main(){
        struct node *root=new struct node;
        root=NULL;
        node_add(root,2);
        node_add(root,3);
        node_add(root,1);
        node_add(root,5);
        node_add(root,10);
        node_add(root,9);
        node_add(root,8);
        node_add(root,5);

        return 0;
}