Árvore binária de busca
Árvore binária de busca é um experimento interativo de Estruturas de dados, uma simulação gratuita do StudyFi Lab que funciona direto no navegador.
Em cada nó, os valores menores ficam à esquerda e os maiores à direita. Por isso buscar e inserir seguem um único caminho a partir da raiz e custam O(h), onde h é a altura da árvore; numa árvore balanceada h ≈ log₂ n. Remover tem três casos: uma folha simplesmente some, um nó com um filho é substituído por esse filho e um nó com dois filhos recebe o valor do seu sucessor em ordem. O percurso em ordem lista os valores ordenados; árvores parecidas sustentam os índices de bancos de dados.
Experimente: Remova a raiz: ela tem dois filhos, então você verá a busca do sucessor. Depois tente “Inserir valores ordenados”: a árvore degenera numa lista e a altura cresce até n.
Perguntas frequentes
O que mostra o experimento “Árvore binária de busca”?
Em cada nó, os valores menores ficam à esquerda e os maiores à direita. Por isso buscar e inserir seguem um único caminho a partir da raiz e custam O(h), onde h é a altura da árvore; numa árvore balanceada h ≈ log₂ n. Remover tem três casos: uma folha simplesmente some, um nó com um filho é substituído por esse filho e um nó com dois filhos recebe o valor do seu sucessor em ordem. O percurso em ordem lista os valores ordenados; árvores parecidas sustentam os índices de bancos de dados.
Como experimento “Árvore binária de busca”?
Remova a raiz: ela tem dois filhos, então você verá a busca do sucessor. Depois tente “Inserir valores ordenados”: a árvore degenera numa lista e a altura cresce até n.
Estudando para uma prova?
Envie suas anotações e o StudyFi as transforma em flashcards, testes e podcasts.