Questão 163069

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobrás - Analista de Sistemas Júnior - Processos de Negócios
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em uma árvore de busca binária. Após a completa inserção de todos os elementos nesta árvore, são feitas buscas de números na mesma. O tempo médio de busca de um número nesta árvore é

• A. O(1)
  
• B. O(log N)
  
• C. O(N)
  
• D. O(Nlog N)
  
• E. O(N²)

Gabarito: C

Comentários

• Letra C
  
  Quando forma removidos da pilha os números voltaram em ordem decrescente.
  Se inserir um lista decrescente em um arvore, teremos um árvore com um único ramo, semelhante a uma lista encadeada. A busca nessa estrutura é de ordem O(N)
  
• Então o pior caso da busca binaria deveria ser O(n). Porem vi em muitas referencias que o pior caso é O(log n). Agora fiquei na duvida.
• Oi Bruno!! O que acontece é que os elementos da pilha foram inseridos de forma linear na arvore, por isso é que a resposta é O(n).
  No caso da arvore binaria de pesquisa completa e balanceada a complexidade é esta que você disse O(log n).
• Questão bem bolada que engana fácil se não estiver firme nos conceitos. Em uma árvore de busca binária balanceada, por definição, os elementos menores estão à esquerda de um nó e os maiores, à direita. Além disso, por ser balanceada (AVL), as alturas das duas sub-árvores a partir de cada nó diferem nó máximo em uma unidade. Desta forma, a complexidade de busca é O(log n) na base 2. Em outras palavras, a cada vez que dobra a quantidade de elementos, o número de operações de busca aumenta em um. Como nesta árvore os números foram inseridos a partir de uma pilha ordenada, a cada inserção - do maior para o menor valor - os nós posicionaram-se a esquerda do nó pai, formando uma árvore de um único ramo, ou seja, uma árvore que não está balanceada. Nestas condições, a busca se torna sequencial, sendo necessário, no pior caso, percorrer todos os elementos da árvore - O(n).

• A primeira informação é que temos uma lista ordenada e cada elemento dessa lista é retirado e inserido em uma pilha, logo após são retirados da pilha, com isso obtemos a lista em ordem inversa, se inserirmos essa lista inversa em uma árvore obtemos uma árvore degenerada que tem complexidade de tempo O(N). Logo, resposta letra C)