Questão de TI - Soluções · FGV EPE 2024 (nº 75)

Uma árvore de busca binária (BST) organiza seus dados de forma que, para qualquer nó, todos os valores na sua subárvore esquerda são menores e todos na subárvore direita são maiores. Inserir um novo valor significa encontrar o local correto para ele, seguindo essa regra, percorrendo um caminho da raiz até uma folha (ou onde a folha deveria estar).

Análise do algoritmo:
O algoritmo começa na raiz (A.raiz) e desce pela árvore (x = x.esquerda ou x = x.direita) até encontrar o lugar onde o novo nó z deve ser inserido. A cada passo do laço ENQUANTO, ele se move um nível abaixo na árvore. O laço para quando x se torna NULL, indicando que o nó pai (y) para z foi encontrado. O número de iterações do laço é diretamente proporcional ao número de níveis que ele percorre, que é no máximo a altura da árvore. As operações fora do laço (inicialização e atribuição final do nó) levam tempo constante.

Tempo de execução:
O tempo de execução é dominado pelo laço ENQUANTO. Este laço executa comparações e atribuições, que são operações de tempo constante. O número de vezes que o laço é executado é igual ao número de nós visitados no caminho da raiz até o ponto de inserção. No pior caso, esse caminho pode ter o comprimento da altura da árvore.

(A) Incorreta: $O(n)$ implicaria que o algoritmo visitaria todos os $n$ nós da árvore, o que não é necessário para a inserção em uma BST.
(B) Incorreta: Esta seria a complexidade para uma BST balanceada (onde a altura $h$ é $O(\log n)$), mas o algoritmo é para uma BST geral, onde a altura $h$ pode ser tão grande quanto $n$ (no caso de uma árvore degenerada ou "torta"). A pegadinha é associar automaticamente BST com $\log n$, sem considerar a altura real da árvore.
(C) Incorreta: $O(n \log n)$ é geralmente associado a algoritmos de ordenação ou operações mais complexas que envolvem múltiplos percursos ou estruturas auxiliares. A inserção é um único percurso.
(D) Correta: O algoritmo percorre um único caminho da raiz até o ponto de inserção do novo nó. O número máximo de passos nesse caminho é determinado pela altura da árvore ($h$). Cada passo (comparação e movimento para esquerda/direita) leva tempo constante. Portanto, o tempo total é proporcional à altura da árvore, ou seja, $O(h)$.
(E) Incorreta: $O(\log h)$ significaria que o tempo de execução cresceria logaritmicamente com a altura, o que não corresponde a um percurso linear da raiz até a folha. Se a altura é $h$, o número de passos é $h$, não $\log h$.