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

Árvores B: Definição de Ordem e Particionamento

Gabarito: letra A. A única alternativa que mantém a relação correta de que o número de descendentes é sempre igual ao número de registros mais um (para nós internos) e que as demais grandezas (mínimo, máximo, faixa da raiz) são consistentes com a definição clássica de uma Árvore B de ordem m (considerando m como o número mínimo de registros por nó, exceto raiz). Nessa interpretação, cada nó (exceto raiz) tem no mínimo m registros e m+1 descendentes, no máximo 2m registros e 2m+1 descendentes; a raiz pode ter entre 1 e 2m registros; e o particionamento (split) ocorre quando se tenta inserir em um nó já com 2m registros (isto é, nó cheio).

A banca testa o conhecimento das propriedades fundamentais de uma Árvore B. A definição variante adotada nesta questão é a que associa o parâmetro m ao número mínimo de registros por nó (exceto raiz). As demais alternativas quebram a relação obrigatória entre registros e descendentes ou apresentam valores inconsistentes.

Alternativa A — ✅ Correta ⟵ GABARITO

Segue a definição padrão com a relação registros + 1 = descendentes:

• Mínimo: m registros e m+1 descendentes.

• Máximo: 2m registros e 2m+1 descendentes.

• Raiz: entre 1 e 2m registros (se não for folha, também segue a regra de descendentes).

• Split: ocorre quando um nó já contém 2m registros (atingiu o máximo) e uma nova inserção é tentada, gerando um overflow que força a divisão do nó.

Alternativa B — ❌ Incorreta

Apresenta mínimo de descendentes como m-1, que é menor que o mínimo de registros (m). Isso viola a propriedade de que o número de ponteiros (descendentes) em um nó interno deve ser exatamente o número de registros mais um (para acomodar os intervalos). Além disso, os valores máximos (2m registros, 2m+2 descendentes) e o número de split (6m) não são coerentes com a definição usual.

Alternativa C — ❌ Incorreta

Mínimo de registros m-1 com mínimo de descendentes m (relação correta aqui), mas o máximo de descendentes é 4m+2, que é dois a mais que o máximo de registros (4m). Em uma Árvore B, essa diferença deve ser exatamente 1. A faixa da raiz (1 a 4m) e o split (4m) também não se alinham com a relação padrão.

Alternativa D — ❌ Incorreta

Mínimo m-2 registros e m descendentes (diferença de 2). Máximo 8m registros e 8m+2 descendentes (diferença de 2). Raiz entre 1 e 6m, split em 6m – valores arbitrários e sem correspondência com a definição.

Alternativa E — ❌ Incorreta

Mínimo m-3 registros e m descendentes (diferença de 3). Máximo 3m registros e 4m+2 descendentes (diferença de m+2, completamente fora do padrão). A faixa da raiz (1 a 4m) e split (4m) também inconsistentes.

Gabarito: letra A