10

Considere um árvore binária de busca não balanceada e uma lista vetorial ordenada. Qual das duas estruturas é mais indicada para realizar uma busca por qualquer elemento.

2 Respostas 2

9

O algoritmo mais eficaz para encontrar um elemento qualquer em ambos os casos é o mesmo: busca binária. Ele tem complexidade média O(log n).

O problema é que em árvores binárias não balanceadas, o cenário de pior caso é O(n). Por exemplo, imagine que estou procurando 5 na árvore abaixo:

1
 \
  2
   \
    3
     \
      4
       \
        5

O algoritmo vai percorrer todos os elementos da árvore achar o 5. Já com listas ordenadas, o pior caso continua sendo O(log n). Tendo os mesmos itens como exemplo:

[1,2,3,4,5]

O algoritmo vai percorrer apenas o 3, 4 e 5 até encontrar o resultado. Desta forma é preferível usar uma lista ordenada.

0

Árvore ABB. A complexidade da árvore é O(log n) e a complexidade da lista ordenada é O(n), então a busca em uma árvore ABB é mais eficiente que a busca na lista.

1
  • Se voce tem uma lista ordenada, você pode usar algoritmos melhres que uma busca linear.
    – jsbueno
    15/12/2016 às 10:52

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .