Arbori AVL

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

#define N 4
#define max(a,b) ((a)>(b)?(a):(b))
#define modul(a) ((a)>0?(a):-(a))

typedef struct tnod {
    int val,h;
    struct tnod *st,*dr;
} tnod;

tnod * make(int );

tnod *findup(tnod *,tnod *);

int height(tnod *);

tnod *parent(tnod *,tnod *);

void add(tnod *&,tnod *);

int leaf(tnod *);

void prefix(tnod *,int );

void rotateL(tnod *&,tnod *);

void rotateR(tnod *&,tnod *);

void rotateRL(tnod *&,tnod *);

void rotateLR(tnod *&,tnod *);

void fixup (tnod* & , tnod* );

tnod* build();

tnod* build1();

tnod* build2();

tnod* build3();

tnod* build4();

int main()
{
    tnod *r = build();
    prefix(r,0);
    return 0;
}

tnod *make(int x)
{
    // create nod nou cu adancime 1
    tnod *nou = (tnod*)malloc(sizeof(tnod));
    nou->val = x;
    nou->h = 1;
    nou->st = nou->dr = NULL;
    return nou;
}

int height(tnod *r)
{
    // inaltimea celui mai inalt subarbore din r
    return (r==NULL?0:r->h);
}

tnod *parent(tnod *r,tnod *p)
{
    // cauta parinte nod p in arbore cu radacina r
    if (r==NULL || p==NULL || p==r)
        return NULL;
    if (p==r->st || p==r->dr)
        return r;
    if (p->val < r->val)
        return parent(r->st,p);
    return parent(r->dr,p);
}

void add(tnod *&r,tnod *p)
{
    // adauga nod p in arbore cu radacina r
    tnod *c;
    if (r==NULL) {
        // arbore vid, initializare radicina cu noul nod
        r=p;
        return;
    }
    c=r;
    while ( c!=NULL ) {
        if (p->val == c->val)
            // daca e gasit in arbore, iesire din functie
            return;

        if (p->val < c->val) {
            // cauta in subarbore stang
            if (c->st == NULL) {
                c->st = p;
                break;
            } else
                c = c->st;
        }
        if (p->val > c->val) {
            // cauta in subarbore drept
            if (c->dr==NULL) {
                c->dr=p;
                break;
            } else
                c=c->dr;
        }
    }

    // actualizarea inaltimilor tuturor nodurilor de deasupra celui adaugat
    c=p;
    while (c!=NULL) {
        c->h = max(height(c->st),height(c->dr))+1;
        c=parent(r,c);
    }
}

int leaf(tnod *r)
{
    // verifica daca e frunza
    if (r==NULL)
        return -1;
    if (r->st || r->dr)
        return 0;
    return 1;
}

void prefix(tnod *r, int sp)
{
    // afisare prefixata indentata
    if (r==NULL)
        return;
    printf("%*c%d(%d)\n",sp,' ',r->val,r->h);
    if (!leaf(r)) {
        if (r->st)
            prefix(r->st,sp+N);
        else
            printf("%*c-\n",sp+N,' ');
        if (r->dr)
            prefix(r->dr,sp+N);
        else
            printf("%*c-\n",sp+N,' ');
    }
}

void rotateL(tnod *&r,tnod *p)
{
    tnod *f,*c;
    if (r==NULL || p==NULL)
        return;
    c=parent(r,p);
    f = p->dr;
    printf("L -> %d\n",p->val);
    p->dr = f->st;
    f->st = p;
    if (c==NULL)
        r = f;
    else
        c->dr=f;
    c = p;
    while (c!=NULL){
        c->h = max(height(c->st),height(c->dr))+1;
        //printf("--[%d - %d]--\n",c->val,c->h);
        c = parent(r,c);
    }
}

void rotateR(tnod *&r,tnod *p)
{
    tnod *f,*c;
    if (r==NULL || p==NULL)
        return;
    c=parent(r,p);
    //printf("R -> %d\n",p->val);
    f = p->st;
    p->st = f->dr;
    f->dr = p;

    if (c==NULL)
        r = f;
    else
        c->st=f;
    c = p;
    while (c!=NULL){
        c->h = max(height(c->st),height(c->dr))+1;
        c = parent(r,c);
    }
}

void rotateRL(tnod *&r,tnod *p)
{
    if (r==NULL || leaf(r))
        return;
    rotateR(r,p->dr);
    //r->h = max(height(r->st),height(r->dr))+1;
    rotateL(r,p);
}

void rotateLR(tnod *&r,tnod *p)
{
    if (r==NULL || leaf(r))
        return;
    rotateL(r,p->st);
    //r->h = max(height(r->st),height(r->dr))+1;
    rotateR(r,p);
}

void fixup (tnod* & r, tnod* nou )
{
    // nou=ultimul nod adaugat
    tnod *p,*f;
    if (r==NULL || nou==NULL)
        return;
    p = findup(r,nou);
    if (p==NULL)
        return;
    else
        printf("-- %d --\n",p->val);
    if (height(p->st) > height(p->dr)) {
        //dezechilibrat stanga
        f = p->st;
        if (height(f->st) > height(f->dr))
            rotateR(r,p);
        else
            rotateLR(r,p);
    } else {
        //dezechilibrat dreapta
        f = p->dr;
        if (height(f->dr) > height(f->st))
            rotateL(r,p);
        else
            rotateRL(r,p);
    }
}

tnod *findup(tnod *r,tnod *p)
{
    tnod *c = parent(r,p);
    while ((c!=NULL && modul(height(c->st)-height(c->dr))<2))
    {
        c=parent(r,c);
    }
    return c;
}

tnod* build()
{
    tnod *r=NULL,*c,*p;
    //int v[]= {1,3,2,4,6,5,7},n=7,i;
    int v[]= {5,4,1,7,8,6,0},n=6,i;
    //int v[]={8,7,6,5,4,3,2,1},n=8,i;
    //int i,n=33;
    for (i=0;i<n;++i){
        c=make(v[i]);
        add(r,c);
        fixup(r,c);
        prefix(r,0);
    }
    return r;
}

tnod *build1()
{
    tnod *r = make(1);
    tnod *doi = make(2),*trei = make(3);
    r->dr = doi;
    r->h = 3;
    doi->dr = trei;
    doi->h = 2;
    return r;
}

tnod *build2()
{
    tnod *r = make(3);
    tnod *doi = make(2),*unu = make(1);
    r->st = doi;
    r->h = 3;
    doi ->st = unu;
    doi -> h = 2;
    return r;
}

tnod *build4()
{
    tnod *r = make(3);
    tnod *doi = make(2),*unu = make(1);
    r->st = unu;
    r->h = 3;
    unu ->dr = doi;
    unu -> h = 2;
    return r;
}

tnod* build3()
{
    tnod* r= make(1);
    tnod *doi = make(2),*trei=make(3);
    r->dr=trei;
    r->h=3;
    trei->st=doi;
    trei->h=2;
    return r;
}