3

Pelo que entendi, o algoritmo de árvore binária de busca funciona no final das contas, da mesma maneira que o algoritmo de busca binária, com apenas algumas alterações, correto?

Sendo mais direto: a árvore binária de busca é a implementação do algoritmo de busca binária numa estrutura de árvore, certo?

2 Respostas 2

3

Quase isso.

O conceito de busca binária é a ideia de dividir o espaço de busca sucessivamente em metades até que você só tenha o elemento que estava procurando ou conclua que ele não está no conjunto de elementos procurados. Para dar certo, pressupõem-se que esse espaço de busca tenha os elementos devidamente ordenados para que ao quebrá-lo no meio, você saiba em qual metade remanescente continuar a busca.

Entretanto, o conceito de busca binária nada fala sobre a implementação em si. Pode ser arquivos, arrays, listas, cartas de baralho na mão de uma pessoa ou até mesmo uma sequência de pedras ordenadas por tamanho em cima de uma mesa.

Já a árvore de busca binária é uma implementação específica em particular. A árvore binária é uma estrutura de dados muito versátil e eficiente (desde que sejam árvores ao menos razoavelmente balanceadas) para se armazenar dados que permitam posteriormente que os mesmos sejam pesquisados por meio de busca binária.

No entanto, não é que a árvore binária seja uma modificação do algoritmo de busca binária. Na verdade ela é uma estratégia a ser utilizada para se atacar um problema. Se o seu problema depende de buscar dados rapidamente e esses podem ser ordenados por algum critério, uma forma de atingir-se isso é organizando-os em forma de uma árvore binária para então poder fazer a busca binária.

2
  • Isso me lembrou que na busca binária meio que equivale ao caso de árvore completa. Árvores degeneradas viram listas Commented 16/03/2018 às 21:27
  • 1
    @JeffersonQuesado E é por isso que inventaram as árvores binárias com auto-rebalanceamento. Árvores desbalanceadas no pior caso se degeneram em listas ligadas. Commented 16/03/2018 às 21:28
2

Não é que funcione com algumas alterações. Você pode aplicar o algoritmo de busca binária em qualquer estrutura de dados que esteja ordenada.

Mas cada estrutura de dados vai ter uma implementação própria para navegar a estrutura, assim o algoritmo de busca binária em um vetor tem uma implementação, em árvore tem outra.

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 .