Arvores

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1125 palavras )
  • Download(s) : 0
  • Publicado : 18 de maio de 2012
Ler documento completo
Amostra do texto
Árvore B
-----------------------------------------------------------------------------------

#include
#include
#include
#define m 2
#define mm 4
#define reservado "cls"

typedef int TipoChave;
typedef struct
{
TipoChave Chave;
} Registro;

typedef struct Pagina_str *Apontador;
typedef struct Pagina_str
{
int n;
Registro r[mm];
Apontador p[mm + 1];
}Pagina;

typedef Apontador TipoDicionario;
void Inicializa(TipoDicionario *Dicionario)
{
*Dicionario = NULL;
} /* Inicializa */

void Pesquisa(Registro *x, Apontador Ap)
{
int i;

if (Ap == NULL)
{
printf("Erro: Registro nao esta presente\n");
getchar();
getchar();
return;
}
i = 1;
while (i < Ap->n && x->Chave > Ap->r[i - 1].Chave)i++;
if (x->Chave == Ap->r[i - 1].Chave)
{
*x = Ap->r[i - 1];
return;
}
if (x->Chave < Ap->r[i - 1].Chave)
Pesquisa(x, Ap->p[i - 1]);
else
Pesquisa(x, Ap->p[i]);
} /* Pesquisa */

void InsereNaPagina(Apontador Ap, Registro Reg, Apontador ApDir)
{
int k;
int NaoAchouPosicao;

k = Ap->n;
NaoAchouPosicao = k > 0;
while(NaoAchouPosicao)
{
if (Reg.Chave >= Ap->r[k - 1].Chave)
{
NaoAchouPosicao = 0;
break;
}
Ap->r[k] = Ap->r[k - 1];
Ap->p[k + 1] = Ap->p[k];
k--;
if (k < 1)
NaoAchouPosicao = 0;
}
Ap->r[k] = Reg;
Ap->p[k + 1] = ApDir;
Ap->n++;
} /*InsereNaPagina*/

void Ins(Registro Reg, Apontador Ap, int *Cresceu,Registro *RegRetorno, Apontador *ApRetorno)
{
Apontador ApTemp;
int i, j;

if (Ap == NULL)
{
*Cresceu = 1;
*RegRetorno = Reg;
*ApRetorno = NULL;
return;
}
i = 1;
while (i < Ap->n && Reg.Chave > Ap->r[i - 1].Chave)
i++;
if (Reg.Chave == Ap->r[i - 1].Chave)
{
printf(" Erro: Registro ja esta presente\n");
getchar();getchar();
*Cresceu = 0;
return;
}
if (Reg.Chave < Ap->r[i - 1].Chave)
Ins(Reg, Ap->p[i - 1], Cresceu, RegRetorno, ApRetorno);
else
Ins(Reg, Ap->p[i], Cresceu, RegRetorno, ApRetorno);
if (!*Cresceu)
return;
if (Ap->n < mm)
{ /* Pagina tem espaco */
InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
*Cresceu = 0;return;
}
/* Overflow: Pagina tem que ser dividida */
ApTemp = (Apontador) malloc(sizeof(Pagina));
ApTemp->n = 0;
ApTemp->p[0] = NULL;
if (i r[mm - 1], Ap->p[mm]);
Ap->n--;
InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
}
else
InsereNaPagina(ApTemp, *RegRetorno, *ApRetorno);
for (j = m + 2; j r[j - 1], Ap->p[j]);
Ap->n = m;
ApTemp->p[0] =Ap->p[m + 1];
*RegRetorno = Ap->r[m];
*ApRetorno = ApTemp;
} /*Ins*/


void Insere(Registro Reg, Apontador *Ap)
{
int Cresceu;
Registro RegRetorno;
Apontador ApRetorno;
Apontador ApTemp;

Ins(Reg, *Ap, &Cresceu, &RegRetorno, &ApRetorno);
if (Cresceu) { /* Arvore cresce na altura pela raiz */
ApTemp = (Apontador) malloc(sizeof(Pagina));
ApTemp->n= 1;
ApTemp->r[0] = RegRetorno;
ApTemp->p[1] = ApRetorno;
ApTemp->p[0] = *Ap;
*Ap = ApTemp;
}
} /*Insere*/

void Reconstitui(Apontador ApPag, Apontador ApPai, int PosPai, int *Diminuiu)
{
Apontador Aux;
int DispAux, j;

if (PosPai < ApPai->n) { /* Aux = Pagina a direita de ApPag */
Aux = ApPai->p[PosPai + 1];
DispAux = (Aux->n - m+ 1) / 2;
ApPag->r[ApPag->n] = ApPai->r[PosPai];
ApPag->p[ApPag->n + 1] = Aux->p[0];
ApPag->n++;
if (DispAux > 0) { /* Existe folga: transfere de Aux para ApPag */
for (j = 1; j < DispAux; j++)
InsereNaPagina(ApPag, Aux->r[j - 1], Aux->p[j]);
ApPai->r[PosPai] = Aux->r[DispAux - 1];
Aux->n -= DispAux;
for (j = 0; j...
tracking img