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
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.
Á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.
-
Se voce tem uma lista ordenada, você pode usar algoritmos melhres que uma busca linear.– jsbuenoCommented 15/12/2016 às 10:52