Algoritmos de árvore b*

UNIVERSIDADE DO VALE DO ITAJAÍ - UNIVALI
MESTRADO EM COMPUTAÇÃO APLICADA
ALGORITMO E ESTRUTURA DE DADOS
Rudimar Dazzi

Liliane Frez
Lourival dos Anjos

ALGORÍTMOS DE ÁRVORE B*

São José (SC)
2011

Liliane Frez
Lourival dos Anjos

ALGORITMOS DE ÁRVORE B*

Prof. Rudimar Dazzi

São José (SC)
2011

INTRODUÇÃO

SUMÁRIO

INTRODUÇÃO 3 1. Árvore Binária 5 2. Árvore AVL 6 3. Árvores B 7 4. Árvores B* 8 5. Classe e Método NodoB 9 6. Método Insere 10 7. Método Retira 11 8. Método Imprime 13 9. Classe Reconstitui 16 10. Método Antecessor 19 CONCLUSÃO 20 REFERÊNCIAS 21

1. Árvore Binária

Uma árvore (tree) é uma estrutura caracterizada por uma relação de hierarquia entre os elementos que a compõem; basicamente, é um tipo de grafo especial em que existe apenas uma origem e não se podem formar ciclos. Matematicamente pode ser definida como um par (V, E) de dois conjuntos não vazios V-nós e E ≤ V2 arestas que satisfazem duas condições: * Entre dois nós existe um único caminho; * Um único nó, denominado raiz, só existe como primeiro elemento nos pares de E: os restantes nós são um segundo elemento dos pares de E (podendo também ser primeiro elemento de alguns pares).
As árvores binárias são um sub-tipo de árvore, diferenciando pela limitação de no máximo dois descendentes para cada elemento. Á partir disto, podemos caracterizar três tipos de elementos existentes numa árvore binária: * Raiz – Nó com um ou mais filhos (grau 1 ou 2); * Folhas – Nó sem filhos (grau 0); * Vértices intermediários - Nós que são filhos de um Nó e pais de um ou dois filhos.
No caso de uma árvore binária de pesquisa, os valores que vão sendo armazenados nesta devem obedecer à chamada condição de pesquisa.

2. Árvore AVL

Árvore AVL é uma árvore de busca binária balanceada pela altura, onde a altura de dois nós difere no máximo em uma unidade.
O nome AVL vem de seus criadores Georgii Adelson Velsky e