Árvore Binária de Busca em JavaScript
Tulio Faria3 de julho de 2017
Hoje vamos falar mais sobre árvores binárias, porém um tipo específico, a árvore binária de busca.
Qual a diferença da árvore binária de busca para a árvore binária normal?
Na normal, simplesmente inserimos os nós dentro da árvore sem garantir nenhuma regra, já a de busca segue a seguinte regra:
Temos a raiz e inserimos um valor nessa raiz. Quando inserimos o segundo valor, se for maior que a raiz, ele fica à direita, se ele for menor, ficará à esquerda. Com isso conseguimos fazer muitas outras operações utilizando essa árvore binária.
Primeiramente vamos fazer a inserção em uma árvore binária de busca. Para fazermos isso, temos que checar se essa árvore tem algum valor, depois verificamos se ele é maior ou menor para inserirmos para left ou right.
const arvore = {} function insert(tree, value) { if (tree.value) { if (value > tree.value) { insert(tree.right, value) } else { insert(tree.left, value) } } else { tree.value = value tree.right = {} tree.left = {} } } insert(arvore, 10) console.log(arvore)
Se não for inserido o tree.value, vai ser igual a value, o tree.right e tree.left serão árvores vazias. Eu estou definindo isso porque quando inserirmos podemos passar uma árvore vazia no insert e ele continua fazendo isso de forma recursiva. Colocando o valor 10, perceba que será retornado: Se inserirmos, por exemplo, um valor 11 em seguida:
insert(arvore, 10) console.log(arvore) insert(arvore, 11) console.log(arvore)
Será retornado o seguinte:
Agora vamos colocar o valor 9:
insert(arvore, 10) console.log(arvore) insert(arvore, 11) console.log(arvore) insert(arvore, 9) console.log(arvore)
Será retornado o seguinte: Na primeira inserção, retorna 10, na segunda 10 e 11 e na terceira 10, 11 e 9, sendo 11 do lado direito, 9 do lado esquerdo e 10 nossa raiz. Vamos colocar um 8 agora:
insert(arvore, 10) console.log(arvore) insert(arvore, 11) console.log(arvore) insert(arvore, 9) console.log(arvore) insert(arvore, 8) console.log(arvore)
O resultado será:
Com o 8 agora temos 10 na raiz, 11 do lado direito, do lado esquerdo 9 e do lado esquerdo do lado esquerdo 8.
Com isso conseguimos fazer o algoritmo de inserção na árvore de busca. É importante ressaltar que isso não é programação funcional, já que não estamos retornando uma nova árvore. Fiz isso apenas para mostrar que boa parte dos algoritmos que fazemos em C ou alguma linguagem que vemos na graduação utilizam a passagem por referência.
Confira o passo a passo no vídeo:
Curta o DevPleno no Facebook, inscreva-se no canal e não se esqueça de cadastrar seu e-mail para não perder as novidades. Abraço!
Autor
Tulio Faria3 de julho de 2017