Binary Search Tree - suppression de noeuds

Question

J'essaie de comprendre pourquoi lorsque vous supprimez un noeud dans une arborescence BST et que vous devez conserver les enfants et adhérer à la structure BST, vous devez soit prendre l'enfant droit du noeud (valeur plus élevée, puis le noeud étant supprimé) et si cet enfant a un enfant à gauche, prenez cet enfant. Sinon, le noeud est supprimé directement enfant.

Pourquoi ne prenez-vous pas simplement le noeud en cours de suppression enfant de gauche, s'il y en a un. Cela fonctionne encore correctement?

Ou ai-je raté quelque chose?

Je suis en train de lire l'article this.

Answer 1

Vous simplifiez à l'extrême.

Le nœud sélectionné pour remplacer celui qui a été supprimé doit être plus grand que tous les nœuds à gauche de celui supprimé et plus petit que tous les nœuds à droite. Il doit donc s'agir du descendant le plus à droite du sous-arbre gauche ou du descendant le plus à gauche du sous-arbre droit; sauf si l'un ou l'autre des sous-arbres est entièrement absent, nous pouvons entièrement supprimer un niveau d'arbre en remplaçant le nœud supprimé par l'enfant qui était présent.

Les règles répertoriées dans l'article vous donneront toujours le descendant le plus à droite du sous-arbre lorsque les deux arbres sont présents. Si vous le souhaitiez, vous pouviez en effet dériver un jeu de règles alternatif qui utilisait le descendant le plus à droite du sous-arbre le plus à gauche.

Il ne fonctionne pas correctement pour utiliser toujours l'enfant de gauche. En effet, s'il y a un enfant à droite et que l'enfant à gauche a deux enfants, cela ne peut même pas être fait sans reconstruire essentiellement l'arbre.

Answer 2

Vous auriez raison pour le cas particulier que vous avez décrit. Mais pour quelque chose de plus général où vous pouvez avoir beaucoup plus de niveaux plus profonds que le nœud à supprimer, vous devez remplacer ce nœud par un nœud qui sera inférieur à tout à droite, et supérieur à tout à gauche. Ainsi, à titre d'exemple:

2 
/\ 
1 6 
    /\ 
    4 7 
    \ 
    5 

Disons que vous vouliez déplacer le nœud 6, suivant vos instructions maintenant nous le remplacer par l'enfant gauche, noeud 4. Maintenant que faisons-nous avec le noeud 5? Nous pourrions en faire l'enfant gauche du noeud 7 (ou le descendant le plus à gauche du noeud 7 s'il existait), mais pourquoi referiez vous tout ce remaniement quand vous saurez que enlever une feuille est trivial et vous voulez juste remplacer le nœud avec un autre nœud qui garderait chaque nœud sur la gauche moins et chaque nœud sur la droite plus grand.