Buscar

16_Arvore B

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 17 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 17 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 17 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
1
Árvores B
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estrutura de Dados e 
Algoritmos
Introdução
2
� Rudolf Bayer, Binary B-Trees for 
Virtual Memory, ACM-SIGFIDET 
Workshop 1971, San Diego, California, 
Session 5B, p. 219-235 
� Motivação
� Custo alto de acesso a memória 
secundária
� A leitura de uma página (nó) é cara em 
I/O
� Solução
� Aumentou o número de chaves em cada 
nó (página)
2
Ideia
3
Árvore B
4
� Características
� Ela é uma árvore balanceada
� Todas as folhas estão no último nível
� Possui um número máximo de filhos que cada nó pode 
ter (ordem)
� Nó de uma árvore B são chamados de páginas 
(guardam mais de 1 elemento)
3
Árvore B
5
� Propriedades (árvore B de ordem m)
� Cada nó tem no máximo m filhos
� Cada nó interno (diferente de raiz e de folha) tem no 
mínimo m/2 filhos
� A raiz tem pelo menos 2 filhos se não for folha.
� Todas as folhas estão no mesmo nível e não têm filhos
� Um nó interno com k filhos possui k-1 elementos.
� Os elementos de cada nó estão ordenados e servem
como separadores dos filhos.
Árvore B
6
� Propriedades (árvore B de ordem m)
� Cada nó tem no máximo m filhos
� Cada nó interno (diferente de raiz e de folha) tem no 
mínimo m/2 filhos
� A raiz tem pelo menos 2 filhos se nao for folha.
� Todas as folhas estão no mesmo nível e nao tem filhos
� Um nó interno com k filhos possui k-1 elementos.
� Os elementos de cada nó estão ordenados e servem
como separadores dos filhos.
4
Exemplo (ordem 3)
7
Nó com mais 
de uma chave, 
ordenada
balanceada
5 10
3 4 6 8 11 13 14
12
17
15
raiz
Estrutura de um nó
8
public class BNode<T extends Comparable<T>> {
}
}
5
Estrutura de um nó
9
public class BNode<T extends Comparable<T>> {
LinkedList<T> elements;
LinkedList<BNode<T>> children;
BNode<T> parent;
int maxKeys;
int maxChildren;
public BNode(int order){
this.maxChildren = order;
this.maxKeys = order - 1;
this.elements = new LinkedList<T>();
this.children = new LinkedList<BNode<T>>();
}
}
Estrutura de um nó
10
public class BNode<T extends Comparable<T>> {
public boolean equals(Object obj) {
boolean resp = false;
return resp;
}
6
Estrutura de um nó
11
public class BNode<T extends Comparable<T>> {
public boolean equals(Object obj) {
boolean resp = false;
if(obj != null){
if(obj instanceof BNode){
if(this.size() == ((BNode<T>)obj).size()){
resp = true;
int i = 0;
while(i<this.size() && resp){
resp = resp && this.getElementAt(i).
equals(((BNode<T>) obj).getElementAt(i));
i++;
}
}
}
}
return resp;
}
Interface da árvore B
12
public interface BTree<T extends Comparable<T>> {
BNode<T> getRoot();
boolean isEmpty();
int height();
BNodePosition<T> search(T element);
void insert(T element);
BNode<T> maximum(BNode<T> node);
BNode<T> minimum(BNode<T> node);
void remove(T element);
int size();
}
7
Interface da árvore B
13
public interface BTree<T extends Comparable<T>> {
BNode<T> getRoot();
boolean isEmpty();
int height();
BNodePosition<T> search(T element);
void insert(T element);
BNode<T> maximum(BNode<T> node);
BNode<T> minimum(BNode<T> node);
void remove(T element);
int size();
}
O retorno é o nó contendo o 
elemento e a posição do 
elemento nele 
(BNode, Position)
Pesquisa
14
public class BNodePosition<T extends Comparable<T>> {
BNode<T> node;
int position;
public BNodePosition(BNode<T> node, int position) {
this.node = node;
this.position = position;
}
public BNodePosition() {
}
}
8
Pesquisa
15
� A ideia é similar à pesquisa em BST
� Diferença
� Um nó pode ter mais de uma chave
� Dentro do nó fazemos uma pesquisa linear
� Procura se o elemento está no nó
� Se não estiver, então procura na sub-árvore cujos 
separadores são x1 e x2 tal que x1 < valor procurado < x2.
� Pode acontecer variações: 
� valor procurado < x1: valor procurado é menor que o menor 
elemento
� x2 < valor procurado: valor procurado é maior que maior 
elemento procurado
� O retorno é o nó contendo o elemento e a posição do 
elemento nele (BNode, Position)
Pesquisa (exemplo)
16
� Pesquisa do nó 8
5 10
3 4 6 8 11 13 14
12
17
15
raiz
9
Pesquisa (exemplo)
17
� Pesquise pelas chaves 14, 7, 17
5 10
3 4 6 8 11 13 14
12
17
15
Pesquisa
18
B-TREE-SEARCH(BNode x, K k)
i ← 1
while i ≤ x.size and k > x.keys[i]
i ← i + 1
if i ≤ x.size and k = x.keys[i]
return (x, i)
if x.leaf
return (null,null)
return B-TREE-SEARCH(x.children[i], k)
10
Inserções 
19
� Acontecem sempre nas folhas
� Algoritmo localiza a folha conveniente para fazer a 
inserção
� Se o nó folha não está cheio então o elemento será 
inserido nele em ordem
� Se o nó folha está cheio
� Faça o split (divisão) do nó. Um elemento vai subir.
� Faça o promote (promoção) do elemento a subir na 
árvore
� Se o pai estiver cheio faz o split e promote no pai 
Inserções 
20
� Split
� Escolha o elemento médio (mediana de separação) dos 
elementos do nó (já considerando o novo elemento 
inserido)
� Valores menores que a mediana são colocados em um 
novo nó folha (esquerdo) e valores maiores são 
colocados em um outro novo nó folha (direito)
� A mediana é inserida como novo elemento do pai (isso 
pode causar um split no pai)
� Filhos da mediana contêm os demais elementos do 
antigo nó;
� Um split na raiz origina uma nova raiz.
11
Inserções (exemplo | m=3) 
21
Inserções (exemplo | m=4) 
22
12
Inserções (exemplo | m=4) 
23
Remoções
24
� É análoga à inserção, porém com alguns 
complicadores, visto que uma chave pode ser 
removida de qualquer nó.
� Assim como na inserção, precisamos garantir que, 
ao removermos a chave as propriedades da árvore-
B não sejam violadas.
� Duas operações podem ser necessárias:
� Concatenação;
� Redistribuição.
13
Remoções
25
� Pontos a se considerar:
� O elemento removido em um nó interno pode ser 
separador de seus nós filhos. 
� Deletar um elemento pode deixar o nó com número de 
elementos e filhos menor que o mínimo exigido. 
� 2 Casos:
� O elemento pertence a uma folha;
� O elemento pertence a um nó interno;
Remoções (Nó Interno)
26
� Chave x não está em uma folha: 
� x é substituída por y:
� a menor chave em uma folha tal que y é maior que x 
(sucessor); ou
� a maior chave em uma folha tal que y é menor que x 
(predecessor);
Portanto, é suficiente fazer análise da remoção em 
uma folha!
(mais adiante veremos ilustrações de remoções de 
nós internos)
14
Remoções (Elemento em uma folha)
27
� Remove o elemento do nó folha.
� Se acontece underflow, verifique os irmãos e 
transfira uma chave ou então faça a fusão do nó
com um irmão.
� Se a deleção acontece no filho da direita transfira o valor 
máximo do filho da esquerda para o pai se não
acontecer underflow no filho da esquerda (depois desça a 
penúltima chave do pai para o filho).
� O caso simétrico é análogo (com filho à esquerda);
� Se não for possível usar elementos de algum irmão
então faça junção de irmãos usando valores do pai
Remoções (Elemento em uma folha)
28
� Não acontece underflow (ordem 5)
>>>>> Buscando 50 >>>>
50 removido!>>>>> Buscando 50 >>>>
15
Remoções (Elemento em uma folha)
29
� Acontece underflow
>>>>>>>>> Redistribuição >>>>>>>>>
>>>>> Buscando 29 >>>>
29 removido!
Remoções (Elemento em uma folha)
30
� Acontece underflow
Concatenação
>>>>>> Redistribuição >>>>>>
>>>>>>>>>>>> Buscando 22 >>>>>>>>>>>>
22 removido! >>>>>>> Buscando 47 >>>>>>
47 removido!
16
Remoções (Elemento em umafolha)
31
� Acontece underflow
Concatenação
>>>>>>>>> Buscando 74 >>>>>>>>> 74 removido!
Remoções (Elemento em um nó interno)
32
� Escolhe um novo separador (sucessor/predecessor – em uma folha)
� Ajusta o nó que teve o elemento removido, como visto 
anteriormente.
>>>> Substituído pelo sucessor (20) >>>>
>>> Removendo o 15 >>>
17
Remoções (Elemento em um nó interno)
33
� Escolhe um novo separador (sucessor/predecessor – em uma folha)
� Ajusta o nó que teve o elemento removido, como visto 
anteriormente.
>>>> Concatenando >>>>
>>> Concatenando >>>
Referências
34
� Capítulo 19
� 1a edição

Outros materiais