Árvore Viva
Uma árvore 3D que cresce a cada número ou pasta inserida. A busca desce pelos galhos contando comparações; compare a árvore equilibrada com a torta e descubra o caminho de um arquivo.
Como usar
Números (árvore de busca): digite um número e use “Inserir”. Ele entra pela raiz e desce pelos galhos: se for menor que o número do nó, vai para a esquerda; se for maior, vai para a direita. Onde encontrar um lugar vazio, nasce um nó novo. “Buscar” faz o mesmo caminho e conta quantas comparações foram precisas.
Pastas (sistema de arquivos): escolha uma pasta, dê um nome e crie um arquivo ou uma pasta dentro dela. Clique num arquivo para ver o caminho completo dele, ou use “Procurar pelo nome” para ver o computador olhando pasta por pasta.
Arraste o fundo da cena para girar; use a roda do mouse ou dois dedos para aproximar. Pelo teclado: Tab até a cena, setas giram e as teclas + e − aproximam. Todos os comandos também estão nos botões, e a árvore aparece em texto no painel.
Árvore de busca
Pastas e arquivos
- nó com filhos
- folha (nó sem filhos)
- visitado na busca
- encontrado
- pasta
- arquivo
- pasta escolhida para criar
- visitado na busca
- encontrado
Desafios
- Monte uma árvore de busca com 7 números em apenas 3 níveis.
- Insira 6 números de um jeito que a árvore vire um galho só, com 6 níveis.
- Busque um número que não está na árvore. Quantas comparações bastaram para ter certeza?
- No modo Pastas, crie um arquivo a 3 pastas de profundidade e descubra o caminho completo dele.
Para o professor
O que está por trás: uma árvore é um grafo sem ciclos, com um único caminho da raiz até cada nó. Na árvore de busca binária, cada nó guarda um número; tudo o que está à esquerda é menor e tudo o que está à direita é maior. Por isso, para achar um número, basta descer um caminho: o número de comparações é no máximo a quantidade de níveis. Uma árvore equilibrada com 7 números tem 3 níveis (e com 1.000 números, cerca de 10); se os números chegam já em ordem, a árvore vira um galho só e a busca fica tão lenta quanto olhar a lista inteira. Visto de frente, os nós aparecem da esquerda para a direita em ordem crescente: é o percurso “em ordem”. O modo Pastas mostra outra árvore do dia a dia: o sistema de arquivos. Quem sabe o caminho (Documentos/Escola/prova.pdf) vai direto; quem só sabe o nome precisa olhar pasta por pasta. Na Computação, as árvores costumam ser desenhadas com a raiz em cima; o botão “Raiz em cima” vira a árvore.
Metodologia sugerida: investigação em duplas, depois de jogar a Estante da Busca Binária. Uma dupla insere os números em ordem e outra embaralhada, e as duas comparam a altura das árvores. Use com o plano Árvores de decisão e grafos.
- Com os números 1, 2, 3, 4, 5, 6 e 7, em que ordem é preciso inserir para a árvore ficar com só 3 níveis? Existe mais de uma ordem?
- Numa árvore com 3 níveis, qual é o maior número de comparações de uma busca? E numa árvore torta com 7 níveis?
- Por que, no computador, não pode haver dois arquivos com o mesmo nome na mesma pasta, mas pode em pastas diferentes?
- Que outras árvores aparecem no dia a dia? (Árvore genealógica, chaveamento de campeonato, organograma, sumário de um livro.)
Habilidades: EF09CO01 (árvores e grafos) e EF06CO08 (armazenar e recuperar arquivos). Material concreto equivalente: cartões numerados colocados no chão com barbante para os galhos, ou caixas de sapato dentro de caixas maiores para as pastas.