Skip to content

Instantly share code, notes, and snippets.

@gabrielkw

gabrielkw/avl.c

Last active April 25, 2017 13:21
Show Gist options
  • Save gabrielkw/11c6dab20c0925526806d2f8986368c5 to your computer and use it in GitHub Desktop.
Save gabrielkw/11c6dab20c0925526806d2f8986368c5 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment