QUESTÕES:
1 - (POSCOMP 2023) Sobre as árvores binárias de busca, é correto afirmar que:
A) Seja
um nó em uma árvore de busca binária. Se y é um nó na subárvore esquerda de
, então y.chave
.chave. Se y é um nó na subárvore direita de
, então
.chave
.chave.
B) A propriedade de árvore de busca que permite imprimir todas as chaves em sequência ordenada por meio de um simples algoritmo recursivo é denominada percurso de árvore em pré-ordem.
C) Para excluir um nó z de uma árvore de busca binária T , se z tem apenas um filho, então simplesmente o removemos modificando seu pai de modo a substituir z por NIL como seu filho.
D) Para excluir um nó
de uma árvore de busca binária
, se
tem dois filhos, então elevamos o primeiro filho para que ocupe a posição de
na árvore modificando o pai de
de modo a substituir
pelo filho de
.
E) Para encontrar um nó em uma árvore de busca binária cuja chave é um mínimo, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.
A) Seja
B) A propriedade de árvore de busca que permite imprimir todas as chaves em sequência ordenada por meio de um simples algoritmo recursivo é denominada percurso de árvore em pré-ordem.
C) Para excluir um nó z de uma árvore de busca binária T , se z tem apenas um filho, então simplesmente o removemos modificando seu pai de modo a substituir z por NIL como seu filho.
D) Para excluir um nó
E) Para encontrar um nó em uma árvore de busca binária cuja chave é um mínimo, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.
Passo 1
Beleza, aqui a gente tem uma questão de teoria de árvores binárias de busca (BST). O enunciado apresenta cinco afirmações sobre BSTs e pede pra identificar qual delas é correta. Para resolver, a gente vai precisar lembrar das propriedades fundamentais de BST (ordenamento, percurso e exclusão).
Passo 2
Teoria básica:
Em uma BST, para todo nó :
Em uma BST, para todo nó
- Qualquer nó
na subárvore esquerda de satisfaz . - Qualquer nó
na subárvore direita de satisfaz .
Além disso, o percurso in-order (esquerda, raiz, direita) imprime as chaves em ordem crescente, e a exclusão tem três casos:
- Nó sem filhos: remove direto.
- Nó com um filho: substitui o nó pelo seu filho.
- Nó com dois filhos: acha o sucessor (menor da subárvore direita), copia a chave e exclui o sucessor.
Passo 3
Analisando a opção A:
“A) Se está na subárvore esquerda de
, então
. Se
está na subárvore direita de
, então
.”
– Isso está invertido: na esquerda deve valer . Logo A é falsa.
“A) Se
– Isso está invertido: na esquerda deve valer
Passo 4
Analisando a opção B:
“B) A propriedade que permite imprimir as chaves em sequência ordenada é denominada percurso de árvore em pré-ordem.”
– Na verdade a ordenação crescente vem do in-order, não do pré-ordem. Então B é falsa.
“B) A propriedade que permite imprimir as chaves em sequência ordenada é denominada percurso de árvore em pré-ordem.”
– Na verdade a ordenação crescente vem do in-order, não do pré-ordem. Então B é falsa.
Passo 5
Analisando a opção C:
“C) Para excluir um nó , se
tem apenas um filho, simplesmente o removemos modificando seu pai para substituir
por NIL.”
– Errado: se tem um filho, você substitui
pelo seu filho, não por NIL. Então C é falsa.
“C) Para excluir um nó
– Errado: se
Passo 6
Analisando a opção D:
“D) Para excluir um nó com dois filhos, elevamos o primeiro filho para ocupar o lugar de
.”
– Também não: o procedimento correto é usar o sucessor (ou predecessor) para manter a ordenação, não “promover” o filho direto. D é falsa.
“D) Para excluir um nó
– Também não: o procedimento correto é usar o sucessor (ou predecessor) para manter a ordenação, não “promover” o filho direto. D é falsa.
Passo 7
Analisando a opção E:
“E) Para encontrar a chave mínima, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.”
– Isso bate com o algoritmo padrão: você anda sempre à esquerda até que o ponteiro seja NIL; o último nó não-NIL encontrado é o mínimo. E é verdadeira.
“E) Para encontrar a chave mínima, deve-se seguir os ponteiros de filhos da esquerda desde a raiz até encontrar um valor NIL.”
– Isso bate com o algoritmo padrão: você anda sempre à esquerda até que o ponteiro seja NIL; o último nó não-NIL encontrado é o mínimo. E é verdadeira.
Resposta
E