Árvores binárias de pesquisa

Invariante global

Cada nó exige que toda a subárvore esquerda tenha chaves menores e toda a direita tenha chaves maiores. Esta página usa chaves únicas: a igualdade não cria um nó novo.

• Comparações locais não chegam. Numa árvore com raiz 8, filho esquerdo 4 e filho direito de 4 com chave 9, cada ligação pai-filho parece ordenada, mas o 9 está na subárvore esquerda de 8 e viola o invariante.

• Valida com limites abertos herdados. Não uses x-1 nem x+1.

• Pesquisa desce um só lado em $O(h+1)$. Vazio prova ausência.

• Inserir para em filho vazio. Igualdade não muda o conjunto.

Cadeia dá altura n-1. Inserir as chaves pela ordem das medianas recursivas minimiza a altura: ordena primeiro e insere a mediana, depois as medianas das metades.

Retirar sem partir a ordem

Nó tem	Faz
Zero filhos	Liga vazio e liberta
Um filho	Liga o filho e liberta
Dois filhos	Copia o sucessor e apaga o sucessor

Sucessor é o mínimo da direita e não tem esquerdo, mas pode ter direito: religa-o. Atualiza a raiz quando for preciso.

Em-ordem final [1,6,7,8].

Intervalos e biblioteca

• Sucessor sem direita é o primeiro antepassado vindo da esquerda. Pode não existir.
• Enumerar k chaves com poda custa $O(\log n+k)$.
• set e map pesquisam em logaritmo. find não insere; map[k] cria se faltar.
• lower_bound(x) é o primeiro >=x; upper_bound(x) o primeiro >x. Podem ser end().

Contratos completos.