Considere uma árvore binária de busca com n elementos e altura mínima. O temp...
Responda: Considere uma árvore binária de busca com n elementos e altura mínima. O tempo de acesso a qualquer elemento desta árvore é da ordem de:
💬 Comentários
Confira os comentários sobre esta questão.
Por Rodrigo Ferreira em 31/12/1969 21:00:00
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).
⚠️ Clique para ver os comentários
Visualize os comentários desta questão clicando no botão abaixo
Ver comentários