# Árvores binárias de pesquisa

Ordem global das subárvores, procura, inserção e remoção com sucessor.

Página: https://resumos.rgo.pt/cadeiras/aed/arvores-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.

![Antes, raiz 3 com filhos 1 e 8; 8 tem filho esquerdo 6 e 6 tem filho direito 7. Depois, raiz 6 com filhos 1 e 8, e 7 à esquerda de 8. O filho do sucessor permanece na árvore.](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/figura-1.svg)

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.

## Exercícios

As justificações e os programas em C++ são de autoavaliação. Compara o raciocínio com os critérios da solução.

Remover dois filhos com sucessor

Insere numa BST simples \[9,4,13,2,7,11,15,10\]. Remove 9 usando o sucessor. Dá a nova raiz e a em-ordem.

Pista

O sucessor é o mínimo da subárvore direita.

Mais uma pista

O caminho 13->11->10 encontra esse mínimo.

Solução

A nova raiz tem chave 10; retira a antiga folha 10 da esquerda de 11. A em-ordem é \[2,4,7,10,11,13,15\] e as restantes ligações não mudam. O sucessor é maior que toda a esquerda e menor que as restantes chaves da direita, por isso a ordem global conserva-se. O custo total é O(h+1).

Confere a tua resposta:

*   Escolhi 10, o mínimo da direita, como nova chave da raiz.
*   Retirei o nó antigo com 10, sem duplicar a chave.
*   Obtive em-ordem 2,4,7,10,11,13,15 e conservei a ordem global.

Erros frequentes

Não escolhas simplesmente o filho direito 13; não deixes duas cópias de 10 se a BST usa chaves únicas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/#remover-uma-chave)

Detetar uma ordem inválida

A raiz é 20, o filho esquerdo é 8 e o filho direito de 8 é 25. Os restantes filhos são vazios. É uma BST de chaves únicas? Justifica com limites.

Pista

O limite da raiz também se aplica a todos os descendentes esquerdos.

Mais uma pista

O nó 25 tem de estar no intervalo aberto (8,20).

Solução

Não é uma BST, porque 25 excede o limite superior 20 herdado. As comparações entre pai e filho isoladamente são insuficientes. Propagar limites abertos valida todos os nós em O(n), com espaço O(h+1) numa recursão.

Confere a tua resposta:

*   Rejeitei a árvore porque 25 está na esquerda de 20.
*   Propaguei ao nó 25 o intervalo aberto (8,20).
*   Distingui comparações locais da condição sobre toda a subárvore.

Erros frequentes

Não concluas validade só porque 8<20 e 25>8; evitar x+1 e x-1 também evita overflow nos limites extremos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/#invariante-de-ordem-global)

Religar o filho do sucessor

Insere `[3,1,8,6,7]` numa BST vazia, com chaves únicas. Remove 3 usando o sucessor. Desenha a árvore antes e depois, mostra a ligação que evita perder 7 e dá a em-ordem final.

Pista

O sucessor não tem filho esquerdo.

Solução

Antes, 3 tem filhos 1 e 8; o filho esquerdo de 8 é 6, e 6 tem filho direito 7. O mínimo da direita de 3 é 6. Copia 6 para a raiz e substitui `8.esquerdo` por 7 antes de libertar o antigo nó 6. Depois, a raiz 6 tem filhos 1 e 8, com 7 à esquerda de 8. A em-ordem é `[1,6,7,8]`. Perder 7 violaria a pós-condição de remover apenas 3, mesmo que a ordem entre os nós sobreviventes continuasse válida.

Confere a tua resposta:

*   Copiei o sucessor para o nó removido.
*   Liguei o filho direito do sucessor ao seu pai.
*   Verifiquei a em-ordem final.

Erros frequentes

Apagar o sucessor sem transplantar o filho direito perde uma subárvore.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/#remover-uma-chave)

Construir a menor e a maior altura

Insere as chaves distintas `{2,5,8,11,14,17,20}` numa BST simples, inicialmente vazia. Dá uma ordem de inserção que maximize a altura e outra que a minimize, desenhando as ligações. Justifica os dois extremos. Na primeira árvore, o mínimo tem de estar numa folha?

Solução

Inserir `[2,5,8,11,14,17,20]` cria a cadeia direita com seis arestas, altura 6, o máximo para sete nós. O mínimo 2 é a raiz e tem filho direito, logo não é folha. Inserir `[11,5,17,2,8,14,20]` cria raiz 11, filhos 5 e 17, com folhas 2 e 8 sob 5, 14 e 20 sob 17. A altura é 2. Altura 1 só permite três nós; sete exigem pelo menos altura 2. Escolher medianas recursivamente e inserir cada raiz antes dos seus descendentes atinge esse limite.

Confere a tua resposta:

*   Construí uma cadeia de altura 6 e uma árvore de altura 2.
*   Justifiquei o mínimo pela capacidade de cada altura e insiro a raiz antes dos descendentes.
*   Mostrei que o mínimo pode ter filho direito e não ser folha.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/#ordem-de-inser%C3%A7%C3%A3o-e-altura)