Rodrigo Ferreira
EQUIPE
23/10/2025 • 12:56
Gabarito: c) O(log2 n)
Uma árvore binária de busca (ABB) é uma estrutura de dados onde cada nó possui no máximo dois filhos, e os valores são organizados de forma que o filho esquerdo contém valores menores e o filho direito valores maiores que o nó pai.
Quando a árvore tem altura mínima, ela está balanceada, ou seja, a altura é proporcional ao logaritmo do número de elementos, especificamente log base 2 de n, porque a cada nível a quantidade de nós pode dobrar.
O tempo de acesso a um elemento em uma ABB balanceada é proporcional à altura da árvore, pois para encontrar um elemento, percorremos do nó raiz até o nó desejado, passando por no máximo a altura da árvore.
Portanto, o tempo de acesso é da ordem de O(log2 n), que corresponde à alternativa c).
Checagem dupla: alternativas a), b) e e) representam tempos muito maiores que o necessário para uma árvore balanceada. A alternativa d) também é logarítmica, mas a base do logaritmo não altera a ordem de complexidade, pois log base 10 e log base 2 diferem apenas por uma constante multiplicativa, mas a notação assintótica geralmente considera log base 2 para árvores binárias.
Assim, a resposta correta é a alternativa c).
Uma árvore binária de busca (ABB) é uma estrutura de dados onde cada nó possui no máximo dois filhos, e os valores são organizados de forma que o filho esquerdo contém valores menores e o filho direito valores maiores que o nó pai.
Quando a árvore tem altura mínima, ela está balanceada, ou seja, a altura é proporcional ao logaritmo do número de elementos, especificamente log base 2 de n, porque a cada nível a quantidade de nós pode dobrar.
O tempo de acesso a um elemento em uma ABB balanceada é proporcional à altura da árvore, pois para encontrar um elemento, percorremos do nó raiz até o nó desejado, passando por no máximo a altura da árvore.
Portanto, o tempo de acesso é da ordem de O(log2 n), que corresponde à alternativa c).
Checagem dupla: alternativas a), b) e e) representam tempos muito maiores que o necessário para uma árvore balanceada. A alternativa d) também é logarítmica, mas a base do logaritmo não altera a ordem de complexidade, pois log base 10 e log base 2 diferem apenas por uma constante multiplicativa, mas a notação assintótica geralmente considera log base 2 para árvores binárias.
Assim, a resposta correta é a alternativa c).