Java

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1388 palavras )
  • Download(s) : 0
  • Publicado : 10 de maio de 2011
Ler documento completo
Amostra do texto
Introdução:
A base deste trabalho é a implementação das Arvores Binárias. Para uma melhor comparação de desempenho entre outras arvores binárias.
Definição:
Uma árvore binária (chamada de binária pois de cada nó podem nascer até 2 novos nós) é uma estrutura de dados caracterizada por:
- Ou não tem elemento algum (árvore vazia).
- Ou tem um elemento distinto, denominado raiz, comdois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Uma definição mais concreta.Uma árvore binária(= binary tree) é formada de nós; cada nó tem um certo conteúdo (por exemplo, um número inteiro) e os endereços (das raízes) de duas subárvores: uma esquerda e uma direita.As árvores B são árvores balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário como discos magnéticos. Elas visam otimizar as operações de entrada e saída nos dispositivos. O tempo de acesso àsinformações em um disco é prejudicado principalmente pelo tempo de posicionamento do braço de leitura. Uma vez que o braço esteja posicionado no local correto, a leitura pode ser feita de forma bastante rápida. Desta forma, devemos minimizar o número de acessos ao disco. Diferente das árvores binárias, cada nó em uma árvore B pode ter muitos filhos, isto é, o grau de um nó pode ser muito grande.Algoritmo da inserção em Java:
public void Inserir(No novo, No anterior){
if (anterior != null){
if (novo.ObtemValor() < anterior.ObtemValor())
//Como o novo nó tem valor menor do que o do nó anterior, desce para a esquerda do nó anterior.
inicio.filho_Esq=this.Insere(novo, anterior.filho_Esq);
elseif(novo.ObtemValor()>anterior.ObtemValor())
//Como o novo nó tem valor maior do que o do nó anterior, desce para a direita do nó anterior.
anterior.p_Dir=this.Insere(filho, anterior.filho_Dir);
else
//Caso seja um nó já existente, sai do método.
return;
}else
//Insere o novo nó como folha.
anterior = novo;
}Definição: Uma árvore B possui as seguintes propriedades:
1. Todo o nó X possui os seguintes campos:
a. n, o número de chaves armazenadas em X;
b. as n chaves k1, k2...kn são armazenadas em ordem crescente;
c. folha, que indica se X é uma folha ou um nó interno.
2. Se X é um nó interno então ele possui n+1 ponteiros f1, f2...fn+1 para seus filhos (podendo algunsserem nulos)
3. Se ki é alguma chave na sub-árvore apontada por fi, então

4. Todas as folhas da árvore estão na mesma altura (que é a altura da árvore).
5. Existe um número máximo e mínimo de filhos em um nó. Este número pode ser descrito em termos de um inteiro fixo t maior ou igual a 2 chamado grau mínimo.
a. Todo o nó diferente da raiz deve possuir pelo menos t-1 chaves.Todo o nó interno diferente da raiz deve possuir pelo menos t filhos. Se a árvore não é vazia, então a raiz possui pelo menos uma chave.
b. Todo o nó pode conter no máximo 2t - 1 chaves. Logo um nó interno pode ter no máximo 2t filhos. Dizemos que um nó é cheio se ele contém 2t - 1 chaves.
const t = 2;
typedef struct no_arvoreB arvoreB;

struct no_arvoreB {
int num_chaves;
charchaves[2*t-1];
arvoreB *filhos[2*t];
bool folha;
}; |
Estrutura do nó |
De acordo com a definição acima a árvore B mais simples ocorre quando t=2. Neste caso todo o nó diferente da raiz possui 2, 3 ou 4 filhos. Esta árvore é também conhecida por árvore 2-3-4.
|
Árvore B com t = 2 |
Dizemos que uma árvore B é de ordem n quando n representa o número máximo de filhos de um nó, exceto a...
tracking img