Muito se fala sobre árvores binárias, especialmente sobre a inversão dessas estruturas. Mas o que isso realmente significa? Quais são as consequências dessa operação? E, antes de tudo, o que é uma árvore binária? Neste artigo, quero começar do princípio e, passo a passo, chegar até o tão mencionado, e muitas vezes temido, processo de inversão de árvores binárias. 😊

A ideia não é se aprofundar no tema, mas sim contextualizá-lo e fornecer uma direção sobre o assunto.

Primeiro, o que é uma Árvore Binária?

Uma árvore binária é uma estrutura de dados hierárquica composta por nós, em que cada nó pode ter no máximo dois filhos: um filho à esquerda e um filho à direita. Essa estrutura é amplamente utilizada em computação para organizar dados de forma eficiente, permitindo buscas, inserções e remoções rápidas.

Principais conceitos de uma árvore binária:

• Raiz (root): O primeiro nó da árvore.
• Nós (nodes): Elementos da árvore que podem conter um valor e apontar para filhos.
• Filho esquerdo e filho direito: Cada nó pode ter até dois filhos.
• Folha (leaf): Um nó que não possui filhos.
• Altura da árvore: O maior número de arestas (conexões) do nó raiz até uma folha.

Tipos de árvores binárias:

Árvore binária cheia: Todos os nós possuem exatamente dois filhos ou nenhum.
Árvore binária completa: Todos os níveis da árvore estão completamente preenchidos, exceto possivelmente o último, onde os nós estão o mais à esquerda possível.
Árvore binária balanceada: A diferença de altura entre a subárvore esquerda e a subárvore direita de qualquer nó é pequena (geralmente 0 ou 1).
Árvore de busca binária (BST – Binary Search Tree): Uma árvore binária onde o nó à esquerda sempre contém valores menores e o nó à direita, valores maiores.

E de onde vem as Árvores Binárias?

As árvores binárias têm sua origem no campo da teoria das estruturas de dados e remontam aos primeiros estudos sobre organização eficiente de informações em computação. A ideia de uma estrutura hierárquica para armazenar dados surgiu no contexto da matemática e da lógica computacional, mas ganhou popularidade com os primeiros avanços em ciência da computação.

Origens e evolução:

1. Teoria dos Grafos (século XVIII-XIX)

• As árvores são um caso especial de grafos, um conceito matemático formalizado por Leonhard Euler no século XVIII.
• No século XIX, Arthur Cayley estudou árvores como modelos matemáticos, especialmente em química e contagem de moléculas.

2. Surgimento na Computação (década de 1950-1960)

• Com o avanço da computação, as árvores começaram a ser usadas para organização de dados e busca eficiente.
• Claude Shannon e George Boole desenvolveram ideias de lógica binária, que influenciaram estruturas hierárquicas como árvores.
• John von Neumann e outros pioneiros ajudaram a modelar o armazenamento de dados em estruturas semelhantes a árvores.

3. Formalização como estrutura de dados (década de 1960-1970)

• Donald Knuth, um dos maiores nomes da ciência da computação, descreveu formalmente as árvores binárias e seus algoritmos em seu livro The Art of Computer Programming (1968).
• Durante esse período, surgiram aplicações como árvores binárias de busca (BSTs) e variações como árvores AVL e Red-Black.

Desde então, árvores binárias evoluíram e são usadas em bancos de dados, inteligência artificial, compressão de dados (árvore de Huffman) e muitas outras áreas.

Como vocês podem ver, como quase tudo em tecnologia, árvores binárias também cheiram a naftalina 🙂

Vamos a prática!

Aqui está um exemplo de como criar uma árvore binária usando Typescript

Vamos criar uma árvore binária de busca (BST – Binary Search Tree), que mantém os valores ordenados.

Criar a estrutura do nó da árvore

Cada nó da árvore precisa armazenar um valor, um filho esquerdo e um filho direito.

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Criar a classe da árvore binária

Agora, criamos a classe BinarySearchTree, que conterá métodos para inserir, buscar e exibir os elementos.

