Árvore Binária de Busca (BST)
Gabarito: letra B. Uma BST é, por definição, uma árvore binária, e portanto cada nó pode ter no máximo dois filhos. As demais alternativas violam propriedades fundamentais da BST, conforme explicado a seguir.
O material de apoio define que uma árvore binária de busca é uma "árvore binária rotulada" e que "todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz". Além disso, a altura no pior caso pode ser O(n), quando a árvore degenera em lista encadeada (árvore zig-zag).
Alternativa | Afirmação | Correta? | Justificativa |
|---|
A | Valor de qualquer nó é sempre menor que o de seus filhos | ❌ Incorreta | O nó raiz tem valor maior que o filho esquerdo e menor que o direito; a propriedade correta é que todos os valores da subárvore esquerda são menores e os da direita são maiores |
B | Todos os nós têm no máximo dois filhos | ✅ Correta (GABARITO) | BST é um tipo de árvore binária, e toda árvore binária tem essa propriedade definidora |
C | Soma dos valores à esquerda é menor que a soma à direita | ❌ Incorreta | A propriedade é individual (cada nó), não sobre somas; a distribuição dos números pode inverter a relação |
D | Altura é sempre O(log n) | ❌ Incorreta | No pior caso (inserção ordenada), a BST degenera em lista encadeada com altura O(n); apenas árvores balanceadas garantem O(log n) |
E | Valores armazenados em posições contíguas de memória | ❌ Incorreta | Nós são alocados dinamicamente com ponteiros; posições contíguas são características de vetores/arrays |
Alternativa A — ❌ Incorreta
Afirma que qualquer nó tem valor sempre menor que o de seus filhos. Isso é falso: o nó raiz, por exemplo, tem valor maior que o filho esquerdo e menor que o filho direito. A propriedade correta é que todos os valores da subárvore esquerda são menores, e os da subárvore direita são maiores.
Alternativa B — ✅ Correta ⟵ GABARITO
Uma BST é um tipo de árvore binária, e toda árvore binária tem a propriedade de que cada nó possui no máximo dois filhos. Essa é uma característica definidora, independentemente da ordenação das chaves.
Alternativa C — ❌ Incorreta
A propriedade da BST é individual: cada nó tem valor maior que todos os da esquerda e menor que todos os da direita. A soma dos valores das subárvores não é necessariamente menor ou maior; ela depende da distribuição dos números. Por exemplo, a subárvore esquerda pode conter muitos números grandes e a direita poucos pequenos, invertendo a relação esperada.
Alternativa D — ❌ Incorreta
A altura de uma BST não é sempre O(log n). No pior caso, quando os elementos são inseridos em ordem crescente ou decrescente, a árvore se torna uma lista encadeada, com altura O(n). O próprio material de apoio afirma: "No pior caso, uma ABB poderá ter altura O(n)". Árvores balanceadas (como AVL ou rubro-negra) garantem O(log n), mas a BST comum não.
Alternativa E — ❌ Incorreta
Nós de uma BST são alocados dinamicamente, geralmente utilizando ponteiros. Não há exigência de que os valores estejam em posições contíguas de memória; isso seria característico de um vetor ou array, não de uma árvore.
Gabarito: letra B.