1) Por que árvores? O que as tornam indispensáveis

Árvores são estruturas de dados hierárquicas que modelam relações de dependência e hierarquia de forma natural. Elas organizam dados de maneira que inserções, buscas e remoções possam ocorrer com eficiência, mantendo propriedades úteis como ordenação e agrupamento lógico.

Princípios-chave:
– Representação explícita de hierarquia: nós com referências a filhos.
– Travessias estruturadas: pré-ordem, em-ordem, pós-ordem e level-order.
– Desempenho escalável: operações próximas de O(log n) em árvores balanceadas.

2) Estruturas de árvore: representação, nós e propriedades

Uma árvore genérica tem nós conectados por arestas, com uma raiz que dá origem a ramos e folhas. Em implementações práticas, escolhemos a forma de representação que facilita acessos e mutabilidade.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
            

3) Percursos de árvores e complexidade

Travessias são operações centrais para inspeção, serialização e reconstrução de estruturas. Considerando uma árvore binária com n nós:

• Pré-ordem, em-ordem e pós-ordem: tempo O(n); espaço O(h) devido à pilha/recursão.
• Level-order: tempo O(n); espaço O(width) da árvore, geralmente O(n) no pior caso.

Observação: árvores não balanceadas podem degenerar em estruturas lineares, elevando a altura h para O(n) e degradando o desempenho.

4) Árvores balanceadas e aplicações práticas

Para manter desempenho estável em operações dinâmicas, as árvores balanceadas mantêm a altura logarithmica. Principais famílias:

• AVL: balanceamento estrito com rotações para manter a altura em O(log n).
• Red-Black: balanceamento mais flexível, com garantias de altura ainda logarítmica.
• B-Tree/B+Tree: otimizadas para acesso a disco, utilizadas em bancos de dados e sistemas de arquivos.

Notas práticas:
– Em cenários concorrentes, considere imutabilidade parcial para facilitar sincronização.
– Escolha a árvore com base no perfil de acesso: leituras sequenciais, atualizações frequentes ou operações transacionais com disco.

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new BSTNode(value);
    if (!this.root) {
      this.root = node;
      return this;
    }
    let curr = this.root;
    while (true) {
      if (value === curr.value) {
        // ignorar duplicatas
        return this;
      }
      if (value < curr.value) {
        if (!curr.left) {
          curr.left = node;
          return this;
        }
        curr = curr.left;
      } else {
        if (!curr.right) {
          curr.right = node;
          return this;
        }
        curr = curr.right;
      }
    }
  }

  contains(value) {
    let curr = this.root;
    while (curr) {
      if (value === curr.value) return true;
      curr = value < curr.value ? curr.left : curr.right;
    }
    return false;
  }
}