avl.c

// Árvore AVL em C

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

int maiorEntre(int a, int b) {
    if(a > b) {
        return a;
    } else {
        return b;
    }
}

typedef struct Nodo {
    int altura;
    int valor;
    struct Nodo *filhoEsquerdo;
    struct Nodo *filhoDireito;
} Nodo;

Nodo* novoNodo(int novoValor) {
    Nodo* N = malloc(sizeof(Nodo));

    N->valor = novoValor;
    N->altura=1;
    N->filhoDireito=N->filhoEsquerdo=NULL;

    return N;
}

int altura(Nodo *N) {
    if(N == NULL) return 0;

    return N->altura;
}

int fatorDeBalanceamento(Nodo *N) {
    if (N == NULL) return 0;

    return altura(N->filhoEsquerdo) - altura(N->filhoDireito);
}

Nodo* menorNodo(Nodo *N) {
    Nodo *ponteiro = N;

    while(ponteiro->filhoEsquerdo != NULL) {
        ponteiro = ponteiro->filhoEsquerdo;
    }

    return ponteiro;
}

Nodo* maiorNodo(Nodo *N) {
    Nodo *ponteiro = N;

    while(ponteiro->filhoDireito != NULL) {
        ponteiro = ponteiro->filhoDireito;
    }

    return ponteiro;
}

Nodo* rotacaoParaDireita(Nodo *y) {
    //        z                                   y
    //       / \                                /   \
    //      y   T4   Rotação à direita (z)     x      z
    //     / \       - - - - - - - - ->      /  \    /  \
    //    x   T3                            T1  T2  T3  T4
    //   / \
    // T1   T2
    //
    Nodo *x = y->filhoEsquerdo;
    Nodo *T2 = x->filhoDireito;

    x->filhoDireito = y;
    y->filhoEsquerdo = T2;

    y->altura = 1 + maiorEntre(altura(y->filhoEsquerdo), altura(y->filhoDireito));
    x->altura = 1 + maiorEntre(altura(x->filhoEsquerdo), altura(x->filhoDireito));

    return x;
}

Nodo* rotacaoParaEsquerda(Nodo *x) {
    //   z                                  y
    //  /  \                              /   \ 
    // T1   y     Rotação à esquerda(z)  z      x
    //     /  \   - - - - - - - ->      / \    / \
    //    T2   x                       T1  T2 T3  T4
    //        / \
    //      T3  T4
    //
    Nodo *y = x->filhoDireito;
    Nodo *T2 = y->filhoEsquerdo;

    y->filhoEsquerdo = x;
    x->filhoDireito = T2;

    x->altura = 1 + maiorEntre(altura(x->filhoEsquerdo), altura(x->filhoDireito));
    y->altura = 1 + maiorEntre(altura(y->filhoEsquerdo), altura(y->filhoDireito));

    return y;
}

Nodo* inserir(Nodo* N, int valorParaInserir) {
    if (N == NULL) return(novoNodo(valorParaInserir));

    if (valorParaInserir < N->valor) {
        N->filhoEsquerdo  = inserir(N->filhoEsquerdo, valorParaInserir);
    } else if (valorParaInserir > N->valor) {
        N->filhoDireito = inserir(N->filhoDireito, valorParaInserir);
    } else {
        return N;
    }

    N->altura = 1 + maiorEntre(altura(N->filhoEsquerdo), altura(N->filhoDireito));

    int fator = fatorDeBalanceamento(N);

    if (fator > 1 && valorParaInserir < N->filhoEsquerdo->valor) {
        // Caso esquerda-esquerda
        // T1, T2, T3 e T4 são sub-árvores.
        //        z                                   y
        //       / \                                /   \
        //      y   T4   Rotação à direita (z)     x      z
        //     / \       - - - - - - - - ->      /  \    /  \
        //    x   T3                            T1  T2  T3  T4
        //   / \
        // T1   T2
        //
        return rotacaoParaDireita(N);
    }

    if (fator < -1 && valorParaInserir > N->filhoDireito->valor) {
        // Caso direita-direita
        //   z                                  y
        //  /  \                              /   \ 
        // T1   y     Rotação à esquerda(z)  z      x
        //     /  \   - - - - - - - ->      / \    / \
        //    T2   x                       T1  T2 T3  T4
        //        / \
        //      T3  T4
        //
        return rotacaoParaEsquerda(N);
    }

    if (fator > 1 && valorParaInserir > N->filhoEsquerdo->valor) {
        // Caso esquerda-direita
        //      z                           z                         x
        //     / \                        /   \                      /  \ 
        //    y   T4  Rot. esquerda (y)  x    T4  Rot. direita(z)  y      z
        //   / \      - - - - - ->      /  \      - - - - - - ->  / \    / \
        // T1   x                      y    T3                  T1  T2 T3  T4
        //     / \                    / \
        //   T2   T3                T1   T2
        //
        N->filhoEsquerdo =  rotacaoParaEsquerda(N->filhoEsquerdo);

        return rotacaoParaDireita(N);
    }

    if (fator < -1 && valorParaInserir < N->filhoDireito->valor) {
        // Caso direita-esquerda
        //    z                        z                           x
        //   / \                      / \                         /  \ 
        // T1   y   Rot. direita (y) T1  x   Rot. esquerda(z)   z      y
        //     / \  - - - - - - - ->   /  \   - - - - - - ->   / \    / \
        //    x   T4                  T2   y                 T1  T2  T3  T4
        //   / \                          /  \
        // T2   T3                      T3   T4
        //
        N->filhoDireito = rotacaoParaDireita(N->filhoDireito);

        return rotacaoParaEsquerda(N);
    }

    return N;
}

Nodo* remover(Nodo *N, int valorParaRemover) {
    if(N ==  NULL) return N;

    if(valorParaRemover < N->valor) {
        N->filhoEsquerdo = remover(N->filhoEsquerdo, valorParaRemover);
    } else if(valorParaRemover > N->valor) {
        N->filhoDireito = remover(N->filhoDireito, valorParaRemover);
    } else {
        if( (N->filhoEsquerdo != NULL) && (N->filhoDireito != NULL) ) {
            // Se o nodo possui dois filhos não-nulos...
            Nodo *temp = menorNodo(N->filhoDireito);

            N->valor = temp->valor;
            N->filhoDireito = remover(N->filhoDireito, temp->valor);
        } else {
            // Se qualquer um dos filhos for nulo...
            Nodo *temp;

            if(N->filhoEsquerdo != NULL) {
                temp = N->filhoEsquerdo;
            } else {
                temp = N->filhoDireito;
            }

            if(temp == NULL) {
                temp = N;
                N = NULL;
            } else {
                *N = *temp;
            }

            free(temp);
        }

        if(N ==  NULL) return N;

        N->altura = 1 + maiorEntre(altura(N->filhoEsquerdo),altura(N->filhoDireito));

        int fator = fatorDeBalanceamento(N);

        if(fator > 1 && fatorDeBalanceamento(N->filhoEsquerdo) >= 0) {
            return rotacaoParaDireita(N);
        }

        if(fator > 1 && fatorDeBalanceamento(N->filhoEsquerdo) < 0) {
            N->filhoEsquerdo = rotacaoParaEsquerda(N->filhoEsquerdo);
            return rotacaoParaDireita(N);
        }

        if(fator < -1 && fatorDeBalanceamento(N->filhoDireito) <= 0) {
            return rotacaoParaEsquerda(N);
        }

        if(fator < -1 && fatorDeBalanceamento(N->filhoDireito) > 0) {
            N->filhoDireito = rotacaoParaDireita(N->filhoDireito);
            return rotacaoParaEsquerda(N);
        }

        return N;
    }
}

void imprimirEmPreOrdem(Nodo *N) {
    if(N != NULL) {
        printf("%d ", N->valor);
        imprimirEmPreOrdem(N->filhoEsquerdo);
        imprimirEmPreOrdem(N->filhoDireito);
    }
}

int main() {
    Nodo *raiz = NULL;

    raiz = inserir(raiz, 53);
    raiz = inserir(raiz, 23);
    raiz = inserir(raiz, 29);
    raiz = inserir(raiz, 13);
    raiz = inserir(raiz, 37);
    raiz = inserir(raiz, 97);
    raiz = inserir(raiz, 61);
    raiz = inserir(raiz, 47);
    raiz = inserir(raiz, 73);
    raiz = inserir(raiz, 71);
    raiz = inserir(raiz, 19);
    raiz = inserir(raiz, 59);
    raiz = inserir(raiz, 89);

    imprimirEmPreOrdem(raiz);
    printf("\n menor: %d \n maior: %d", menorNodo(raiz)->valor, maiorNodo(raiz)->valor);
    printf("\n");

    raiz = remover(raiz, 19);
    raiz = remover(raiz, 13);
    raiz = remover(raiz, 97);

    imprimirEmPreOrdem(raiz);

    printf("\n menor: %d \n maior: %d", menorNodo(raiz)->valor, maiorNodo(raiz)->valor);

    printf("\n");
    return 0;
}