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

struct drvo{
    int broj;
    int balans;
    struct drvo *levi, *desni;
};

#define novi(x) x=(struct drvo*) malloc(sizeof(struct drvo))

int dodaj(struct drvo**,int);
struct drvo* form();
void ispis(struct drvo*);
void lrotacija(struct drvo**);
void drotacija(struct drvo**);
int dubina(struct drvo*);

int dodaj(struct drvo **p, int vrednost){
    int inkrement, rezultat;
    struct drvo *t=*p;
    rezultat=0;
    if(t==NULL){
        novi(t);
        t->broj=vrednost;
        t->levi=t->desni=NULL;
        t->balans=0;
        rezultat=1;
    }
    else{
        if(vrednost>t->broj)
            inkrement=dodaj(&(t->desni),vrednost);
        else
            inkrement=-dodaj(&(t->levi),vrednost);
        t->balans+=inkrement;
        if(inkrement!=0 && t->balans!=0){
            if(t->balans<-1){
                if(t->levi->balans<0)
                    drotacija(&t);
                else{
                    lrotacija(&(t->levi));
                    drotacija(&t);
                }
            }
            else if(t->balans>1){
                if(t->desni->balans>0)
                    lrotacija(&t);
                else{
                    drotacija(&(t->desni));
                    lrotacija(&t);
                }
            }
            else
                rezultat=1;
        }
    }
    *p=t;
    return rezultat;
}

struct drvo* form(){
    struct drvo *koren;
    int k;
    koren=NULL;
    scanf("%d",&k);
    while(k) {
        dodaj(&koren,k);
        scanf("%d",&k);
    }
    return koren;
}

void ispis(struct drvo *p){
    if (p) {
        ispis(p->levi);
        printf("%5d",p->broj);
        ispis(p->desni);
    }
}

int dubina(struct drvo *p){
    int dl=0,dd=0;
    if(p){
        if (p->levi) dl=dubina(p->levi);
        if (p->desni) dd=dubina(p->desni);
        if (dl>dd) return ++dl;
        else return ++dd;
    }
    else return 0;
}

void lrotacija(struct drvo **t){
    struct drvo *poml,*pomd;
    int stari_balans;
    poml=*t;
    pomd=poml->desni;
    poml->desni=pomd->levi;
    pomd->levi=poml;
    *t=pomd;
    poml->balans=dubina(poml->desni)-dubina(poml->levi);
    pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

void drotacija(struct drvo **t){
    struct drvo *poml,*pomd;
    int stari_balans;
    pomd=*t;
    poml=pomd->levi;
    pomd->levi=poml->desni;
    poml->desni=pomd;
    *t=poml;
    poml->balans=dubina(poml->desni)-dubina(poml->levi);
    pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

void sredi(struct drvo **p){
    struct drvo *t;
    if(*p){
        t=*p;
        if(t->balans<-1){
            if(t->levi->balans<0)
                drotacija(&t);
            else{
                lrotacija(&(t->levi));
                drotacija(&t);
            }
        }
        else if(t->balans>1){
            if(t->desni->balans>0)
                lrotacija(&t);
            else{
                drotacija(&(t->desni));
                lrotacija(&t);
            }
        }
        *p=t;
    }
}

int nadji(struct drvo **p){
    struct drvo *pom,*pom1;
    int rez;
    pom=*p;
    if(!pom->levi){
        rez=pom->broj;
        pom=pom->desni;
    }
    else
        rez=nadji(&(pom->levi));
    if(pom){
        pom->balans=dubina(pom->desni)-dubina(pom->levi);
        sredi(&pom);
    }
    *p=pom;
    return rez;
}

struct drvo* obrisi_b(struct drvo *p, int k){
    struct drvo *pom;
    if(!p) return NULL;
    if(p->broj==k){
        if((!p->levi) && (!p->desni)){
            free(p);
            return NULL;
        }
        if((!p->levi) && (p->desni)){
            pom=p->desni;
            free(p);
            return pom;
        }
        if((p->levi) && (!p->desni)){
            pom=p->levi;
            free(p);
            return pom;
        }
        if((p->levi) && (p->desni)){
            p->broj=nadji(&(p->desni));
            p->balans=dubina(p->desni)-dubina(p->levi);
            sredi(&p);
            return p;
        }
    }
    if(k<p->broj){
        p->levi=obrisi_b(p->levi,k);
        p->balans=dubina(p->desni)-dubina(p->levi);
        sredi(&p);
        return p;
    }
    else{
        p->desni=obrisi_p(p->desni,k);
        p->balans=dubina(p->desni)-dubina(p->levi);
        sredi(&p);
        return p;
    }
}

int main(){
    struct drvo *p,*q;
    p=form();
    ispis(p);
    printf("\n");
    printf("Dubina je %d\n",dubina(p));

    return 0;
}