Considerando-se a definição de Knuth, se uma árvore B de ord...

Alternativa correta: C - 8 e 12

Vamos entender a lógica por trás da questão. A questão aborda a inserção de elementos em uma árvore B de ordem 5. Para resolver essa questão, é necessário compreender o funcionamento das árvores B, especialmente como os elementos são organizados e como ocorrem as divisões dos nós.

Uma árvore B de ordem 5 é uma árvore balanceada onde cada nó interno tem no mínimo 2 filhos e no máximo 5 filhos. Cada nó pode armazenar até 4 chaves (pois a ordem é 5, então é k-1, onde k é a ordem).

Começando a inserir os elementos fornecidos (10, 15, 8, 1, 4, 12, 20, 9, 3, 32, 17), a árvore vai crescendo e, quando um nó atinge sua capacidade máxima, ele é dividido. Vamos analisar o processo de inserção:

1. Insira 10: A árvore começa com o nó raiz contendo 10.

2. Insira 15: O nó raiz agora contém 10, 15.

3. Insira 8: O nó raiz contém 8, 10, 15.

4. Insira 1: O nó raiz contém 1, 8, 10, 15.

5. Insira 4: O nó raiz contém 1, 4, 8, 10, 15.

6. Insira 12: O nó raiz não pode conter mais do que 4 chaves, então ele é dividido. O meio (chave 8) sobe e o nó é dividido em dois: [1, 4] e [10, 12, 15]. Assim, a árvore agora tem a raiz contendo 8, com dois filhos.

7. Insira 20: O nó [10, 12, 15] agora contém 10, 12, 15, 20.

8. Insira 9: O nó [10, 12, 15, 20] não pode conter mais do que 4 chaves. Ele é dividido, e a chave 12 sobe, dividindo o nó em [10] e [15, 20]. A árvore agora tem a raiz contendo 8, 12, com três filhos.

9. Insira 3: O nó [1, 4] contém 1, 3, 4.

10. Insira 32: O nó [15, 20] contém 15, 20, 32.

11. Insira 17: O nó [15, 20, 32] agora contém 15, 17, 20, 32.

Assim, a raiz final contém as chaves 8 e 12, com três filhos. Portanto, a alternativa correta é C - 8 e 12.

Justificativa das alternativas incorretas:

A - 12: Não está correta porque a raiz deve conter mais de uma chave após as divisões e inserções.

B - 8 e 10: Não está correta porque, após as divisões e inserções, a raiz não contém a chave 10.

D - 10 e 12: Não está correta porque a raiz contém a chave 8, não 10.

E - 15 e 17: Não está correta porque essas chaves estão em um dos filhos, não na raiz.

Gostou do comentário? Deixe sua avaliação aqui embaixo!