Questão de Tecnologia da Informação · FGV CMSP 2024 (nº 58)

Árvores B são estruturas de dados balanceadas, otimizadas para armazenamento em disco, onde cada nó pode conter muitas chaves e ponteiros, minimizando acessos ao disco. O grau mínimo d (ou ordem $m = 2d$) de uma árvore B define as regras de preenchimento dos nós.

(A) Incorreta: A afirmação "Todo nó possui no máximo d - 1 chaves" está errada. Um nó de uma árvore B de grau mínimo d pode ter no máximo $2d - 1$chaves. Se tivesse apenas$d - 1 chaves como máximo, a árvore seria muito esparsa. **(B) Incorreta:** A afirmação "Todo nó, exceto a raiz, possui pelo menos 2d - 1 chaves" está errada. \2d - 1$é o *número máximo* de chaves que um nó pode ter. O número *mínimo* de chaves para um nó não-raiz é$d - 1$. Esta é uma pegadinha comum, confundindo o máximo com o mínimo. **(C) Incorreta:** Incorreta porque a alternativa I está incorreta. **(D) Correta:** Esta afirmação é totalmente correta. * "A raiz possui pelo menos 1 chave e 2 filhos": Se a árvore B não está vazia e a raiz não é uma folha (ou seja, a árvore tem mais de um nó), a raiz deve ter pelo menos 1 chave, o que implica em ter pelo menos 2 filhos (ponteiros). * "e um nó não-folha com k ponteiros contém k - 1 chaves": Esta é uma propriedade fundamental das árvores B (e de muitas outras árvores de busca). As chaves em um nó servem para separar os intervalos de valores apontados pelos seus filhos. Se um nó tem$k$filhos (ponteiros), ele precisa de$k - 1$chaves para definir esses$k$ intervalos.
(E) Incorreta: Incorreta porque a alternativa II está incorreta.