Como excluir um nó da árvore da BST com 2 filhos?

Question

Eu googled, leia vários tutoriais e assisti várias explicações de algoritmo de exclusão do Nó BST antes de postar esta pergunta. Por algum motivo, não consigo encontrar uma explicação completa dos algoritmos de exclusão do Nó BST.

Eu encontrei 4 algoritmos para remover o nó com 2 crianças da árvore de pesquisa binária:
1) Encontre o menor nó da sub-árvore direita e substitua-o pelo nó que queremos excluir.
2) Encontre o maior nó da sub-árvore esquerda e substitua-o pelo nó que queremos excluir.
3) Encontre o mais profundo nó mais à esquerda da sub-árvore direita e substitua-o pelo nó que queremos excluir.
4) Encontre o mais profundo nó mais à direita da sub-árvore esquerda e substitua-o pelo nó que queremos excluir.

Aparentemente, nenhum desses algoritmos funciona para o próximo caso de uso (mais provável porque estou faltando ou não entendo alguma coisa). O caso de uso é remover o elemento 5 da próxima árvore:

Para o primeiro algoritmo que escolheríamos o elemento 6 e perderia sua sub-árvore direita. Para o segundo algoritmo, escolheríamos o elemento 4 e perderia a sub-árvore esquerda. Para o terceiro algoritmo, escolheríamos elemento 7 e que violaria as regras da BST. Para o 4º algoritmo, escolheríamos o elemento 3 que também violaria as regras da BST.

Qual é o algoritmo certo para tal caso de uso?

Answer 1

Você está certo, no BST geralmente o caso em que um nó tem duas crianças é reduzido ao caso em que um nó tem uma criança.

Considere um nó com dois filhos. Troque este nó com seu antecessor no BST (ou seja, o nó mais à direita na subárvore esquerdo), ou --totalmente simétrico-- troca com o sucessor (o nó mais à esquerda na subárvore direita).

O nó a ser removido agora tem no máximo um filho (caso fomos para o antecessor que não pode ter uma criança certa). Se não tiver filhos, eliminamos o nó, e terminamos.

Caso o nó tenha uma única criança, removemos o nó e substituí-lo por sua subárvore. Nós novamente obtemos um BST.

No seu exemplo, queremos remover 5 e trocar com o seu predecessor 4. Now 4 está na raiz e 5 deixou a criança 3. Finalmente removemos 5 e colocamos sua criança 3 em seu lugar. Agora 3 é a criança certa de 2.

ps. Este método é às vezes chamado de "exclusão por copiando", porque os valores são copiados de um nó para outro. Alguns não aprovam esse processo por dois motivos. A primeira cópia pode ser uma operação cara e segundas referências são perdidas (se outra fonte apontar para um nó com um determinado valor). Em vez disso, um só muda os ponteiros.