Questão 898087

• Banca: CESGRANRIO
• Órgão: BNDES
• Ano: 2013
• Provas: CESGRANRIO - 2013 - BNDES - Profissional Básico - Análise de Sistemas - Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados

Uma árvore rubro-negra possui 18 valores inteiros distintos armazenados em seus 18 nós.

Uma função recursiva, cujo cabeçalho é boolean busca (int val), foi escrita com o objetivo de visitar os nós desse tipo de árvore à procura de um determinado valor (val). O algoritmo utilizado tira partido das características de uma árvore rubro-negra, com o objetivo de ser o mais eficiente possível.

Qual é o número máximo de chamadas à função busca( ) que será necessário para informar se um determinado valor está, ou não, armazenado na árvore?

• A. 3
• B. 4
• C. 5
• D. 6
• E. 9

Gabarito: C

Comentários

• Por que não é a letra D?

• Vamos contar as chamadas recursivas, e ver quantos valores a recursão já percorreu

  1°     |    1 valor

   2°  |      |   3 valores

  3º  | |    | |   7 valores

  4º  || ||  || ||  15 valores

  5°   |||||||||||...  31 valores

  Logo a função tem que ser chamada 5 vezes pra com certeza ter passado pelos 18 valores
  

• 18 nos + balanceamento nulo= 32 nós.....x=32

  RUBRO NEGRA PIOR CASO, OlogN= X   ---- 2^x=32   ----   x= 5

  
  

• Uma árvore rubro-negra é uma árvore de busca binária onde cada nó tem um atributo decor, vermelho ou preto. 

  
  

  Fonte: http://pt.wikipedia.org/wiki/%C3%81rvore_rubro-negra

• acertei usando a profundidade/nível da árvore.

  para a CESGRANRIO a raiz começa no nível 1.

  se temos 18 nós , então teremos 5 passos ( chamadas ).

• Força Guerreiro!!!!!!