Questão de Banco de Dados — Banco de Dados Hierárquico e em Rede — INSTITUTO AOCP 2024

Árvore binária completa: definição e propriedades

Gabarito: letra A. A alternativa A está correta porque define com precisão o que é uma árvore binária completa: todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós estão o mais à esquerda possível. Essa é a definição clássica de árvore binária completa, que a distingue da árvore binária cheia (ou estritamente binária) e da árvore binária perfeita.

Uma árvore binária é uma estrutura de dados hierárquica em que cada nó tem, no máximo, dois filhos, chamados de filho esquerdo e filho direito. A partir dessa definição básica, surgem variações importantes que as bancas adoram cobrar: a árvore binária cheia (ou estritamente binária), a árvore binária completa e a árvore binária perfeita. A confusão entre esses três conceitos é a pegadinha mais comum nesse tema.

A árvore binária completa é aquela em que todos os níveis estão completamente preenchidos, exceto possivelmente o último, e no último nível todos os nós estão o mais à esquerda possível. Isso significa que, se você numerar os nós de cima para baixo e da esquerda para a direita, não há "buracos" na sequência: um nó só existe se todos os anteriores existirem. Essa propriedade é fundamental para a implementação de estruturas como o heap, que é usado em algoritmos de ordenação e filas de prioridade.

Já a árvore binária cheia (ou estritamente binária) é aquela em que todo nó tem zero ou dois filhos — nunca apenas um. A árvore binária perfeita é aquela em que todos os níveis estão completamente preenchidos, sem exceção. Veja a diferença na prática: uma árvore com 3 níveis, onde o terceiro nível tem apenas 3 nós à esquerda, é completa, mas não é perfeita (pois o último nível não está cheio) e pode não ser cheia (se algum nó do segundo nível tiver apenas um filho).

A banca explora exatamente essa distinção. A alternativa B inverte a direção do preenchimento ("mais à direita possível"), o que não corresponde à definição. A alternativa C descreve a árvore binária perfeita, não a completa. A alternativa D é claramente incorreta, pois uma árvore binária completa pode ter vários níveis completamente preenchidos, não apenas o primeiro.

Guarde a fronteira entre os três tipos: completa (último nível incompleto, mas preenchido à esquerda), cheia (todo nó tem 0 ou 2 filhos) e perfeita (todos os níveis cheios). É exatamente nessa distinção que as alternativas se dividem.

Alternativa A — ✅ Correta ⟵ GABARITO

A definição apresentada é exatamente a de árvore binária completa: todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós estão o mais à esquerda possível. Essa é a definição canônica, utilizada em estruturas de dados para garantir que a árvore possa ser armazenada eficientemente em um vetor, sem espaços vazios.

Alternativa B — ❌ Incorreta

A alternativa B troca a direção do preenchimento: diz que os nós estão "o mais à direita possível". Na definição de árvore binária completa, o preenchimento do último nível é feito da esquerda para a direita. Essa inversão é uma pegadinha clássica da banca, que testa se o candidato conhece a definição exata.

Alternativa C — ❌ Incorreta

A alternativa C afirma que "todos os níveis estão completamente preenchidos". Isso descreve a árvore binária perfeita, não a completa. A árvore completa admite que o último nível esteja incompleto, desde que os nós existentes estejam à esquerda. A banca confunde os conceitos de árvore completa e perfeita.

Alternativa D — ❌ Incorreta

A alternativa D afirma que "apenas o primeiro nível está completamente preenchido". Isso é incorreto, pois uma árvore binária completa pode ter vários níveis completamente preenchidos — apenas o último nível pode estar incompleto. A alternativa subestima a definição, limitando o preenchimento a um único nível.

Gabarito: letra A