Buscar é comparar e descer.
Compare o alvo com a raiz atual. Se for menor, siga à esquerda; se for maior, à direita; se for igual, a busca termina. O algoritmo visita no máximo um nó por nível: O(h), sendo h a altura.
voltar à Fase 4/ data structure · bancada 02
Binary Search Tree
Organize valores por decisões esquerda-direita.
LR / 04BST
Como encontrar um valor sem visitar todos os nós?
Em uma árvore binária de busca, valores menores ficam à esquerda e maiores à direita de cada nó.
instrumentação / estado atual
passo01 / 04Começar na raiz
focoraizO alvo 18 é comparado com o primeiro nó.
complexidadeO(log n)caso médio
comparação18 ≠ 8observado agora
/ visualização em execução
frame 01Começar na raiz
8
422
261827
menor ← nó → maior/ decisão observadaO algoritmo compara o estado atual antes de avançar.
Passo 1 · O alvo 18 é comparado com o primeiro nó.
Passo 1: O alvo 18 é comparado com o primeiro nó.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o trabalho tende a crescer quando n, a quantidade de elementos na estrutura, aumenta.
operações
O(log n) · Cortes pela metade
Cada comparação elimina aproximadamente metade das possibilidades. Isso depende de a árvore permanecer razoavelmente balanceada.
Com 16 nós são, no máximo, 4 níveis; com 32, 5. Dobrar a estrutura adiciona apenas um nível.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar operações locais de extremidade com uma decomposição recursiva cujo número de movimentos cresce exponencialmente. Stacks & Queues tende a crescer mais devagar do que Towers of Hanoi quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
/ raciocínio sincronizado
A mesma ideia, três leituras.
01
buscar(no, alvo)02
se no é vazio: retorne falso03
se alvo == no.valor: retorne verdadeiro04
se alvo < no.valor: vá para esquerda05
senão: vá para direitaO destaque acompanha o passo atual; leia a linha destacada antes de avançar.
/ leitura técnica · busca ordenada
A altura decide o custo da busca.
Uma Binary Search Tree não é apenas um desenho de nós: é uma promessa local de ordem. A cada comparação, essa promessa permite descartar uma subárvore inteira e seguir por apenas um caminho.
8
422
menoresmaioresINVARIANTE / PARA CADA NÓ
esquerda < raiz < direita
Para todo nó, todas as chaves da subárvore esquerda são menores que a chave do nó e todas as da direita são maiores. A regra deve continuar verdadeira depois de uma busca, inserção ou remoção; é ela que torna o caminho de decisão confiável.
Inserir preserva a fronteira.
A inserção repete o mesmo caminho de busca até encontrar uma posição vazia. O novo valor entra como folha; não é preciso reorganizar as chaves existentes para manter a invariante.
Remover exige escolher o caso.
- Sem filhos: elimine o nó.
- Um filho: conecte o pai diretamente ao filho.
- Dois filhos: substitua pelo sucessor in-order e remova esse sucessor.
MEDIDA CRÍTICA / ALTURA
hníveis até uma folha
O formato importa mais que o rótulo.
Se a altura cresce como log n, busca, inserção e remoção ficam em O(log n). Inserções aleatórias costumam produzir esse comportamento médio, mas não o garantem.
Inserir valores já ordenados pode formar uma cadeia. Nesse limite, h = n e as mesmas operações passam a custar O(n), como em uma lista.
/ percorrer é escolher uma ordem
O in-order revela a ordenação.
- In-order
- Esquerda, raiz, direita. Em uma BST válida, produz as chaves em ordem crescente.
- Pre-order
- Raiz, esquerda, direita. Útil para registrar a estrutura antes de explorar os ramos.
- Post-order
- Esquerda, direita, raiz. Útil quando os filhos precisam ser processados antes do nó.
/ decidir pela operação dominante
BST não substitui toda estrutura de consulta.
- BST balanceada
- Escolha quando busca ordenada, inserções e consultas de intervalo convivem. Variantes AVL, Red-Black e Splay controlam ou adaptam o balanceamento.
- Hash Table
- Prefira para igualdade de chave, quando a ordem não importa e o acesso médio constante é a prioridade. Ela não entrega o percurso ordenado da árvore.
- Array ordenado
- Funciona bem em conjuntos majoritariamente estáticos: Binary Search é rápida, mas inserir ou remover no meio desloca elementos e tende a custar O(n).