Carregando...
Carregando...
Para manter o balanceamento de uma árvore binária de busca (BST), é fundamental entender as operações de rotação que podem ser aplicadas. As rotações são usadas para restaurar o balanceamento da árvore após inserções ou remoções de nós, garantindo que a profundidade da árvore permaneça minimizada para otimizar as operações de busca, inserção e remoção.
Considere as seguintes condições de uma árvore binária de busca após a inserção de um novo nó. Analise as situações e assinale a alternativa correta sobre a rotação necessária para manter a árvore balanceada.
Se a inserção ocorrer no filho esquerdo do filho esquerdo do nó crítico, uma rotação simples à direita é necessária. Se a inserção ocorrer no filho direito do filho direito do nó crítico, uma rotação simples à esquerda é necessária. Se a inserção ocorrer no filho direito do filho esquerdo do nó crítico, uma rotação dupla (esquerda-direita) é necessária. Se a inserção ocorrer no filho esquerdo do filho direito do nó crítico, uma rotação dupla (direita-esquerda) é necessária.
Está correto o que afirma em:
Explique melhor esta questão
Abre o Tutor com o enunciado e as alternativas já no campo — você revisa e envia.
Esta questão foi verificada por um de nossos administradores.
A afirmativa I é correta, pois se a inserção ocorrer no filho esquerdo do filho esquerdo do nó crítico, uma rotação simples à direita é necessária. Isso é para corrigir o desbalanceamento causado pelo aumento da altura na subárvore esquerda.
A afirmativa II é correta, pois se a inserção ocorrer no filho direito do filho direito do nó crítico, uma rotação simples à esquerda é necessária. Isso é para corrigir o desbalanceamento causado pelo aumento da altura na subárvore direita.
A afirmativa III é correta, pois se a inserção ocorrer no filho direito do filho esquerdo do nó crítico, uma rotação dupla (esquerda-direita) é necessária. Isso corrige o desbalanceamento causado por uma configuração em que a subárvore esquerda do nó crítico se torna desbalanceada para a direita.
A afirmativa IV é correta, pois se a inserção ocorrer no filho esquerdo do filho direito do nó crítico, uma rotação dupla (direita-esquerda) é necessária. Isso corrige o desbalanceamento causado por uma configuração em que a subárvore direita do nó crítico se torna desbalanceada para a esquerda.