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. Em 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 alternativa A reproduz corretamente.

Uma árvore binária é uma estrutura de dados hierárquica em que cada nó possui no máximo dois filhos, chamados de filho esquerdo e filho direito. A partir dessa definição básica, surgem variações importantes que a banca costuma 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 principal armadilha em questões sobre o tema.

A árvore binária completa é definida por duas propriedades: (1) todos os níveis, exceto possivelmente o último, estão completamente preenchidos; (2) no último nível, os nós estão o mais à esquerda possível. Isso significa que, se o último nível não estiver totalmente preenchido, os nós que existem nele devem estar agrupados à esquerda, sem lacunas entre eles. Essa estrutura é especialmente útil para implementar heaps (como a heap binária usada em filas de prioridade) e para armazenamento em arrays, pois permite mapear os nós em posições contíguas do vetor.

Por outro lado, a árvore binária cheia (ou estritamente binária) é aquela em que todo nó tem 0 ou 2 filhos — nunca apenas 1 filho. Já a árvore binária perfeita é aquela em que todos os níveis estão completamente preenchidos, ou seja, todos os nós internos têm exatamente 2 filhos e todas as folhas estão no mesmo nível. A árvore perfeita é um caso especial da árvore completa, mas nem toda árvore completa é perfeita.

Vamos a um exemplo concreto para fixar. Considere uma árvore com 4 níveis (raiz no nível 0). Uma árvore perfeita teria 1 + 2 + 4 + 8 = 15 nós, com todos os níveis cheios. Uma árvore completa poderia ter, por exemplo, apenas 10 nós: os níveis 0, 1 e 2 completamente preenchidos (1 + 2 + 4 = 7 nós) e o nível 3 com apenas 3 nós, todos posicionados à esquerda. Se esses 3 nós do último nível estivessem espalhados (por exemplo, um à esquerda e dois à direita, com uma lacuna no meio), a árvore não seria completa.

A pegadinha que a banca explora nesta questão é justamente a troca do termo "à esquerda" por "à direita" na alternativa B, e a generalização indevida nas alternativas C e D. O candidato que não domina a definição exata de árvore binária completa pode facilmente cair na armadilha de achar que "completa" significa "todos os níveis preenchidos" (que é a definição de árvore perfeita) ou que o preenchimento poderia ser à direita.

Guarde a fronteira entre árvore completa, cheia e perfeita: é exatamente nela que as alternativas se dividem. A alternativa A é a única que traz a definição correta, com as duas propriedades essenciais: níveis preenchidos exceto o último e nós mais à esquerda possível.

Alternativa A — ✅ Correta ⟵ GABARITO

A alternativa A reproduz fielmente a definição 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 adotada na literatura de estruturas de dados (como em Cormen et al., "Algoritmos: Teoria e Prática"). A propriedade de preenchimento à esquerda é o que diferencia a árvore completa da árvore cheia e da árvore perfeita.

Alternativa B — ❌ Incorreta

A alternativa B troca o termo "à esquerda" por "à direita". Essa é a pegadinha clássica da banca: a definição correta exige que os nós do último nível estejam o mais à esquerda possível, não à direita. Uma árvore com nós à direita no último nível não é uma árvore binária completa, pois viola a propriedade de preenchimento contíguo à esquerda, essencial para a implementação eficiente em arrays (como em heaps).

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 árvore completa. A árvore completa admite que o último nível não esteja totalmente preenchido — desde que os nós existentes estejam à esquerda. A alternativa C generaliza indevidamente, eliminando a exceção "exceto possivelmente o último" que é parte essencial da definição.

Alternativa D — ❌ Incorreta

A alternativa D afirma que "apenas o primeiro nível está completamente preenchido". Isso é incorreto, pois a definição de árvore completa exige que todos os níveis, exceto possivelmente o último, estejam completamente preenchidos — não apenas o primeiro. Uma árvore com apenas o primeiro nível preenchido seria uma árvore com apenas a raiz, o que não corresponde à definição de árvore completa (e nem de árvore cheia ou perfeita).

Gabarito: letra A