Árvore multidirecional de busca

images

Folha

Semi Folha

Balanceada

Top Down

Uma chave a menos

N ou menos subárvore

click to edit

Árvores B Arvore b

Árvore Balanceada

Folhas se encontrem todas em um mesmo nível

Armazenamento de grande quantidade de dados

A raiz tem no mínimo duas e no máximo n subárvores

Todos os nós externos estão no mesmo nível.

Busca

Buscar a folha na qual será inserido o novo elemento.

Verificar se a folha está ou não completa

Definição enquanto à ordem da árvore

Se o nó estiver cheio deve dividi-lo ao meio

Se a raiz estourar cria-se uma nova

Remoção

Verificar se o elemento a ser removido se encontrar em uma folha

Se o nó continua com o número mínimo de elementos

Não pode ocorrer concatenação no nó pai

Aplicar o procedimento de buscar

Inserção

Se o nó estiver completo se cria outro

Se possuir espaço a chave é inserida

Encontra o nó folha

Árvores B*

click to edit

Quando um nó e seu irmão estiverem completos serão dividos em 3

Retarda divisão em um nó

Árvore B+

Chaves são percorridas sequencialmente

Todas as chaves são ligadas entre si

Forma uma ista encadeada

Testes a cada nó

Árvore binária de busca

Eficiência

Sempre ocupara o espaço de armazenamento total

Não possui numero mínimo de chaves

Tempo de Busca calcula-se pelo numero de nó acessados