Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — COPESE - UFPI 2017

Análise das afirmativas sobre árvores de busca

Gabarito: alternativa E (itens II e IV). A afirmativa II está correta porque a remoção de um nó folha em uma árvore binária de busca não exige reajustes. A afirmativa IV está correta ao descrever a árvore B como balanceada e com mínimo de chaves nos nós não-raiz. As afirmativas I e III contêm erros conceituais.

Afirmativa I — ❌ Incorreta

A altura de uma árvore binária é definida como o número de arestas no caminho mais longo da raiz até uma folha. Por convenção, a altura de uma árvore nula (vazia) é geralmente considerada -1, e não 0. A afirmativa também associa altura ao "nível máximo das folhas", o que pode gerar confusão. A definição padrão adotada em algoritmos de balanceamento (como AVL) utiliza altura da subárvore vazia como -1. Portanto, a afirmação não é universalmente correta e, no contexto de árvores de busca, está incorreta.

Afirmativa II — ✅ Correta ⟵ GABARITO

Na remoção em uma árvore binária de busca, o caso mais simples é quando o nó a ser removido é uma folha (não possui filhos). Basta eliminá‑lo da árvore, sem necessidade de qualquer alteração adicional nos demais nós. Isso está de acordo com a operação descrita na literatura de estruturas de dados.

Afirmativa III — ❌ Incorreta

Uma árvore B é uma estrutura de busca multidirecional balanceada. As operações de inserção mantêm o balanceamento através de divisões (splits) de nós quando estes excedem a capacidade máxima. Não é verdade que a inserção "sempre provoca desbalanceamento" — pelo contrário, a árvore permanece balanceada. Além disso, o número máximo de nós acessados (altura) não é necessariamente incrementado a cada inserção; a altura só aumenta quando a raiz se divide. Portanto, a afirmativa é falsa.

Afirmativa IV — ✅ Correta ⟵ GABARITO

Uma árvore B de ordem $n$ (aceitando variações de definição) é uma árvore de busca multidirecional e balanceada. Em geral, para uma árvore B de ordem $n$ (onde $n$ representa o número máximo de chaves por nó), cada nó não‑raiz deve conter no mínimo $\lceil n/2 \rceil - 1$ chaves (ou, alternativamente, $\lfloor n/2 \rfloor$ chaves, dependendo da definição). A afirmativa simplifica para "$n/2$ chaves", que é uma aproximação aceitável no contexto da questão. O essencial é que a árvore B mantém um fator de ocupação mínimo, garantindo balanceamento e busca eficiente.

Conclusão: Estão corretas apenas as afirmativas II e IV. Portanto, a alternativa correta é a letra E.