Comment supprimer un nœud de BST Tree avec 2 enfants?

Question

J'ai googlé, lisez plusieurs tutoriels et j'ai regardé plusieurs explications d'algorithme de suppression du nœud BST avant de poster cette question. Pour une raison quelconque, je ne trouve pas une explication complète des algorithmes de suppression de nœud BST.

J'ai trouvé 4 algorithmes pour retirer le nœud avec 2 enfants de l'arbre de recherche binaire:
1) Trouvez le plus petit nœud du sous-arbre droit et remplacez-le avec le nœud que nous voulons supprimer.
2) Trouvez le plus gros nœud du sous-arbre gauche et remplacez-le avec le nœud que nous voulons supprimer.
3) Trouvez le nœud le plus profond le plus profond du sous-arbre droit et remplacez-le avec le nœud que nous voulons supprimer.
4) Trouvez le nœud le plus profond le plus profond de l'arborescence gauche et remplacez-le avec le nœud que nous voulons supprimer.

Apparemment, aucun de ces algorithmes ne fonctionne pour le prochain cas d'utilisation (probablement parce que je manque ou ne comprenez pas quelque chose). L'étui d'utilisation consiste à éliminer l'élément 5 de l'arborescence suivante:

Pour le premier algorithme, nous choisirions l'élément 6 et perdrait son sous-arbre droit. Pour le deuxième algorithme, nous choisirions l'élément 4 et perdrait son sous-arbre gauche. Pour le 3ème algorithme, nous choisirions l'élément 7 et qui violerait les règles de la BST. Pour le 4ème algorithme, nous choisirions l'élément 3 qui violerait également les règles de la BST.

Quel est le bon algorithme pour un tel cas d'utilisation?

Answer 1

Vous avez raison, en BST, généralement le cas où un nœud a deux enfants est réduit au cas où un nœud a un enfant.

Considérez un nœud avec deux enfants. Échangez ce nœud avec son prédécesseur dans la BST (c'est le nœud le plus à droite dans le sous-arbre de gauche), ou --Totaly symétrique - échangez avec le successeur (le nœud le plus à gauche dans le sous-arbre de droite).

Le nœud à enlever maintenant a maintenant un enfant (au cas où nous allions pour le prédécesseur, il ne peut pas avoir un enfant droit). Si cela n'a aucun enfant, nous supprimons le nœud et nous sommes terminés.

Si le nœud a un seul enfant, nous supprimons le nœud et le remplace par son sous-arbre. Nous obtenons à nouveau une BST.

Dans votre exemple, nous voulons enlever 5 et l'échange avec son prédécesseur 4. Maintenant, 4 est à la racine et 5 a quitté l'enfant 3. Enfin, nous enlevons 5 et mettons son enfant 3 à sa place. Maintenant 3 est le bon enfant de 2.

ps. Cette méthode est parfois appelée "suppression en copiant", car les valeurs sont copiées d'un nœud à un autre. Certains n'approuvent pas ce processus pour deux raisons. La première copie peut être une opération coûteuse et les secondes références sont perdues (si un autre DaSTRubtructure pointe vers un nœud avec une certaine valeur). Au lieu de cela, on ne change que les pointeurs.