Questão de Tecnologia da Informação · FGV STN 2024 (nº 49)

Conceito-chave: A Árvore B é uma estrutura balanceada usada em bancos de dados para indexação, onde o objetivo é manter buscas, inserções e remoções rápidas (em $O(\log n)$), garantindo que todas as folhas fiquem no mesmo nível (balanceamento perfeito) e que cada nó tenha um número limitado de chaves, definido pelo grau $g$.

• (A) Correta: As afirmativas 1 e 2 estão corretas: todas as folhas no mesmo nível é a definição de balanceamento, e o número máximo de chaves por nó é $2g - 1$ (quando o nó está cheio e será dividido).
• (B) Incorreta: A afirmativa 3 está errada, pois o número mínimo de chaves em um nó (exceto raiz) é $g - 1$, e não 3 (o valor 3 só seria verdadeiro se $g = 4$).
• (C) Incorreta: Além do erro da afirmativa 3, a afirmativa 4 está errada: a complexidade de inserção em uma Árvore B é $O(\log n)$, não $O(n^2)$.
• (D) Incorreta: A afirmativa 3 está errada (mínimo é $g-1$, não 3) e a afirmativa 4 está errada ($O(n^2)$ não é a complexidade correta). A afirmativa 5 também está errada, pois a inserção é $O(\log n)$, não $O(n)$.
• (E) Incorreta: A afirmativa 2 está correta, mas as afirmativas 4 e 5 estão erradas: a complexidade de inserção é $O(\log n)$, não $O(n)$ nem $O(n^2)$.

Armadilha da banca (no distrator B): A banca tenta fazer você acreditar que "mínimo de 3 chaves" é uma regra geral, mas isso é falso — o mínimo depende do grau $g$ e é sempre $g - 1$. O valor "3" só valeria se $g = 4$, o que não é informado. Além disso, a pegadinha clássica é confundir a complexidade de inserção com $O(n)$ (como em listas) ou $O(n^2)$ (como em ordenação ingênua), quando na verdade a Árvore B garante $O(\log n)$ para todas as operações, justamente por ser balanceada e ter altura logarítmica.