Q123950 – Analista de Sistemas – Fundação Getulio Vargas 2015

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.