Árvores binárias de pesquisa

Numa árvore binária de pesquisa, ou BST, todas as chaves da subárvore esquerda são menores que a chave do nó e todas as da direita são maiores. Esta página usa chaves únicas. Outra política pode guardar um contador por chave, mas tem de ajustar inserção, remoção e tamanho.

Assume os percursos da página anterior e os intervalos semiabertos da pesquisa binária. A novidade é a ordem global mantida por rotações e limites herdados.

Invariante de ordem global

Não basta comparares um nó com os seus filhos diretos. Na árvore com raiz 8, filho esquerdo 4 e filho direito de 4 com chave 9, cada ligação pai-filho parece ordenada, mas 9 está na subárvore esquerda de 8 e viola o invariante.

Para validares, propaga limites abertos: a esquerda de x fica com limite superior x, e a direita fica com limite inferior x. Não uses x-1 e x+1 em inteiros extremos. Em cada nó, verifica a chave contra os limites herdados de todos os antepassados.

O percurso em-ordem visita chaves por ordem crescente: por hipótese indutiva, as duas subárvores produzem sequências crescentes; todas as chaves à esquerda vêm antes da raiz e todas à direita depois. O argumento depende da propriedade global.

Procurar e inserir

Compara o alvo com a raiz. Se for igual, encontraste. Se for menor, só a esquerda pode contê-lo; se maior, só a direita. Ao chegares ao vazio, a chave falta. A cada passo, o invariante é que qualquer ocorrência ainda possível está na subárvore atual.

Inserir segue o mesmo caminho até um filho vazio e cria aí uma folha. O percurso acumulou limites que a nova chave satisfaz, por isso a inserção conserva a ordem. Se encontrares uma chave igual, a política de conjunto não altera a árvore.

Inserir [8,3,12,1,6,10,14] cria uma árvore de altura 2. Procurar 6 visita 8, 3 e 6; procurar 5 visita 8, 3 e 6, depois o filho esquerdo vazio de 6. Encontrar o mínimo consiste em seguir filhos esquerdos; o máximo segue direitos.

O custo é $O(h+1)$, com h a altura. Numa árvore equilibrada é $O(\log(n+1))$; numa cadeia é $O(n)$. Inserir chaves crescentes numa BST simples produz uma cadeia. A altura esperada é logarítmica com uma ordem de inserção uniformemente aleatória de chaves distintas; essa hipótese não é uma garantia para dados arbitrários.

Ordem de inserção e altura

Para um conjunto de n chaves distintas, a maior altura possível é n-1. Inserir por ordem crescente cria apenas filhos direitos; por ordem decrescente, apenas esquerdos. São duas maneiras de construir uma cadeia, sem alterar as regras da BST.

Para minimizar a altura, ordena as chaves e insere primeiro uma mediana; depois as medianas das duas metades, repetindo até inserir todas. Em [2,5,8,11,14,17,20], uma ordem possível é [11,5,17,2,8,14,20]. A árvore final tem altura 2, o mínimo, pois altura 1 só permite três nós. A ordem crescente dos mesmos sete valores dá altura 6.

O mínimo de uma BST não precisa de ser folha: não tem filho esquerdo, mas pode ter direito. Na cadeia crescente anterior, o mínimo 2 é a raiz e tem filho 5. A definição de mínimo exclui chaves menores, sem excluir chaves maiores abaixo dele.

Remover uma chave

Primeiro procura a chave. Se faltar, a árvore mantém-se. No nó encontrado, há três casos:

1. Nenhum filho: substitui a ligação que chega ao nó por vazio e liberta-o.
2. Um filho: substitui essa ligação pelo único filho e liberta o nó antigo. A subárvore continua dentro dos limites herdados.
3. Dois filhos: encontra o sucessor, o mínimo da subárvore direita. Copia a sua chave, e o respetivo valor se existir, para o nó a remover; depois remove o sucessor da subárvore direita. Esse sucessor não tem filho esquerdo, pelo que a segunda remoção cai num caso simples.

Na árvore construída com [8,3,12,1,6,10,14], remover 8 substitui a raiz por 10, o mínimo da direita. A antiga folha 10 sai da esquerda de 12 e a em-ordem fica [1,3,6,10,12,14].

Para ver o caso em que o sucessor tem filho, considera outra árvore: raiz 3, filho esquerdo 1 e filho direito 8; 8 tem filho esquerdo 6, e 6 tem filho direito 7. Ao remover 3, copia 6 para a raiz e substitui 8.esquerdo por 7. A em-ordem final é [1,6,7,8]. Apagar o antigo 6 sem religar 7 perderia uma subárvore. Se usares o predecessor, o máximo da esquerda, a forma final pode diferir e continuar correta.

O sucessor é maior que todas as chaves da esquerda e não é maior que qualquer outra chave da direita. Por isso a substituição conserva a ordem global. O caminho para achar o sucessor e remover o nó continua limitado pela altura: tempo $O(h+1)$, não $O(h^2)$.

Com multiplicidades, retirar uma ocorrência pode apenas reduzir o contador. Ao transplantares o sucessor, não deixes a mesma chave repartida por dois nós se o invariante usa comparações estritas. Uma remoção da raiz também tem de atualizar o apontador da raiz, não apenas um campo de um pai inexistente.

Limites, intervalos e biblioteca

O sucessor de uma chave tem dois casos: se existir subárvore direita, é o seu mínimo; caso contrário, é o primeiro antepassado em cujo ramo esquerdo está a chave. O predecessor é simétrico. A ausência de sucessor para o máximo é um resultado válido.

Para enumerares chaves num intervalo, descarta subárvores fora dos limites e visita em-ordem as restantes. Numa árvore equilibrada, uma consulta por intervalo com k resultados pode custar $O(\log n+k)$. Fazer um percurso completo e filtrar custa $O(n)$ e perde essa vantagem quando k é pequeno.

std::set representa um conjunto ordenado e std::map associa um valor a cada chave. Em ambos, pesquisa, inserção e remoção por chave têm custo logarítmico. map.find(chave) consulta sem inserir, ao contrário de map[chave], que cria um valor por omissão se a chave faltar.

multiset admite valores repetidos. Na ficha 08 (2025/26), count(valor) conta ocorrências e erase(valor) apaga todas. Para apagar só uma, passa a erase um iterador devolvido por find, depois de confirmares que não é end(). Com m ocorrências numa coleção de tamanho n, contar ou apagar todas custa $O(\log n+m)$.

lower_bound(x) encontra o primeiro valor >=x e upper_bound(x) o primeiro >x; podem devolver end(). Percorrer o intervalo entre ambos conta os repetidos, mas os iteradores destas árvores não admitem subtração como os de um vetor. A equivalência é definida pelo comparador, não obrigatoriamente por operator==. O padrão garante os contratos e custos, sem exigir uma espécie concreta de árvore.

A comparação de chaves e a cópia dos valores contam. Com strings compridas, a análise de uma consulta pode incluir o custo de cada comparação.