class BinarySearchTree {
  root: TreeNode | null;

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

Implementar o método de inserção

O método insert() adiciona um novo valor à árvore seguindo as regras da BST:

• Se for menor que o nó atual, vai para a esquerda.

• Se for maior que o nó atual, vai para a direita.

insert(value: number): void {
  const newNode = new TreeNode(value);

  if (this.root === null) {
    this.root = newNode;
    return;
  }

  let current = this.root;
  while (true) {
    if (value < current.value) {
      if (current.left === null) {
        current.left = newNode;
        return;
      }
      current = current.left;
    } else {
      if (current.right === null) {
        current.right = newNode;
        return;
      }
      current = current.right;
    }
  }
}

Implementar o método de busca

Este método verifica se um valor está presente na árvore.

search(value: number): boolean {
  let current = this.root;

  while (current !== null) {
    if (value === current.value) return true;
    current = value < current.value ? current.left : current.right;
  }

  return false;
}

Implementar a exibição da árvore (em-ordem)

A busca em ordem (in-order traversal) imprime os valores de forma ordenada (menor → maior).

inOrderTraversal(node: TreeNode | null = this.root): void {
  if (node !== null) {
    this.inOrderTraversal(node.left);
    console.log(node.value);
    this.inOrderTraversal(node.right);
  }
}

Testar a árvore

Agora, vamos criar uma instância da árvore e testar os métodos:

const bst = new BinarySearchTree();

bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.insert(7);

console.log("Busca pelo número 7:", bst.search(7)); // true
console.log("Busca pelo número 20:", bst.search(20)); // false

console.log("Elementos ordenados:");
bst.inOrderTraversal(); // Saída: 2, 5, 7, 10, 15

Resumo do que fizemos

1. Criamos a classe TreeNode para representar os nós.

2. Criamos a classe BinarySearchTree para armazenar a raiz da árvore.

3. Implementamos a inserção de valores.

4. Implementamos a busca de valores.

5. Criamos a função de exibição da árvore em ordem crescente.

6. Testamos a árvore binária com valores.

Mas uma árvore binária também pode estar desbalanceada, o que isso significa?

Uma árvore binária desbalanceada pode ter ramos muito profundos em relação a outros, o que prejudica a eficiência das operações de busca, inserção e remoção. O objetivo de balanceamento é garantir que a árvore tenha uma profundidade mais uniforme, evitando que se torne parecida com uma lista encadeada.

Para resolver isso precisamos balancear essa árvore

Passo 1: Identificar se a Árvore Está Desbalanceada

Uma árvore está desbalanceada quando:

• Os ramos são muito profundos de um lado e rasos do outro.

• A diferença de altura entre as subárvores esquerda e direita (fator de balanceamento) é maior que 1.

A altura de um nó pode ser calculada assim:

E o fator de balanceamento é:

Se o fator de balanceamento for maior que 1 ou menor que -1, o nó está desbalanceado.

Passo 2: Extração dos Valores da Árvore

Antes de balancear a árvore, precisamos coletar todos os seus valores. Para isso, usamos um percurso in-order (esquerda → raiz → direita), que extrai os valores de forma ordenada.

Código para extração

function extractValues(node: TreeNode | null, values: number[] = []): number[] {
  if (node !== null) {
    extractValues(node.left, values);
    values.push(node.value);
    extractValues(node.right, values);
  }
  return values;
}

Esse método extrai todos os valores da árvore em uma lista.

Passo 3: Construir uma Árvore Balanceada

Agora que temos os valores ordenados, podemos reconstruir a árvore usando a técnica do Binary Search Tree (BST) balanceado. Escolhemos o elemento do meio da lista como raiz e repetimos o processo para as subárvores esquerda e direita.

Código para construção da árvore balanceada

function buildBalancedBST(sortedValues: number[], start: number = 0, end: number = sortedValues.length - 1): TreeNode | null {
  if (start > end) return null; // Base da recursão

  const mid = Math.floor((start + end) / 2);
  const node = new TreeNode(sortedValues[mid]);

  node.left = buildBalancedBST(sortedValues, start, mid - 1);
  node.right = buildBalancedBST(sortedValues, mid + 1, end);

  return node;
}

Esse método garante que a árvore seja balanceada, pois:

• A raiz será sempre o nó do meio.

• Os elementos menores ficam na esquerda e os maiores na direita.

• A recursão distribui os nós de maneira uniforme.

Passo 4: Aplicando a Transformação

Agora unimos tudo em uma função que balanceia qualquer árvore binária.

Código Completo abaixo

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Extrair valores em ordem crescente
function extractValues(node: TreeNode | null, values: number[] = []): number[] {
  if (node !== null) {
    extractValues(node.left, values);
    values.push(node.value);
    extractValues(node.right, values);
  }
  return values;
}

// Construir a árvore balanceada
function buildBalancedBST(sortedValues: number[], start: number = 0, end: number = sortedValues.length - 1): TreeNode | null {
  if (start > end) return null;

  const mid = Math.floor((start + end) / 2);
  const node = new TreeNode(sortedValues[mid]);

  node.left = buildBalancedBST(sortedValues, start, mid - 1);
  node.right = buildBalancedBST(sortedValues, mid + 1, end);

  return node;
}

// Função que balanceia a árvore
function balanceTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  const values = extractValues(root);
  return buildBalancedBST(values);
}

// Criando uma árvore desbalanceada
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(30);
root.left.left = new TreeNode(22);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(45);
root.right.right.right = new TreeNode(67);
root.right.left.right = new TreeNode(16);
root.left.left.left = new TreeNode(2);

// Balanceando a árvore
const balancedRoot = balanceTree(root);

// Função para imprimir a árvore ordenada
function inOrderTraversal(node: TreeNode | null): void {
  if (node !== null) {
    inOrderTraversal(node.left);
    console.log(node.value);
    inOrderTraversal(node.right);
  }
}

console.log("Árvore balanceada:");
inOrderTraversal(balancedRoot);

Passo 5: Testando o Código

A árvore original estava desbalanceada, e agora podemos balanceá-la chamando:

const balancedRoot = balanceTree(root);

Saída esperada:

Árvore balanceada:
2
5
7
10
15
16
22
30
45
67

O que aconteceu?

Extraímos os valores da árvore usando um percurso in-order.
Ordenamos os valores extraídos (caso não estejam ordenados).
Criamos uma nova árvore BST balanceada, escolhendo sempre o elemento do meio como raiz.

E agora por último, o grande astro do nosso artigo, a inversão da árvore!

Inversão de Árvore Binária: O que é e por que é importante?

A inversão de uma árvore binária é o processo de trocar os filhos esquerdo e direito de todos os nós da árvore. Ou seja, a subárvore esquerda vira a subárvore direita e vice-versa.

Por que a inversão de árvore binária é importante?

1. Teste de lógica e recursão

Esse problema é muito comum em entrevistas de emprego porque testa a capacidade do candidato de entender recursão e manipulação de estruturas de dados.

2. Fundamentos de Árvores

As árvores são essenciais em computação (bancos de dados, sistemas de arquivos, inteligência artificial). A inversão mostra que você entende como navegar e modificar árvores.

3. Uso em imagens e gráficos

Inverter uma árvore pode ser útil para espelhar imagens, renderizar gráficos tridimensionais ou processar redes neurais.

Passo a Passo para Inverter uma Árvore Binária

A ideia principal é trocar os filhos esquerdo e direito recursivamente para todos os nós da árvore.

Passo 1: Definir a Estrutura da Árvore

Usamos a mesma estrutura que já criamos antes:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Passo 2: Criar a Função de Inversão

A inversão funciona assim:

1. Se o nó for nulo, retornamos null.

2. Trocamos os filhos esquerdo e direito.

3. Chamamos a inversão recursivamente para os filhos.

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null; // Se a árvore for vazia, não há nada para inverter

  // Troca os nós esquerdo e direito
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // Chama recursivamente para os filhos esquerdo e direito
  invertTree(root.left);
  invertTree(root.right);

  return root; // Retorna a árvore invertida
}

Passo 3: Criar e Inverter uma Árvore Binária

Agora, usamos a mesma árvore de antes para aplicar a inversão.

// Criando a árvore binária original
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(30);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(45);
root.right.right.right = new TreeNode(67);
root.right.left.right = new TreeNode(16);
root.left.left.left = new TreeNode(22);

// Função para imprimir a árvore In-Order (esquerda, raiz, direita)
function inOrderTraversal(node: TreeNode | null): void {
  if (node !== null) {
    inOrderTraversal(node.left);
    console.log(node.value);
    inOrderTraversal(node.right);
  }
}

console.log("Árvore Original:");
inOrderTraversal(root);

// Invertendo a árvore
const invertedRoot = invertTree(root);

console.log("Árvore Invertida:");
inOrderTraversal(invertedRoot);

Passo 4: Testando a Inversão

A árvore original antes da inversão:

        10
       /  \
      5    30
     / \   /  \
    2   7 15  45
   /       \    \
  22       16   67

