Questão 54 · Informática: Programação e algoritmos
O trecho de código escrito em PHP (versão 5.4.4) apresentado a seguir implementa o algoritmo de busca em árvore binária. <?php class Nodo { public $valor, $esq, $dir; }; class ArvoreBalanceada { public $raiz; // nodo raiz ou NULL /* Procura um nodo da árvore que con- * tenha um valor numérico. * Entrada: * $valor valor numérico a procurar * $nodo nodo da árvore ou subárvore * (instância da classe Nodo ou NULL) * Saída: * nodo que possui valor solicitado * ou NULL */ public function procura($valor, $nodo) { if ($nodo === NULL) return $nodo; else { if ($valor == $nodo->valor) return $nodo; else if ($valor < $nodo->valor) { return $this->procura($valor, $nodo->esq); } else { return $this->procura($valor, $nodo->dir); } } } };?> Considere que o método procura() seja aplicado ao nó raiz da árvore binária de busca e que esta seja balanceada.
Assinale a opção que indica a complexidade desse algoritmo.
- A) O(n)
- B) O(log n)
- C) O(n log n)
- D) O(n²)
- E) O(n³)
Marque a alternativa correta:
Gabarito: B
Gabarito definitivo divulgado pela banca FGV (DPE/MT 2015).
Comentário
Gabarito: B.
O método procura() compara o valor buscado com o do nó atual: se for igual, retorna o nó; se for menor, segue para a subárvore esquerda; se for maior, segue para a direita. Em cada chamada descarta-se uma subárvore. Como a árvore é balanceada, sua altura é da ordem de log n, e o número de comparações é proporcional à altura. Portanto a complexidade é O(log n): alternativa B.
- (A) O(n) ocorreria se a árvore fosse degenerada (como uma lista), em que seria preciso percorrer todos os nós.
- (C) O(n log n) não corresponde a uma única descida pela árvore.
- (D) O(n²) é maior do que o necessário para um único caminho da raiz até uma folha.
- (E) O(n³) também não tem relação com um único caminho da raiz até uma folha.
Dica: a busca em árvore binária de busca custa proporcional à altura; árvore balanceada tem altura O(log n).
Fundamentos: árvores binárias de busca · complexidade logarítmica · altura de árvores balanceadas
Comentário gerado pela Cravei IA a partir do enunciado e do gabarito definitivo divulgado pela banca, e conferido por uma verificação automática. A IA pode errar: o gabarito oficial sempre prevalece.
Fonte: prova FGV DPE/MT 2015 (Analista de Sistemas), questão 54, com o gabarito definitivo da banca. Comentário: Equipe Cravei · como fazemos e revisamos.