Teste sobre Árvore de busca binária

Pergunta 1: Uma Árvore de Busca Binária é uma estrutura de dados que organiza elementos de forma que todos os valores na subárvore esquerda de um nó são menores que o valor do próprio nó, e todos os valores na subárvore direita são maiores que o valor do próprio nó.

A. Sim

B. Não

Explicação: A propriedade fundamental de ordenação de uma Árvore de Busca Binária estabelece que, para qualquer nó, todos os valores em sua subárvore esquerda são menores que o valor do nó, e todos os valores em sua subárvore direita são maiores que o valor do nó. Esta é a característica distintiva que permite buscas eficientes.

Pergunta 2: A unicidade de valores em uma Árvore de Busca Binária é uma regra estrita em todas as suas definições?

A. Sim

B. Não

Explicação: O material de estudo afirma que a unicidade de valores, embora seja uma convenção comum, 'não é uma regra estrita de todas as definições'.

Pergunta 3: Qual é a propriedade fundamental que distingue uma Árvore de Busca Binária (ABB) e a torna eficiente para busca?

A. Cada nó possui no máximo três filhos, garantindo uma estrutura mais robusta.

B. Para qualquer nó, todos os valores na sua subárvore esquerda são maiores e na subárvore direita são menores que o valor do próprio nó.

C. A propriedade de ordenação, onde valores menores estão na subárvore esquerda e valores maiores na subárvore direita de um nó.

D. A capacidade de armazenar valores duplicados sem a necessidade de uma convenção específica.

Explicação: A propriedade fundamental que torna uma Árvore de Busca Binária eficiente para busca é a propriedade de ordenação. Esta propriedade estabelece que, para qualquer nó na árvore, todos os valores na sua subárvore esquerda são menores que o valor do próprio nó, e todos os valores na sua subárvore direita são maiores que o valor do próprio nó. Esta regra direciona a busca e garante a eficiência logarítmica em árvores balanceadas. As outras opções descrevem propriedades incorretas ou não são a característica distintiva principal.

Pergunta 4: Sobre a complexidade de tempo da operação de busca em uma Árvore de Busca Binária (ABB), qual das seguintes afirmações está correta?

A. A complexidade de tempo da busca é sempre O(log n), independentemente da estrutura da árvore.

B. No melhor caso, quando a árvore é balanceada, a complexidade de tempo é O(log n).

C. No pior caso, quando a árvore é degenerada em uma lista encadeada, a complexidade de tempo é O(n).

D. A complexidade de tempo da busca é sempre O(h), onde h é o número total de nós da árvore.

Explicação: A complexidade de tempo da busca em uma ABB é O(h), onde h é a altura da árvore. No melhor caso, para uma árvore balanceada, h é aproximadamente log₂ n, resultando em uma complexidade de O(log n). No pior caso, para uma árvore degenerada (como uma lista encadeada), h é igual a n, resultando em uma complexidade de O(n). Portanto, a afirmação de que a complexidade é sempre O(log n) está incorreta. A afirmação de que a complexidade é sempre O(h) onde h é o número total de nós da árvore também está incorreta, pois h representa a altura, não o número total de nós, e O(h) é uma complexidade geral que varia conforme o balanceamento da árvore.

Pergunta 5: Na remoção de um nó `N` que possui apenas um filho, a propriedade da ABB é mantida substituindo `N` por um de seus sucessores para garantir a ordenação da árvore.

A. Sim

B. Não

Explicação: No caso de remoção de um nó `N` com apenas um filho, o estudo de caso indica que "O nó `N` é substituído pelo seu único filho. O pai de `N` agora aponta para o filho de `N`." A necessidade de manter a propriedade da ABB através da substituição por 'um de seus sucessores' é mencionada explicitamente apenas para o Caso 3, onde o nó `N` possui dois filhos, tornando-o o caso mais complexo.