Em uma Árvore Binária de Busca (BST) balanceada, qual das seguintes operações geralmente exibe uma complexidade de tempo média de O (log n), considerando a estrutura balanceada da

Gabarito

D

Comentário do professor

Em uma Árvore Binária de Busca (BST) Balanceada, a razão pela qual **Inserção**, **Remoção** e **Busca** apresentam complexidade média \(O(\log n)\) é a característica central de balanceamento: a **altura** da árvore cresce proporcionalmente a \( \log n \).

**Busca**: percorre-se da raiz até um nó folha seguindo comparações, realizando no máximo um número de passos proporcional à **altura**; assim o custo é \(O(\log n)\).

**Inserção**: localiza-se a posição adequada da mesma forma que na busca e insere-se o nó; em árvores balanceadas (ex.: AVL, Red‑Black) as rotações necessárias para manter o balanceamento têm custo adicional limitado, mantendo o tempo total em \(O(\log n)\).

**Remoção**: envolve localizar o nó (custo \(O(\log n)\)), possivelmente substituir por sucessor/predecessor e aplicar rotações/reajustes locais; essas operações são também limitadas em número, preservando a complexidade \(O(\log n)\).