Agora, a árvore invertida fica assim:

        10
       /  \
      30    5
     /  \   /  \
    45   15 7   2
   /    /       \
  67   16       22

Saída esperada no console:

Árvore Original:
22
2
5
7
10
15
16
30
45
67

Árvore Invertida:
67
45
30
16
15
10
7
5
2
22

Analisando a Eficiência do Código

A função invertTree() percorre cada nó uma única vez, então sua complexidade de tempo é O(n), onde n é o número de nós da árvore.

• Espaço de memória: O(h) (altura da árvore), devido à chamada recursiva na pilha.

• Melhor caso: Uma árvore perfeitamente balanceada tem altura log(n).

• Pior caso: Se a árvore for uma lista encadeada (totalmente desbalanceada), a altura será O(n).

Por que essa questão aparece tanto em entrevistas?

Bom… testa conhecimento de árvores 🥲

Árvores são uma estrutura fundamental em computação.

As empresas querem saber se você consegue navegar e modificar árvores.

Exige conhecimento de recursão

Muitas pessoas acham recursão difícil, então essa questão filtra candidatos que sabem lidar com chamadas recursivas.

Problema simples, mas desafiador

Parece um problema simples, mas exige pensamento lógico.

Muitas empresas (Google, Meta, Amazon) gostam desse problema porque mostra clareza de pensamento.

E como Aprender?

Bom, não existe um segredo ou bala de prata 😢

Entender árvores binárias pode parecer desafiador no início, mas com a abordagem certa e prática constante, você dominará esse conceito fundamental da ciência da computação. Aqui está um guia passo a passo para te ajudar nessa jornada:

1. Fundamentos Teóricos:

• Conceitos básicos:
  • Comece compreendendo a terminologia: nós, raiz, filhos, folhas, altura, profundidade.
  • Visualize diferentes tipos de árvores binárias: completas, cheias, balanceadas.
• Teoria dos grafos:
  • Familiarize-se com a relação entre árvores binárias e grafos.
  • Entenda como as propriedades dos grafos se aplicam às árvores binárias.

2. Implementação e Prática:

• Escolha uma linguagem de programação:
  • Python, Java, Javascript, Typescript, C++, etc..
  • Implemente árvores binárias do zero, sem usar bibliotecas prontas.
• Operações básicas:
  • Aprenda a realizar operações essenciais: inserção, busca, exclusão, travessia (inordem, pré-ordem, pós-ordem).
  • Pratique essas operações em diferentes tipos de árvores binárias.
• Árvores binárias de busca (BSTs):
  • Entenda como as BSTs organizam os dados para busca eficiente.
  • Implemente algoritmos de busca, inserção e exclusão em BSTs.
• Árvores balanceadas:
  • Explore árvores AVL e árvores rubro-negras, que garantem desempenho otimizado.
  • Compreenda os algoritmos de balanceamento e pratique sua implementação.

3. Recursos e Materiais:

• Livros:
  • “Estruturas de Dados e Algoritmos com JavaScript” da Loiane Groner.
  • “Estruturas de Dados e Algoritmos em C” de Michael T. Goodrich, Roberto Tamassia, David M. Mount.
  • “Algoritmos: Teoria e Prática” de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
• Cursos online:
  • Coursera, edX e Udemy oferecem cursos de estruturas de dados e algoritmos.
  • Plataformas como o leetcode e o hackerrank, podem auxiliar na prática de algoritmos que usam árvores binárias.
• Recursos online:
  • Visite sites como GeeksforGeeks e Tutorialspoint para tutoriais e exemplos de código.
  • Aproveite vídeos no YouTube para visualizações e explicações passo a passo.

4. Visualize Árvores Binárias

• Use ferramentas de visualização para entender como as árvores funcionam:
  • Visualgo
  • BinaryTreeVisualizer
• Desenhe árvores manualmente para fixar o conceito.

---

Lembre-se, a chave para o sucesso é a prática consistente e a aplicação dos conceitos em problemas reais.

---

Dica, gosto muito dessa playlist sobre Estrutura de Dados com Java do professor Leandro Guarino, é muito didática e você poderá aprender não só sobre arvores binárias mas também sobre todas as demais estruturas que são usadas no desenvolvimento de software, é um excelente back to the basics 🙂
E mesmo que você não saiba java pode ser de grande proveito, pois os conceitos apresentados valem para qualquer linguagem.

---

Bom era isso pessoas, espero que tenha ajudado, muito obrigada pela leitura! =D

2