Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvore Multidirecional Remoção, . - Coggle Diagram
Árvore Multidirecional Remoção
Eliminação da chave pode ser feitas de muitas maneiras.
Substituição da chave pela sucessora. (Se estiver em um nó não folha)
Não poderá fica menor que (n-1)/2
Verificar se um dos dois irmãos desse nó contém um número de chaves pelos menos uma unidade a mais do que o valor mínimo de chaves.
Se os dois irmãos estiverem com o numero mínio de nós, então deve-se concatenar ou consolidar o nó que perdeu uma das chaves com um de seus irmão.
Compactação de nó. (Se estiver em um nó folha)
Verificar se o elemento a ser removido se encontra em uma folha.
Se o nó continua com o numero mínimo de elementos.
Aplicar o procedimento de buscar.
Não pode ocorrer concatenação no nó pai.
Algoritmo de remoção.
Se o elemento a ser removido não se encontrar em uma folha é substituído pelo elemento imediatamente maior ou imediatamente menor.
Se o nó continuar com o número mínimo de elementos, fim.
Se o elemento a ser removido se encontrar em uma folha, o elemento é simplesmente retirado.
Se não, a folha obrigatoriamente tem uma chave a menos que o mínimo.Assim verifique os nós irmãos
5.1 Se um dos nós irmãos tiver mais do que o número mínimo de
elementos, aplique redistribuição.
5.2 Se não, concatene o nó com um dos irmãos e o elemento separador do pai.
Aplicar o procedimento de buscar, verificando a existência do elemento a ser removido na árvore
Se ocorrer concatenação, volte ao passo 4 com o nó pai, porque remover um elemento do pai pode acarretar de o pai não ter mais o número mínimo de elementos.
Caso 1: Remoção de uma chave em um nó folha sem causar underflow .
Situação mais simples possível.
Eliminar a chave da página.
Rearranjar as chaves remanescentes dentro
da página para fechar o espaço liberado.
Caso 2: Remoção de uma chave em um nó não
folha
Trocar a chave a ser removida com a sua
chave sucessora imediata.
Remover a chave diretamente do nó folha.
Sempre remover chaves somente nas folhas.
Caso 3: Remoção de uma chave em um nó causando underflow.
Procurar uma página irmã adjacente que contenha mais chaves do que o mínimo.
Reacomodar a chave separadora, modificando o
conteúdo do nó pai.
Redistribuir as chaves entre as páginas.
Caso 4: Remoção de uma chave em um nó, causando underflow e a redistribuição não pode ser aplicada
Combinar para formar uma nova página.
O conteúdo de um nó irmão adjacente.
A chave separadora no nó pai.
O conteúdo do nó que sofreu underflow.
Tratar o underflow no nó pai, caso necessário.
Concatenação
Pode causar underflow no nó pai.
Concatenação pode ser propagada em direção ao nó raiz.
Reverte a promoção de uma chave.
Caso 5: Underflow no nó pai causado pela
remoção de uma chave em um nó filho.
Utilizar redistribuição ou concatenação, dependendo da quantidade de chaves que a página irmã adjacente contém
Caso 6: Diminuição da altura da árvore
A chave é absorvida pela concatenação de
seus nós filhos.
Elimina a raiz antiga.
O nó raiz possui uma única chave.
Tornar o nó resultante da concatenação dos
nós filhos a nova raiz da árvore.
Underflow
Ocorre quando o número de chaves em uma página fica abaixo do número mínimo de chaves permitido.
.