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

Árvore B – Número máximo de nós visitados

Gabarito: letra B (5 nós). Em uma árvore B de ordem d (d=8), o pior caso de altura (máximo de nós visitados) ocorre quando cada nó tem o mínimo de chaves permitido: a raiz com 1 chave (2 filhos) e os demais nós com d chaves (d+1 filhos). A fórmula do número mínimo de chaves para uma altura h (arestas) é n_min = 2·(d+1)^h – 1. Resolvendo para 30.000 chaves, encontra-se h=4 (arestas), o que significa 5 nós no caminho (raiz + 4 níveis).

O raciocínio baseia-se na definição de árvore B apresentada: cada nó que não a raiz possui entre d e 2d chaves, e a raiz pode ter de 1 a 2d chaves. Para maximizar a altura, utilizamos o menor número de chaves por nó.

Vamos calcular: com d=8, cada nó não raiz tem no mínimo 8 chaves e, portanto, no mínimo 9 filhos (pois filhos = chaves+1). A raiz tem no mínimo 1 chave e 2 filhos. O número mínimo de chaves em uma árvore de altura h (arestas) é dado por:

n_min(h) = 1 + 2·8·(1 + 9 + 9² + … + 9^(h-1)) = 1 + 16·( (9^h – 1)/8 ) = 2·9^h – 1.

Agora, para n=30.000, encontramos o maior h tal que n_min(h) ≤ 30.000:

• h=4 → n_min(4) = 2·6561 – 1 = 13121 ≤ 30000

• h=5 → n_min(5) = 2·59049 – 1 = 118097 > 30000

Portanto, a altura máxima (arestas) é h=4, o que corresponde a um caminho com 5 nós (raiz, nível 1, nível 2, nível 3, folha no nível 4). Logo, o número máximo de nós visitados é 5.

Alternativa A — ❌ Incorreta

A opção 3 nós é muito baixa para armazenar 30.000 chaves nessa configuração; seria necessário um fator de ramificação muito maior ou uma árvore quase cheia.

Alternativa B — ✅ Correta ⟵ GABARITO

Conforme demonstrado, o pior caso resulta em 5 nós visitados (altura 4 arestas).

Alternativa C — ❌ Incorreta

7 nós corresponderia a altura 6 arestas, mas mesmo com o mínimo de chaves por nó, a árvore já comporta mais de 118.000 chaves nessa altura, muito acima das 30.000 – portanto não é o máximo.

Alternativa D — ❌ Incorreta

15 nós é excessivo; seria necessário uma árvore muito mais esparsa, o que não é possível pois o mínimo de chaves por nó já determina limites superiores de altura.

Alternativa E — ❌ Incorreta

15.000 nós é um valor absurdo – a árvore B é balanceada e a altura cresce logaritmicamente, não linearmente.

Gabarito: letra B.