Considere a seguinte B-tree onde t = 3 (fator de ramificação). Qual das seguintes árvores é o resultado da inserção de B?

Alternativa A

A questão solicita o resultado da inserção da chave B em uma árvore B com grau mínimo t=3. Para resolver, devemos seguir o algoritmo padrão de inserção em árvores B, considerando as regras de balanceamento.

Regras da Árvore B (t=3)

Para um grau mínimo t=3, cada nó deve obedecer às seguintes restrições:

• Chaves Mínimas: t - 1 = 2 chaves (exceto a raiz).
• Chaves Máximas: $2t - 1 = 5$ chaves.
• Filhos: Se um nó tem n chaves, ele tem n+1 filhos.

Passo a Passo da Inserção

1. Verificação da Raiz Atual
A raiz atual contém as chaves {D, G, K, N, V}.

• Total de chaves: 5.
• Capacidade máxima permitida: 5.
• Conclusão: A raiz está cheia (overflow). Antes de inserir qualquer novo valor, é necessário dividir a raiz.

2. Divisão da Raiz
Quando a raiz está cheia, sua chave mediana é promovida para criar uma nova raiz.

• Chaves ordenadas: D, G, K, N, V.
• Mediana: K.
• Nova Estrutura:
• Nova Raiz: Contém apenas K.
• Subárvore Esquerda: Recebe chaves menores que K (D, G).
• Subárvore Direita: Recebe chaves maiores que K (N, V).
• Redistribuição dos Filhos:
• Os filhos originais antes de K (AC, EF, HI) passam a pertencer ao filho esquerdo (DG).
• Os filhos originais depois de K (LM, OPRST, WX) passam a pertencer ao filho direito (NV).

3. Inserção da Chave B
Agora que a raiz não está cheia, procuramos onde inserir B.

• Comparação com Raiz K: B < K, então descemos para a subárvore esquerda (DG).
• Comparação com DG: B < D, então descemos para o primeiro filho (AC).
• Inserção: A chave B é inserida na folha AC.
• Ordem crescente: A, B, C.
• Novo nó folha: {A, B, C}.
• Como este nó agora tem 3 chaves (máximo 5), ele não precisa ser dividido.

Análise das Opções Visuais

Comparando nossa estrutura deduzida com as imagens fornecidas:

• Raiz: Deve ser K. (Elimina V, pois raiz é N).
• Esquerda: Nó DG com filhos ABC, EF, HI.
• Direita: Nó NV com filhos LM, OPRST, WX.

Vamos verificar a imagem II:

• Raiz: K.
• Filho Esquerdo: DG com folhas ABC, EF, HI.
• Filho Direito: NV com folhas LM, OPRST, WX.
• Correspondência: Perfeita.

As outras imagens estão incorretas:

• I: O nó DG teria 4 filhos (ABC, EF, HI, LM), o que viola a regra ($2$ chaves exigem no máximo $3$ filhos). Além disso, LM deveria estar à direita de K.
• III e IV: Apresentam combinações de chaves nas folhas (BEF, AC separado) que não correspondem à inserção correta de B na folha AC.
• V: Raiz alterada para N, o que indica um pivô errado na divisão inicial.

Portanto, a única árvore correta é a apresentada na figura II, que corresponde à opção a.

Alternativa A