No tutorial desta semana veremos como implementar um sistema de busca binária em JavaScript e como estruturas recursivas podem nos auxiliar quando trabalhamo com listas e ordenação.
Estrutura de dados
Uma estrutura de dados refere-se a forma como os dados são armazenados e organizados. Um texto por exemplo é como uma grande cadeia de caracteres, enquanto que os registros armazenados no banco de dados podem ser vistos como uma tabela bidimensional composta por linhas e colunas.
Algumas estruturas de dados são consideradas básicas como matrizes, listas, pilhas e filas. Hoje iremos falar de uma estrutura conhecida como Árvore.
Não se preocupe, pois não será necessário revisar os conceitos de biologia, uma vez que o nome árvore provém do fato de que esta estrutura obedece a uma organização hierárquica semelhante a um organograma.
Um pequeno resumo para entendermos:
- Cada posição de uma árvore é chamada de nó;
- O nó no topo é o nó raiz;
- Os nós no outro extremo são nós terminais (ou nós folha);
- O número de nós seguindo pelo caminho mais longo até chegar ao nó terminal se refere a profundidade da árvore;
- Um nó qualquer junto com nós abaixo dele forma uma estrutura menor chamada de subárvore ou ramo;
- Podemos falar em ramo a esquerda ou ramo a direita dependendo de como a árvore é mostrada;
- Um ancestral direto de um nó é o nó pai, assim como um descendente direto é um nó filho;
- A altura de um nó é a distância entre esse nó e o seu descendente mais afastado;
- Por fim, uma árvore binária é uma árvore onde cada pai não tem mais de dois filhos.
Essas estruturas são simuladas na memória, ou seja, a memória é uma sequência de células de memória endereçáveis, por isso seria inviável organizar os dados como matrizes, listas e árvores, no entanto como essa simulação ocorre já é assunto para outro tópico.
Recursividade
Como você já deve saber um laço de repetição implica repetir um conjunto de instruções até atingir a condição desejada.
Enquanto (condição) Faça (bloco de código) Fim Enquanto
A recursão envolve repetir um conjunto de instruções como uma tarefa em si mesma. Um exemplo muito simples para ficar mais claro é o de uma função que retorna a soma dos números até 0.
Função soma(inteiro num) retorna Inteiro
Inicio Se (num > 0) Então Função_Retorna(num + soma(num - 1)); Senão Função_Retorna(0); Fim_Se Fim
Cada vez que a função é chamada em si mesma, passa a ser executada uma nova cópia desta função em que os parâmetros são independentes da chamada anterior. Essa ideia visa dividir um problema em problemas menores do mesmo tipo através de iterações sucessivas, técnica conhecida como divisão e conquista.
Algoritmo de busca binária
Agora podemos falar sobre o algoritmo de busca binária 😀
Vamos supor que desenvolvemos um programa de busca sequencial, então imagine uma lista contendo 10 nomes onde iremos procurar um nome específico utilizando este programa, Joãozinho por exemplo. Sem muito esforço poderíamos comparar este nome com cada um dos nomes desta lista, ao encontrar, nosso problema está resolvido. A questão é, em quantas etapas isso foi realizado, ou seja, quantas vezes foi necessário comparar um nome com outro sequencialmente para saber se Joãozinho estava na lista? Talvez duas ou então cinco, ou no pior dos casos dez vezes, dependendo da ordem em que os nomes aparecem.
Muito bem, agora vamos pensar em outra situação hipotética, uma lista contendo os títulos de todos os livros de uma biblioteca com um acervo de mais de 100 milhões de itens. Neste caso para encontrar o título desejado você teria duas opções, sentar, tomar um café e aguardar a execução do programa ou encontrar uma solução mais eficiente.
Apesar de tentadora a ideia de ficar sentado tomando um café vamos desenvolver o algoritmo.
A brincadeira funciona assim:
- A busca será um sucesso se encontrarmos o valor que procuramos, caso contrário, será uma falha;
- Não pode haver valores duplicados;
- Começamos a busca vendo se a lista está vazia consultado o valor do nó raiz. Se estiver obviamente a busca falhou. Caso contrário, seguimos para o nó subjacente;
- Sempre que avançamos de um nó para outro devemos obedecer às seguintes regras: se o valor for menor do que o valor de entrada, avançamos para o nó da esquerda, se for maior, avançamos para o nó da direita e se for igual a busca foi um sucesso.
- Isso é tudo!
Vejamos uma implementação em JavaScript:
function ArvoreBinaria() {
this.noRaiz = null;
}
ArvoreBinaria.prototype = {
constructor: ArvoreBinaria,
// Adiciona um novo valor
adicionar: function(valor) {
// Cria um novo objeto para armazenar o valor atual
var novoNo = {
valor: valor,
esq: null,
dir: null
};
var noAtual;
if (this.noRaiz == null) {
// Caso a árvore esteja vazia
this.noRaiz = novoNo;
} else {
noAtual = this.noRaiz;
while (true) {
if (valor < noAtual.valor) {
// Atribuímos um novo nó a esquerda caso não exista
// ou seguimos adiante usando o nó da esquerda como nó atual
if (noAtual.esq == null) {
noAtual.esq = novoNo;
break;
} else {
noAtual = noAtual.esq;
}
} else if (valor > noAtual.valor) {
// Atribuímos um novo nó a direita caso não exista
// ou seguimos adiante usando o nó da direita como nó atual
if (noAtual.dir == null) {
noAtual.dir = novoNo;
break;
} else {
noAtual = noAtual.dir;
}
} else {
break;
}
}
}
},
// Verifica se o valor existe ou não na árvore
contem: function(valor) {
var encontrado = false,
noAtual = this.noRaiz;
while (!encontrado && noAtual) {
// Se o valor é menor que o do nó atual, atribua o nó da esquerda
if (valor < noAtual.valor) {
noAtual = noAtual.esq;
}
// Se o valor é maior que o do nó atual, atribua o nó da direita
else if (valor > noAtual.valor) {
noAtual = noAtual.dir;
}
// Valor do nó atual é igual ao valor passado como parâmetro
else {
encontrado = true;
}
}
return encontrado;
},
// Retorna o número de níveis entre o nó atual e o descendente
// mais afastado, seguindo o caminho mais longo
altura: function(no) {
if (!no) return 0;
var alturaEsq = this.altura(no.esq);
var alturaDir = this.altura(no.dir);
return Math.max(alturaEsq, alturaDir) + 1;
},
// Percorre a árvore e exibe os valores em ordem crescente no console
percorrer: function(no) {
if (no) {
this.percorrer(no.esq);
console.log(no.valor);
this.percorrer(no.dir);
}
},
// O menor é o nó do mais baixo nível a esquerda
menorNo: function(no) {
if (!no) {
return 0;
}
if (no.esq) {
return this.menorNo(no.esq);
}
return no.valor;
},
// O maior é o nó do mais baixo nível a direita
maiorNo: function(no) {
if (!no) {
return 0;
}
if (no.dir) {
return this.maiorNo(no.dir);
}
return no.valor;
}
};
Na classe árvore binária adicionamos 6 métodos. Os métodos adicionar e contem seguem a mesma ideia, isto é, conferir nó por nó dentro do laço de repetição. Note que os outros 4 métodos fazem uso da recursividade e nos dão algumas informações extras sobre a estrutura. Podemos ver o resultado de tudo isso logo abaixo:
var arvore = new ArvoreBinaria(); arvore.adicionar(1); arvore.adicionar(2); arvore.adicionar(7); arvore.adicionar(5); arvore.percorrer(arvore.noRaiz); // 1, 2, 5, 7 arvore.contem(7); // true arvore.maiorNo(arvore.noRaiz); // 7 arvore.menorNo(arvore.noRaiz); // 1 arvore.altura(arvore.noRaiz); // 4
Referências:
compapl.tech.blog 