Arvores multiplas, árvore b

ESTRUTURA DE DADOS
Prof. Dr. Carlos Estombelo-Montesco

1

Lembram
Arvore ? Arvore binária ? Árvore binária de busca ? Árvores AVL ?

2

1

Árvores Múltiplas
Definição geral de árvore ... A definição considerou:
Uma estrutura vazia ou Como uma estrutura cujos filhos são árvores diferentes (disjuntas) t1, ..., tk. Portanto nesta definição cada nó:
Pode ter mais de dois filhos

Este tipo de árvore é chamada de
Árvore múltipla de ordem “m” ou árvore “mária”
3

Árvores Múltiplas
Nas árvores múltiplas
Cada NÓ pode ter mais de uma chave ! e estas chaves (agrupadas em um nó) dispostas em uma seqüência ordenada

4

2

Árvores Múltiplas
Árvore de busca múltipla de ordem “m”
1. 2. 3.

Cada nó tem “m” filhos e m-1 chaves As chaves em cada um dos nós estão em ordem ascendente As chaves que estão dentro do primeiro filho “i1”, são menores do que as chaves que estão no “i-ésimo” filho

4.

As chaves que estão dentro do último filho “im”, são maiores do que as chaves que estão no “i-ésimo” filho.
5

Árvores Múltiplas
Árvore de busca múltipla de ordem “m”
Árvore quaternária

Portanto: ordem = Nro máximo de filhos que um nó poderia ter.
6

3

Árvores Múltiplas
Árvores m-árias Desempenham o Mesmo papel, Mesmo propósito Árvores binárias

Árvores de busca m-árias

Árvores binárias busca

7

Árvores Múltiplas
Árvores m-árias Desempenham o Mesmo papel, Mesmo propósito Árvores binárias

Árvores de busca m-árias

Árvores binárias busca

Rápida recuperação e atualização de informação

8

4

Árvores Múltiplas
Árvore de busca múltipla de ordem “m”
Árvore quaternária

35 esta no segundo nó testado 55 está no quinto nó testado
9

Árvores Múltiplas
Árvore de busca múltipla de ordem “m”
Árvore quaternária

Problema: • Desbalanceamento !! Armazenamento secundário

35 esta no segundo nó testado 55 está no quinto nó testado
10

5

Acesso ao disco, blocos e nós
Unidade básica de operação E/S
Disco: