Árvores em JavaScript: nós, percorridas e fundamento para BST e heaps. Implementação clara com exemplos práticos em Node.js.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
DOM, pastas do SO, menu aninhado — tudo árvore: um nó raiz, filhos, sem ciclo (na teoria). Base pra BST (ep. 12), heap (ep. 9) e trie (ep. 13).
O que você vai aprender:
TreeNode com left e rightPré-requisitos: filas (ep. 5) e arrays (ep. 2).
left e rightÁrvores são uma das estruturas de dados mais fundamentais e poderosas na programação, com árvores a gente pode organizar dados de maneira hierárquica. Esse tipo de estrutura pode ajudar a gente a otimizar processamento de dados, desde a manipulação de sistemas de arquivos até a realização de buscas e ordenações rápidas.
Vamos ver a implementação básica de uma árvore em NodeJS/Javascript e as vantagens de usar essa estrutura.
Uma árvore é composta por nós, com um único nó no topo (o primeiro) que é mais conhecido como raiz. Cada nó pode ter zero ou mais nós filhos, mas apenas um pai, exceto a raiz, que não possui pai. Parece que já complicou né kkkk!
A profundidade de um nó é medida pelo número de arestas entre o nó e a raiz. Árvores são ideais para representar relações hierárquicas e para realizar buscas e inserções eficientes.
Pra gente implementar uma árvore básica precisamos definir uma classe para o nó da árvore e outra para a árvore em si. Aqui está um exemplo simplificado de uma árvore binária:
class TreeNode {
constructor(value) {
this.value = value
this.left = null // Filho à esquerda
this.right = null // Filho à direita
}
}
class BinaryTree {
constructor() {
this.root = null
}
// Métodos para inserir, buscar, percorrer, etc.
}Bora criar a função pra inserir itens na árvore?
insert(value) {
//check for params
const node = new TreeNode(value);
if (this.root === null) {
this.root = node;
} else {
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = node;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = node;
return this;
}
current = current.right;
}
}
}
}Depois do insert vamos "printar" a árvore, então adiciona o print depois do insert:
print() {
return console.log(JSON.stringify(this.__traverse(this.root)));
}
__traverse = (node) => {
const tree = { value: node.value };
tree.left = node.left === null ? null : this.__traverse(node.left);
tree.right = node.right === null ? null : this.__traverse(node.right);
return tree;
};Jon, que raios é esse __traverse?
Então, o traverse é o nome que geralmente se usa quando falamos de "andar pelos nós da árvore", chamamos isso de traverse.
Agora vamos incluir uns itens na árvore e rodar o peão do báu:
const tree = new BinaryTree()
tree.insert(9)
tree.insert(4)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
tree.insert(6)
tree.lookup(6)
tree.print()Se você fez tudo isso aí bonitinho, o resultado do print deve ser algo nessas linhas:
{
"value": 9,
"left": {
"value": 4,
"left": { "value": 1, "left": null, "right": null },
"right": { "value": 6, "left": null, "right": null }
},
"right": {
"value": 20,
"left": { "value": 15, "left": null, "right": null },
"right": { "value": 170, "left": null, "right": null }
}
}Uma observação aqui é, implementamos uma árvore binária, ou seja os elementos maiores que o root vão para direita, os menores para esquerda. Existem outros tipos de árvores que vamos explorar em outros posts.
Árvores são utilizadas para modelar a estrutura de sistemas de arquivos, onde cada diretório é um nó que pode conter arquivos (nós sem filhos) ou outros diretórios (nós com filhos).
Em estruturas como árvores de busca binárias (BST), a gente consegue armazenar, buscar e ordenar dados, com operações de busca, inserção e remoção que, em média, têm tempo de execução logarítmico.
logarítmico?
Quer dizer que o tempo de execução é mais rápido que outras soluções tipo ordenar um array utilizando funções básicas por exemplo bubble-sort.
Inserir 1,2,3,4,5 em BST ingênua vira lista — O(n). Em produção: árvore balanceada ou Map ordenado da runtime.
Recursão profunda em percurso estoura stack — versão iterativa com pilha explícita em árvore muito alta.
| Conceito | Detalhe |
|---|---|
| Binária | no máximo 2 filhos |
| BST | esquerda < nó < direita |
| Percursos | in / pre / post-order |
| Próximo | ep. 12 BST, ep. 7 grafos |
Você precisa implementar árvore de cabeça no trampo ou só reconhecer quando o problema é hierárquico? Comenta — e bug no exemplo JSON da árvore, avisa.
Receba notas de arquitetura e performance na sua caixa de entrada. Mesma lista do convite—inscreva-se aqui quando quiser.
