Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024

Árvore B: Propriedades e Complexidade

Gabarito: letra A. Apenas as afirmativas 1 e 2 estão corretas. Em uma Árvore B de grau g (mínimo de chaves por nó), todas as folhas estão no mesmo nível (propriedade de balanceamento) e o número máximo de chaves por nó é 2g−1. As demais afirmativas erram o mínimo de chaves (não é 3, mas g−1) e a complexidade da inserção (não é O(n²) nem O(n), mas O(log N)).

A banca testa o conhecimento das definições clássicas da Árvore B, estrutura balanceada usada em índices de bancos de dados relacionais.

Afirmativa 1 — ✅ Correta

"Todas as folhas estão no mesmo nível de profundidade na árvore." Essa é uma propriedade fundamental: a Árvore B é balanceada por altura, garantindo que todas as folhas estejam na mesma profundidade, o que assegura complexidade logarítmica para operações.

Afirmativa 2 — ✅ Correta

"Todos os nós podem conter, no máximo, 2g - 1 chaves." Correto. Em uma Árvore B de grau g (minimum degree), cada nó pode conter no máximo 2g−1 chaves. O número máximo de filhos é 2g.

Afirmativa 3 — ❌ Incorreta

"Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, 3 chaves." Errado. O número mínimo de chaves em nós não raiz é g−1, não 3. A raiz pode ter a partir de 1 chave. O valor 3 seria válido apenas se g=4, mas o grau g não é fixado.

Afirmativa 4 — ❌ Incorreta

"Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n²)." Errado. A altura da Árvore B é O(log N) (na base do fator de ramificação), portanto a inserção tem complexidade O(log N), não quadrática.

Afirmativa 5 — ❌ Incorreta

"Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n)." Errado. Novamente, a complexidade é O(log N), não linear.

Conclusão: As afirmativas 1 e 2 estão corretas; as demais, incorretas. Portanto, a alternativa que reúne apenas as corretas é a letra A (1 e 2).