Em uma Árvore Binária de Busca (BST) balanceada, qual das seguintes operações geralmente exibe uma complexidade de tempo média de
, considerando a estrutura balanceada da árvore?
d) inserção de um novo nó, remoção de um nó e busca por um elemento.
d) inserção de um novo nó, remoção de um nó e busca por um elemento.
Passo 1
Vamos analisar a questão: em uma Árvore Binária de Busca (BST) balanceada, queremos saber quais operações geralmente têm uma complexidade de tempo média de
. As operações em questão são a inserção de um novo nó, a remoção de um nó e a busca por um elemento. Vamos entender o que é uma BST balanceada e como cada operação se comporta em termos de eficiência.
Passo 2
Primeiro, uma Árvore Binária de Busca (BST) é uma estrutura de dados onde cada nó tem, no máximo, dois filhos. Para qualquer nó, os valores dos nós na subárvore esquerda são menores que o valor do próprio nó, e os da subárvore direita são maiores. Isso permite uma busca eficiente por elementos.
Passo 3
Uma árvore está balanceada quando as alturas das subárvores esquerda e direita de qualquer nó diferem no máximo em uma unidade. Isso garante que o caminho da raiz a uma folha seja sempre proporcional a
, onde
é o número de nós na árvore. Portanto, operações que percorrem esses caminhos terão complexidade de
.
Passo 4
Vamos analisar cada operação:
-
Inserção de um novo nó: Envolve encontrar a posição correta na árvore para manter a propriedade da BST, o que requer percorrer o caminho da raiz até a posição de inserção. Como a árvore é balanceada, esse caminho tem comprimento
. -
Remoção de um nó: Similar à inserção, primeiro precisamos localizar o nó a ser removido, o que leva . Após a remoção, pode ser necessário reequilibrar a árvore, mas em uma árvore balanceada, isso também ocorre em tempo
. -
Busca por um elemento: Consiste em comparar o elemento alvo com os nós, seguindo caminhos à esquerda ou direita. Com a árvore balanceada, o número de comparações é proporcional a
, ou seja, .
Resposta
Todas as operações mencionadas — inserção de um novo nó, remoção de um nó e busca por um elemento — geralmente têm uma complexidade de tempo média de
em uma BST balanceada.