Operação de remoção em BST §

---

A remoção de um elemento em uma árvore de busca binária é uma operação que pode ser feita de diferentes maneiras, dependendo da estrutura dos filhos do nó que será removido.

1. Nó a ser removido é um nó folha §

A remoção de um nó folha é a situação mais simples. Basta eliminar o nó da árvore e ajustar o ponteiro do seu nó pai para apontar para NULL.

Exemplo §

Remover o nó 4 da árvore abaixo:

      6
     / \
    4   8

Aqui, basta ajustar o campo left do nó 6 para apontar para NULL:

      6
       \
        8

2. Nó a ser removido possui somente um filho §

Se o nó a ser removido tiver apenas um filho, o processo de remoção é feito conectando o nó pai diretamente ao filho do nó removido.

Ou seja, o filho do nó removido assume o lugar do nó na árvore.

Exemplo: §

Remover o nó 10 da árvore abaixo:

      8
       \
        10
          \
           14

Neste caso, o nó 10 tem apenas um filho (nó 14). Para remover 10, basta fazer com que o nó 8 aponte diretamente para 14:

      8
       \
        14

3. O Nó a ser removido possui dois filhos §

Quando o nó a ser removido tem dois filhos, a remoção é mais complexa, pois precisamos reorganizar a árvore para manter a propriedade da árvore de busca binária.

A solução é encontrar o nó cuja chave é mais próxima do nó removido, o que pode ser feito de duas maneiras:

• Usar o menor valor da subárvore direita (o sucessor) do nó a ser removido.
• Usar o maior valor da subárvore esquerda (o antecessor).

Geralmente, é mais comum utilizar o sucessor, que é o nó de menor valor na subárvore à direita.

Exemplo: §

Remover o nó 3 da árvore abaixo:

      5
     / \
    3   8
   / \
  2   4

Para remover o nó 3, devemos encontrar o sucessor. O menor valor na subárvore à direita de 3 é o nó 4. O nó 4 substitui 3, mantendo a estrutura da árvore:

      5
     / \
    4   8
   /
  2

Referências §

---

Aula 2 - TAD Árvores Binárias e BST