Aula Arvore B - Exclusão na Arvore B, Btree, exclusão.

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Definição de Árvore B:
Segundo (Ziviani, 2002), uma Árvore B de ordem m* é tal que:
Cada página possui, no mínimo m registros (e m+1 descendentes) e no máximo 2m registros (e 2m+1 descendentes), exceto a página raiz, que pode conter entre 1 e 2m registros;
Todas as páginas folha aparecem no mesmo nível.
* Diverge de outras definições.
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Operação de remoção:
Caso trivial 1:
Quando o registro a ser removido estiver em uma página folha com pelo menos m+1 registros;
Quando o registro a ser removido não estiver numa página folha:
Substitui-se o registro por um que contenha uma chave adjacente (antecessora ou sucessora);
Caso trivial 2:
Quando o substituo estiver originalmente em uma página com, pelo menos, m+1 registros;
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Exemplo (caso trivial 2)
Remover o registro com chave 43 da seguinte árvore:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
E quando, após uma remoção, uma página fica com menos de m registros?
Neste caso uma propriedade da Árvore B é violada;
Com isto, é necessário tomar emprestado um registro da página vizinha;
Nesta situação, duas coisas podem ocorrer:
O número de registros da página vizinha é maior que m. Assim, basta tomar um registro emprestado e trazê-lo para a página em questão via página pai.
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Exemplo
Remover o registro com chave 33 da seguinte árvore:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
A segunda possibilidade é a de que a página vizinha também tenha exatamente m registros (neste caso as duas juntas têm 2m-1 registros);
Nesta situação as duas páginas devem ser fundidas em uma só;
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Exemplo: remoção do registro com chave 41 da seguinte árvore:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Observe que, dependendo do contexto, o processo pode se propagar até a raiz;
Exemplo: remover o registro com chave 41 da seguinte árvore:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Etapa 1:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Etapa 2:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Resultado:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Eliminação de uma chave em Árvore B:
1. Se a chave não estiver numa folha, troque-a com seu sucessor imediato.
2. Elimine a chave da folha.
3. Se a folha continuar com o número mínimo de chaves, fim.
4. A folha tem uma chave a menos que o mínimo. Verifique as páginas irmãs da esquerda e direita:
4.1.se uma delas tiver mais que o número mínimo de chaves, aplique redistribuição.
4.2.senão concatene a página com uma das irmãs e a chave pai.
5. Se ocorreu concatenação, aplique passos de 3 a 6 para a página pai.
6. Se a última chave da raiz for removida, a altura da árvore diminui.
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Exercício:
Dada a seguinte Árvore B, descreva o estado da mesma após realizar a remoção dos registros com seguintes seqüências de chave;
45, 30 e 28;
50, 8, 10, 4, 20, 40, 55, 17, 33, 11 e 36;
3, 9 e 52.
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Soluções possíveis:
*
*
*
Prof. Yandre Maldonado
Busca em Memória Secundária
Referências Bibliográficas:
Cormen, Thomas H. et al. Algoritmos – teoria e prática. Rio de Janeiro: Elsevier, 2002;
Drozdek, Adam. Estrutura de Dados e Algoritmos em C++. São Paulo: Pioneira Thomsom Learning, 2002;
Ziviani, Nivio. Projeto de Algoritmos – com implementações em Pascal e C. São Paulo: Pioneira Thomsom Learning, 2002;