Implementando Árvore (Tree) com NodeJS e Javascript

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 right
• Inserir e buscar em árvore binária simples
• Percursos in-order, pre-order, post-order
• Quando árvore ≠ objeto JSON aninhado

Pré-requisitos: filas (ep. 5) e arrays (ep. 2).

Árvores em JavaScript: nós, 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.

Implementação

A Teoria

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.

A Prática

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.

Aonde Você pode Usar/Ver

Organização de Sistemas de Arquivos

Á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).

Processamento e Busca de Dados

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.

Edge cases: árvore desbalanceada

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.

TL;DR — Árvore

Próximos passos

• Grafos (ep. 7): conexões sem hierarquia única — Implementando Grafos
• BST (ep. 12): busca ordenada — Árvore de busca binária

Antes de fechar

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.