A2 TADS4 Estrutura De Dados Teleaula 7 Tema 7 Impressao
1814 palavras
8 páginas
19/09/2014Estrutura de Dados
Tema 7: Árvore Multidirecional (Árvore B.)
O que é uma árvore B
Definida por Rudolf Bayer em 1971 no Boeing
Scientific Research Labs.
Sua definição foi motivada pela necessidade de diminuir o tempo de acesso a dados armazenados em memória secundária. O tempo de acesso à memória secundária ainda hoje é bem maior que o tempo de acesso à memória principal.
O que é uma árvore B
Árvore B é multidirecional balanceada.
Multidirecional cada nó (ou página) pode armazenar várias k chave (ou elementos) e, assim, apontar para k+1 filhos, onde k ≥ 1.
Balanceada todas as folhas estão no mesmo nível.
1
19/09/2014
Características de uma árvore B
Raiz: o nó inicial da árvore;
Grau: o número de filhos que um nó possui;
Nível (ou profundidade): a distância de um nó até a raiz;
Altura: o maior nível encontrado na árvore. A altura de uma árvore B com n nós é sempre lg(n);
Folha: o nó que não possui filho. Características de uma árvore B
Ordem: quantidade máxima de filhos que um nó pode conter.
Se a árvore tem ordem n:
poderá ter até n-1 chaves k1, ..., kn em cada nó.
as chaves dentro de um nó ficam ordenadas. Assim, k1 ≤ k2 ≤ ... ≤ kn-1.
cada nó poderá ter no máximo n filhos.
todo nó que possua t chaves
(t ≤ n-1) terá t+1 filhos.
Exemplo de árvore de ordem 3
Raiz
E
Folha
A
D
M
J
G
S
P
L
O
Q
X
R
T
V
Z
Altura da árvore é 2
Todos as folhas estão no mesmo nível.
Qtd. máxima de chaves: 3-1
Qtd. mínima de chaves:
3 1
2
2
19/09/2014
Organização das chaves
Seja k uma chave pertencente a um nó não folha de uma árvore. Podemos afirmar que:
na sub-árvore à esquerda de k só existirão chaves menores ou iguais a k;
na sub-árvore à direita de k só existirão chaves maiores que k.
Organização das chaves
30
10 21
5
8
15 17
60
45
26
32
75
44 53
62
88 95
Buscar uma chave x em uma Árvore B de ordem n k1 p1
p2
k2
k3
p3
...
p4
Kn-2
pn-2
Kn-1
pn-1
pn
3
19/09/2014
Buscar uma chave x em uma