DS & II

Capítulo 12 - Árvores Binárias de Busca

Leitura de 4 min

🚀 Capítulo 12: Árvores Binárias de Busca (BST) (Tema: Stranger Things)

NOTE

Este capítulo utiliza a temática de Stranger Things para explicar as Árvores Binárias de Busca. Para encontrar o portal para o Mundo Invertido, você precisa seguir a regra: números menores para a esquerda, maiores para a direita!

1. 🎯 Objetivo da Aula

Compreender o conceito de Árvore Binária de Busca (Binary Search Tree - BST) e a regra fundamental de ordenação que permite buscas extremamente rápidas.

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

Dustin está tentando rastrear portais interdimensionais em Hawkins. Cada portal tem uma frequência numérica.

  • Para organizar os dados e não precisar buscar portal por portal (Busca Linear), ele decide usar uma Árvore Binária de Busca.
  • A regra é simples: Ele começa no portal central (Raiz). Se o novo portal tiver frequência menor, vai para o ramo da esquerda. Se for maior, vai para o ramo da direita.

Seu desafio é ajudar o Dustin a inserir novas frequências nessa árvore e encontrar o portal certo para resgatar o Will!

3. 🧠 Fundamentos: A Teoria Traduzida

Uma Árvore Binária de Busca é uma árvore onde cada nó tem, no máximo, dois filhos (Esquerdo e Direito) e segue uma regra rígida de organização:

📜 A Regra de Ouro da BST:

Para qualquer nó da árvore:

  1. Todos os valores na sua subárvore esquerda devem ser MENORES que o valor do nó.
  2. Todos os valores na sua subárvore direita devem ser MAIORES que o valor do nó.

⚡ Por que isso é rápido?

Porque a cada comparação você elimina metade da árvore! Se você procura o número 30 e a raiz é 50, você já sabe que o 30 só pode estar na esquerda. Você nem precisa olhar o lado direito. Isso dá um tempo de busca de .

4. 📖 Exemplo Guiado: Construindo a Árvore

Vamos inserir as frequências: 50, 30, 70, 20, 40

  1. 50 entra primeiro (Vira a Raiz).
  2. 30 é menor que 50 → Vai para a Esquerda.
  3. 70 é maior que 50 → Vai para a Direita.
  4. 20 é menor que 50 (esquerda), menor que 30 → Esquerda do 30.
  5. 40 é menor que 50 (esquerda), maior que 30 → Direita do 30.
flowchart TD
    A["50"] --> B["30"]
    A --> C["70"]
    B --> D["20"]
    B --> E["40"]
    style A fill:#f9f,stroke:#333,stroke-width:2px

5. 🛠️ Prática Obrigatória 1: Inserindo Elementos

Com base na árvore do exemplo guiado, onde ficariam os seguintes elementos se fossem inseridos agora?

  1. O número 60.
  2. O número 80.
  3. O número 10.

6. 🛠️ Prática Obrigatória 2: Buscando o Portal

Imagine que você está procurando o número 40 na árvore acima.

  1. Qual é o primeiro nó que você compara?
  2. Para qual lado você vai em seguida?
  3. Quantas comparações você fez no total até achar o 40?

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

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 12 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_12_bst.md
│   └── codigos/
│       └── cap12/
│           └── bst_portais.js

9. 💡 Checkpoint de Lógica

O que acontece se tentarmos inserir um número que já existe na árvore? As árvores BST padrão geralmente não permitem duplicatas (ou colocam na direita/esquerda como padrão fixo).

10. 🔥 Desafio de Fixação

Pesquise o que acontece com a velocidade de busca se inserirmos os números já ordenados (ex: 10, 20, 30, 40, 50) em uma BST. (Dica: Ela vai parecer uma árvore ou uma lista ligada?).

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. 60: Menor que 70 → Esquerda do 70.
  2. 80: Maior que 70 → Direita do 70.
  3. 10: Menor que 50, menor que 30, menor que 20 → Esquerda do 20.

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks