Simulic
Português

Árvores binárias de busca – inserção, busca, remoção e percursos

ComputaçãoAlgoritmos e resolução de problemasIdades 17–18

Carregando…

Usar com minha turma ✨ Personalizar com IA Relatar um problema

Insira, busque e remova chaves em uma árvore binária de busca e acompanhe o caminho de comparações por cada nó, a altura da árvore e o número de comparações; remover um nó com 0, 1 ou 2 filhos usa o sucessor em ordem. Inserir chaves ordenadas faz a árvore degenerar em uma lista, e uma tabela de resultados compara isso com ordens de inserção aleatória e balanceada. Um modo Percurso em árvore avança passo a passo pelos percursos pré-ordem, em ordem, pós-ordem e em nível, e um modo Árvore de expressão mostra as notações prefixa, infixa e pós-fixa.

Aula: Árvores binárias e árvores binárias de busca; percursos pré-ordem, em ordem, pós-ordem e em largura; árvores de expressão e notação polonesa

O que mostra

Em uma árvore binária de busca, as chaves da subárvore esquerda são menores e as da direita são maiores que a chave do nó; assim, buscar, inserir e remover seguem um único caminho desde a raiz e precisam de no máximo h + 1 comparações, em que h é a altura. Ordens de inserção aleatórias geram árvores baixas, mas uma entrada ordenada produz uma cadeia tão lenta quanto a busca sequencial. Os percursos visitam cada nó uma vez: os percursos em profundidade usam a pilha de chamadas de uma função recursiva, o percurso em nível usa uma fila e, nas árvores de expressão, geram as notações prefixa, infixa e pós-fixa.

Como usar

No modo Árvore binária de busca, digite uma Chave e clique em Inserir, Buscar ou Remover; as comparações aparecem passo a passo. Escolha uma Ordem de inserção e um Número de chaves e clique em Nova árvore para adicionar uma linha à tabela comparativa. No modo Percurso em árvore, escolha um Percurso e clique em Reproduzir ou Passo. No modo Árvore de expressão, escolha uma expressão ou digite a sua.

Parâmetros que você pode mudar

  • Modo Árvore binária de busca, Percurso em árvore, Árvore de expressão
  • Ordem de inserção inicial Aleatória, Crescente (ordenada), Chave do meio primeiro (balanceada)
  • Número inicial de chaves 3–15 chaves
  • Chaves iniciais a inserir (números de 1 a 99, ex.: 50 30 70; vazio = geradas)
  • Percurso Pré-ordem (NLR), Em ordem (LNR), Pós-ordem (LRN), Em nível (BFS)
  • Expressão de exemplo (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, Personalizada
  • Expressão personalizada (vazio = usar a expressão de exemplo)
  • Velocidade de execução 0,5–4 passos/s

Perguntas para explorar

  1. Qual é a altura da árvore quando sete chaves são inseridas em ordem crescente, e quantas comparações encontram a maior chave?
  2. Por que o percurso em ordem de uma árvore binária de busca sempre lista as chaves em ordem crescente?
  3. Como se escreve (3 + 4) * 5 em notação pós-fixa, e por que os parênteses não são necessários?

Simulações relacionadas