DS & II

Capítulo 13 - Árvores Balanceadas

Leitura de 4 min

🚀 Capítulo 13: Árvores Balanceadas (AVL/Red-Black) (Tema: Star Wars)

NOTE

Este capítulo utiliza a temática de Star Wars para explicar as Árvores Balanceadas. Trazer o equilíbrio para a Força é o mesmo que manter a árvore balanceada para não perder performance!

1. 🎯 Objetivo da Aula

Compreender o problema das árvores binárias desbalanceadas (degeneradas), o conceito de balanceamento e como funcionam as árvores que se auto-balanceiam (como AVL e Red-Black).

2. 🏢 O Cenário Prático (Seu Desafio)

O Mestre Yoda está organizando os arquivos dos aprendizes Jedi. Ele usou uma Árvore Binária de Busca (BST) simples.

  • Os aprendizes foram cadastrados na ordem de idade: 10, 12, 15, 18, 20.
  • Como cada número era maior que o anterior, todos foram para a direita.
  • A árvore virou uma linha reta! Uma fileira de Dominós (ou uma Lista Ligada).

O problema: Para achar o aprendiz de idade 20, o sistema precisa ler todos os outros. A vantagem da árvore sumiu! Seu desafio é trazer o Equilíbrio para a Força (para a árvore) para que a busca volte a ser rápida!

3. 🧠 Fundamentos: A Teoria Traduzida

Uma árvore BST simples é vulnerável à ordem de inserção. Se inserirmos dados já ordenados, ela se torna degenerada (vira uma lista).

⚖️ 1. O que é Balanceamento?

Uma árvore está balanceada quando a altura das subárvores esquerda e direita de qualquer nó não difere em mais de 1 nível.

🔄 2. Árvores Auto-Balanceáveis

Para evitar o problema do Yoda, cientistas criaram árvores que se reorganizam sozinhas a cada inserção. As mais famosas são:

  • Árvore AVL: Garante um balanceamento quase perfeito através de “rotações” dos nós. É mais rígida e ótima para buscas frequentes.
  • Árvore Red-Black: Garante um bom balanceamento pintando os nós de Vermelho ou Preto e seguindo regras de cores. É mais rápida para inserções e deleções.

4. 📖 Exemplo Guiado: A Rotação AVL

Se inserirmos 10, 20, 30 nessa ordem em uma árvore comum: 10 -> 20 -> 30 (Linha reta).

A árvore AVL percebe o desequilíbrio e faz uma Rotação para a Esquerda: O 20 sobe para ser a raiz, o 10 vira filho esquerdo e o 30 vira filho direito! O equilíbrio foi restaurado!

flowchart TD
    A["20"] --> B["10"]
    A --> C["30"]
    style A fill:#f9f,stroke:#333,stroke-width:2px

5. 🛠️ Prática Obrigatória 1: Identificando o Desequilíbrio

Diga se as árvores abaixo estão balanceadas ou não:

  1. Uma raiz com 10 filhos na esquerda e nenhum na direita.
  2. Uma raiz com 5 filhos na esquerda e 4 na direita.
  3. Uma árvore onde todos os nós folhas estão no mesmo nível de profundidade.

6. 🛠️ Prática Obrigatória 2: O Custo do Equilíbrio

Manter a árvore balanceada exige que o computador faça cálculos e mova os nós de lugar (rotações) a cada inserção. Vale a pena gastar esse tempo na inserção para garantir que a busca seja sempre rápida? Em que tipo de sistema isso é mais importante?

7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 13 Estruturas de Dados) e clique em Commit to main.
  2. Envie para a Nuvem (Push): Clique em Push origin.

8. 📂 Estrutura de Pastas

mod_09_estruturas_de_dados/
├── capitulos/
│   ├── capitulo_13_arvores_balanceadas.md
│   └── codigos/
│       └── cap13/
│           └── equilibrio_forca.txt

9. 💡 Checkpoint de Lógica

Se a árvore AVL é mais equilibrada que a Red-Black, por que linguagens como Java e C++ usam a Red-Black para implementar suas estruturas padrão (como o TreeMap)? (Dica: Pense no custo de ficar girando a árvore toda hora).

10. 🔥 Desafio de Fixação

Pesquise o que são as operações de Rotação Simples e Rotação Dupla em uma árvore AVL.

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. Não balanceada (Diferença de altura muito grande).
  2. Balanceada (Diferença de altura é apenas 1).
  3. Perfeitamente balanceada.

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks