Codigos Arvores Binarias

BUSCA

unit buscaarvoreb;

int busca_binaria(arvoreB *no, int info)

{

int meio, ini, fim;

ini = 0;

fim = no->num_chaves-1;

while (ini <= fim)

{

meio = (ini + fim)/2;

if (no->chaves[meio] == info)

return(meio); //Encontrou a chave. Devolve a posíção em que a chave está.

else if (no->chave[meio] > info

fim = meio - 1;

else ini = meio + 1;

}

return(i); //Não encontrou a chave. Devolve a posição do ponteiro para o filho.

}

}

INSERÇAO

unit inserirarvoreb1;

procedure

InsereNaPagina (Ap: TipoApontador; Reg: TipoRegistro ; Ap

Dir: TipoApontador);

var

NaoAchouPosicao:

Boolean;

k :

Integer;

begin

with

Ap^

do

begin

k := n; // chave recebe o numero a ser inserido

NaoAchouPosicao := k > 0;

while

NaoAchouPosicao // variavel logica para executar o "Faça"

do

if Reg.Chave < r [k] .Chave

then begin

r [k+1] := r [k ] ; p[k+1] := p[k] ; // deslocamento das chaves para poder inserir

k := k − 1;

if k < 1 // se k for zero ou negativo a variavel recebe falso

then

NaoAchouPosicao :=

false;

end

else

NaoAchouPosicao :=

false;

r [k+1] := Reg; p[k+1] := ApDir;

n := n + 1;

end;

end; // { Insere Na Pagina }

REMOÇAO

unit retiraarvoreb;

// O algoritmo de remoção de uma árvore B deve garantir que as propriedades

// da árvore sejam mantidas, pois uma chave pode ser eliminada de qualquer

// página e não apenas de páginas folha. podem ocorrer

// underflows nas páginas, ou seja, quando há um número abaixo do mínimo

// permitido (d/2 -1) de chaves em uma página,quando nao ocorre underflow pode

// simplesmente ser apagada,porém quando ocorre é necessario mudanças.

procedure Ret(Ch:TipoChave;

var

Ap:TipoApontador;

var

Diminuiu:

Boolean);

var

Ind , j :

Integer;

procedure

Reconstitui (ApPag: TipoApontador; ApPai: TipoApontador;

PosPai:

Integer; var

Diminuiu :

Boolean);

var

Aux: TipoApontador; DispAux, j :

Integer;

begin

if PosPai < ApPai^.n

then begin

//{ Aux = Pagina a direita de ApPag }

Aux := ApPai^.p[PosPai+1];

DispAux := (Aux^.n −M + 1)

div

2;

ApPag^. r [ApPag^.n+1] := ApPai^. r [PosPai+1];

ApPag^.p[ApPag^.n+1] := Aux^.p[0];

ApPag^.n := ApPag^.n + 1;

if DispAux > 0

then begin

//{ Existe folga : transfere de Aux para ApPag }

for

j := 1

to

DispAux − 1 do

InsereNaPagina (ApPag, Aux^. r [ j ] , Aux^.p[ j ] ) ;

ApPai^. r [PosPai+1] := Aux^. r [DispAux] ;

Aux^.n := Aux^.n − DispAux;

for

j := 1

to

Aux^.n

do

Aux^. r [ j ]:=Aux^. r [ j+DispAux] ;

for

j := 0

to

Aux^.n

do

Aux^.p[ j ]:=Aux^.p[ j+DispAux] ;

Diminuiu