Árvore B

//50 10 20 40 30 100 60 70 80 90 200 240 150 230 -9 40 -9 80 -9 200 -9 100 -9 70 -9 230

#include <stdio.h>

#include <stdlib.h>

const int t = 2;

typedef struct ArvB{

int nchaves, folha, *chave;

struct ArvB **filho;

}TAB;

TAB *Cria(int t){

TAB* novo = (TAB*)malloc(sizeof(TAB));

novo->nchaves = 0;

novo->chave =(int*)malloc(sizeof(int*)*((t*2)-1));

novo->folha=1;

novo->filho = (TAB**)malloc(sizeof(TAB*)*t*2);

int i;

for(i=0; i<(t*2); i++) novo->filho[i] = NULL;

return novo;

}

TAB *Libera(TAB *a){

if(a){

if(!a->folha){

int i;

for(i = 0; i <= a->nchaves; i++) Libera(a->filho[i]);

}

free(a->chave);

free(a->filho);

free(a);

return NULL;

}

}

void Imprime(TAB *a, int andar){

if(a){

int i,j;

for(i=0; i<=a->nchaves-1; i++){

Imprime(a->filho[i],andar+1);

for(j=0; j<=andar; j++) printf(" ");

printf("%d\n", a->chave[i]);

}

Imprime(a->filho[i],andar+1);

}

}

TAB *Busca(TAB* x, int ch){

TAB *resp = NULL;

if(!x) return resp;

int i = 0;

while(i < x->nchaves && ch > x->chave[i]) i++;

if(i < x->nchaves && ch == x->chave[i]) return x;

if(x->folha) return resp;

return Busca(x->filho[i], ch);

}

TAB *Inicializa(){

return NULL;

}

TAB *Divisao(TAB *x, int i, TAB* y, int t){

TAB *z=Cria(t);

z->nchaves= t - 1;

z->folha = y->folha;

int j;

for(j=0;j<t-1;j++) z->chave[j] = y->chave[j+t];

if(!y->folha){

for(j=0;j<t;j++){

z->filho[j] = y->filho[j+t];

y->filho[j+t] = NULL;

}

}

y->nchaves = t-1;

for(j=x->nchaves; j>=i; j--) x->filho[j+1]=x->filho[j];

x->filho[i] = z;

for(j=x->nchaves; j>=i; j--) x->chave[j] = x->chave[j-1];

x->chave[i-1] = y->chave[t-1];

x->nchaves++;

return x;

}

TAB *Insere_Nao_Completo(TAB *x, int k, int t){

int i = x->nchaves-1;

if(x->folha){

while((i>=0) && (k<x->chave[i])){

x->chave[i+1] = x->chave[i];

i--;

}

x->chave[i+1] = k;

x->nchaves++;

return x;

}

while((i>=0) && (k<x->chave[i])) i--;

i++;

if(x->filho[i]->nchaves == ((2*t)-1)){

x = Divisao(x, (i+1), x->filho[i], t);

if(k>x->chave[i]) i++;

}

x->filho[i] = Insere_Nao_Completo(x->filho[i], k, t);

return x;

}

TAB *Insere(TAB *T, int k, int t){

if(Busca(T,k)) return T;

if(!T){

T=Cria(t);

T->chave[0] = k;

T->nchaves=1;

return T;

}

if(T->nchaves == (2*t)-1){

TAB *S = Cria(t);

S->nchaves=0;

S->folha = 0;

S->filho[0] = T;

S = Divisao(S,1,T,t);

S = Insere_Nao_Completo(S,k,t);