Artigo arvores b

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1696 palavras )
  • Download(s) : 0
  • Publicado : 26 de março de 2013
Ler documento completo
Amostra do texto
Faculdades Integradas de Caratinga – FIC
Curso de Ciência da Computação – 3º Período
Disciplina: Ordenação e Pesquisa
Professora: Míriam de Souza Monteiro
Acadêmicos: Camila F. de Freitas Andrade
Lucas Vinicios Azevedo



ÁRVORES B

Introdução
Este estudo tem como objetivo apresentar o funcionamento da árvore B, uma estrutura de dados muito utilizada, pois foi projetadapara otimizar o acesso e a manipulação de um número grande de informações armazenadas em memórias secundárias.

Palavras chave: Árvore B. Inicializar. Pesquisar. Inserir. Remover.

1- A Árvore B
O propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em memórias secundárias. Serve geralmente como estrutura de índice a outros arquivos de registros no qual oíndice pode se tornar muito grande para caber na memória.
Segundo Szwarcfiter; Markenzon (1994, p.166) ”[...] utilizando um recurso de manter mais de uma chave em cada nó da estrutura, proporciona uma organização de ponteiros tal que as operações mencionadas são executadas rapidamente”.
Uma forte característica das árvores B, é que elas são simétricas, os nós folha sempre estão no mesmo nível.Possuem mais de um elemento (registro) dentro de um mesmo nó (página), fazendo assim com que a altura da árvore seja menor do que a de uma árvore binária, por exemplo, resultando numa quantidade menor de acesso a disco.
Em uma árvore B de ordem m temos que: cada página contém no mínimo m registros (e m + 1 descendentes) e no máximo 2m registros (e 2m + 1 descendentes), exceto a página raiz que podeconter entre 1 e 2m registros; todas as páginas folha aparecem no mesmo nível. (ZIVIANI,1999, p. 170).
Sendo definido o valor 2 para a o ordem(M), a quantidade mínima de registros que cada página deve ter será 2, a quantidade máxima será 4, já a quantidade de apontadores para os filhos variam de 3 a 5.
Com a raiz tendo de 1 a 4 registros e 2 a 5 descendentes.


Figura 1.1: Estrutura de umaarvore B.

Páginas Registro Apontador para descentes

2- Inicializar
A função para inicializar a árvore é extremamente simples, semelhante à função para inicializar uma arvore binária, o tipo abstrato de dado dicionário ficará vazio, não contém nem a raiz.
dicionário

Figura 2.1: Inicializando a árvore.

3- Pesquisar
A pesquisa de uma chavena árvore B de acordo com Ziviani (1999, p.171) “[...] é semelhante ao algoritmo Pesquisa para árvore binária de pesquisa”.
O que difere a pesquisa em árvore B é o número de ramificações a partir da quantidade de filhos que a página possui, ou seja, deve decidir entre vários caminhos.
A função recebe primeiramente o ponteiro para a página raiz e o elemento a ser pesquisado, através dapesquisa binária o elemento é comparado com os registros da página até achar o intervalo em que o elemento se encaixe, indo para a sub árvore adequada. Este processo é feito recursivamente até achar o valor ou NULL.
Pesquisando o número 36:


Figura 3.1: Pesquisa com sucesso

Pesquisando o número 2:

Figura 3.1: Pesquisa sem sucesso

4- Inserir
A inserção é realizada na folha, a árvore Bpor ser ordenada e balanceada primeiramente é necessário localizar a página em que o registro será inserido, verificar a quantidade de registros que a página contém e inserir o elemento em uma página já existente para a propriedade ser obedecida.
Inserir uma chave em uma árvore B é significativamente mais complicado que inserir uma chave em uma árvore de pesquisa binária. [...] Não podemossimplesmente criar um novo nó de folha e inseri-lo, pois a árvore resultante deixaria de ser uma árvore B válida. (CORMEN; et al, 2002, p. 356).

Caso1: a página não está cheia, apenas é inserido o registro na página e realiza a movimentação dos outros registros se necessário, a inserção fica limitada àquela página. Poderá ser visto nas imagens 3.1 e 3.2. Inserindo o número 15:

Figura 3.1: Árvore...
tracking img