Árvore Binária de Busca – Operação de Busca

OPERAÇÃO DE BUSCA

Agora que você já entendeu sobre Árvore Binária e Árvore Binária de Busca, vamos falar sobre a operação de busca.

Estou utilizando o exemplo do exercício anterior de árvores binárias. Nós sabemos que a árvore binária tem uma regra de inserção, então podemos esperar algumas coisas dela, por exemplo:

Criamos um search onde passamos uma árvore para ela e quero buscar um valor. Sabemos que se o valor dessa árvore não existir, temos que retornar undefined ou se a árvore for igual ao valor que estou buscando, vou retornar o valor. Caso contrário, se o valor que estou buscando for menor que o nó atual, ele deve estar do lado esquerdo, então vamos buscar o valor apenas no lado esquerdo e por último, se for maior, procuramos do lado direito.

Perceba que encontrou o 10, pois ele tinha na árvore. Se procurarmos um valor que não está na árvore, será retornado o undefined.

Ela sempre dividirá o problema em dois, então ao pensarmos na complexidade do código, é o contrário de termos um ‘for’ dentro do outro.  Como ele sempre divide em dois, no pior caso, o nosso algoritmo é 0(raiz(n)) então se tivermos 25 elementos, teremos mais ou menos 5 comparações, no nosso caso que temos 4, vamos ter 2 comparações. É algo muito rápido, logo a complexidade do algoritmo é 0(log n) que é uma performance muito boa para um algoritmo de busca. O search é o mais importante das árvores, não é atoa que se chama de busca.

Finalizamos todas as operações em árvore, visitar em pré order, in order e pós order, inserção e a busca em si que é muito utilizada.

Confira o vídeo:

Curta o DevPleno no Facebookinscreva-se no canal e não se esqueça de cadastrar seu e-mail para não perder as novidades. Abraço!