Questão 66460

Um professor de um curso de graduação em Ciência da Computação está lecionando sobre estruturas de dados e quer que seus alunos compreendam as implicações práticas da escolha entre uma Árvore de Busca Binária (BST - Binary Search Tree) e uma Árvore de Busca Binária Balanceada (como uma Árvore AVL ou Rubro-Negra). Ele observa que os alunos entendem a mecânica de inserção e busca em uma BST simples, mas não apreciam o problema do 'pior caso'. Para ilustrar, ele apresenta o seguinte trecho de 'Introduction to Algorithms' de Cormen et al.: "Uma árvore de busca binária pode realizar operações como busca, inserção e remoção em tempo $O(h)$, onde $h$ é a altura da árvore. No caso médio, para uma árvore construída com inserções aleatórias, a altura é $O(\log n)$, o que é muito eficiente. No entanto, no pior caso, como ao inserir elementos em ordem já ordenada, a árvore degenera em uma lista encadeada, e sua altura se torna $O(n)$. Isso transforma a BST em uma estrutura de dados ineficiente para essas operações. Árvores de busca binária auto-balanceadas, como as árvores AVL, executam rotações durante as operações de inserção e remoção para garantir que a altura da árvore permaneça $O(\log n)$, mesmo no pior caso, pagando um pequeno preço de sobrecarga em cada operação para manter o balanceamento." O professor então propõe uma atividade: os alunos devem desenhar a BST resultante da inserção dos números [10, 20, 30, 40, 50] em uma árvore inicialmente vazia e analisar sua estrutura.

Com base no cenário e no referencial teórico, avalie as seguintes afirmações:

I. A árvore resultante da inserção sequencial dos números [10, 20, 30, 40, 50] será uma estrutura degenerada, semelhante a uma lista encadeada, onde cada novo nó é o filho direito do anterior. A altura da árvore será 4 (ou $O(n)$).

II. Nesta árvore degenerada, uma operação de busca pelo número 50 exigiria 5 comparações, o mesmo número de comparações de uma busca linear em uma lista ordenada. Isso demonstra o pior caso de desempenho de uma BST.

III. Se a mesma sequência de números fosse inserida em uma árvore AVL, a estrutura final seria balanceada. Por exemplo, após a inserção do 30, uma rotação para a esquerda seria realizada para manter o fator de balanceamento, resultando em uma árvore mais 'cheia' e com menor altura.

É correto o que se afirma em: