Questão de Algoritmos e Estrutura de Dados — Conceitos Básicos de Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Conceitos Básicos de Estrutura de Dados
Código
fg084694
Banca
FGV
Órgão
EPE
Ano
2024
Nível
Superior
Cargo
Analista de Gestão Corporativa - Tecnologia da Informação (Soluções)
Considere o algoritmo a seguir, escrito em pseudocódigo, para inserir um novo valor z em uma árvore de busca binária A com n nós e altura h.1 y = NULL 2 x = A.raiz 3 ENQUANTO x ≠ NULL FAÇA: 4 y = x 5 SE z.chave < x.chave: x = x.esquerda 6 SE NÃO: x = x.direita 7 z.p = y 8 SE y = NULL: A.raiz = z 9 SE NÃO: 10 SE z.chave < y.chave: y.esquerda = z 11 SE NÃO: y.direita = z O algoritmo acima é executado no tempo
AO(n)
BO(log n)
CO(n log n)
DO(h)
EO(log h)
Revelar gabarito e comentário▾
GabaritoD — O(h)
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Inserção em Árvore Binária de Busca – Complexidade
Gabarito: letra D. O algoritmo percorre a árvore da raiz até uma folha, seguindo os ponteiros esquerda/direita conforme a comparação de chaves. O número de iterações do laço ENQUANTO é exatamente a altura h da árvore (número de níveis percorridos). Portanto, o tempo de execução é O(h).
A complexidade da inserção em uma BST (sem balanceamento) é sempre O(h), independentemente do número total de nós n. Em uma árvore degenerada (lista encadeada), h = n, então O(h) = O(n); em uma árvore balanceada, h = log n, então O(h) = O(log n). Mas a notação correta que reflete o comportamento do algoritmo é O(h), pois h é o parâmetro que determina diretamente o custo.
Alternativa A — ❌ Incorreta
O(n) seria o tempo se o algoritmo visitasse todos os nós, o que não ocorre. Apenas em árvores degeneradas (h = n) o valor de O(h) coincide com O(n), mas a expressão geral da complexidade da BST é O(h), e não O(n).
Alternativa B — ❌ Incorreta
O(log n) só é válido para árvores balanceadas (como AVL ou Rubro-Negra). A questão não afirma que a árvore é balanceada; ela apenas fornece a altura h. Para uma BST qualquer, o pior caso é O(h), que pode ser O(log n) ou O(n) dependendo da forma da árvore.
Alternativa C — ❌ Incorreta
O(n log n) é uma complexidade típica de algoritmos de ordenação (como Merge Sort) ou de operações em algumas estruturas de dados. A inserção em BST percorre um único caminho da raiz até a folha, sem repetições ou divisões recursivas que gerariam esse custo.
Alternativa D — ✅ Correta ⟵ GABARITO
Conforme explicado, o laço principal executa h iterações (altura da árvore). Cada iteração realiza operações de atribuição e comparação em tempo constante. Logo, o tempo total é Θ(h) no caso médio e no pior caso, sendo O(h) a notação correta.
Alternativa E — ❌ Incorreta
O(log h) não faz sentido: a altura h já é a medida do caminho percorrido. Se a complexidade fosse O(log h), significaria que o número de passos diminui conforme a altura aumenta, o que é absurdo. Além disso, o número de iterações é linear em h, não logarítmico.
PEGA ESSA DICA!
Em questões de complexidade de BST, sempre lembre: a altura h é o parâmetro relevante. O(log n) só vale se a árvore for balanceada. A notação O(h) captura a realidade do pior caso: se a árvore é uma lista, h = n, se é balanceada, h = log n.