Implementando Árvores (Trees) com NodeJS e Javascript

Árvores

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

Dicas

• Ao implementar árvores, especialmente árvores de busca binárias, presta atenção para manter a árvore balanceada, a fim de otimizar o desempenho das operações de busca, inserção e remoção.
• Implemente as funções traverse (in-order, pre-order e post-order) para explorar os dados armazenados de maneira eficiente.
• Considere o uso de estruturas de árvores especializadas, como AVL, Red-Black Trees, Tries para aplicações que exigem alta eficiência em operações dinâmicas.

Considerações do Jon

Ao contrário do que muitos pensam (principalmente em algumas entrevistas por aí) eu não acho que você precisa saber implementar uma árvore de cabeça, do nada. Mas saber identificar e entender os conceitos base de como funciona uma estrutura de árvore, isso sim, faz sentido. Conseguimos utilizar Árvores em varios tipos de aplicações, de sistemas de arquivos a estruturas de dados dinâmicas, até sistemas de recomendação de produtos, etc, então é legal saber identificar quando estamos usando e quando podemos usar esse tipo de estrutura.

E Você?!

Já criou/utilizou algo parecido nos seus projetos ou no seu trampo? Compartilhe aqui nos comentários suas dúvidas, se já fez, experiências, desafios, dicas, etc!! Vamos explorar esses conceitos juntos, ah e se viu algum bug, erro, melhoria, também comenta aí!