Considérez la procédure de suppression sur une BST, lorsque le nœud à supprimer a deux enfants. Disons que je le remplace toujours avec le nœud tenant la clé minimale dans son sous-arbre de droite.
La question est la suivante: cette procédure est-elle commutative? C'est-à-dire que la suppression de x puis y a le même résultat que de supprimer le premier y, puis x?
Je pense que la réponse est non, mais je ne trouve pas de contre-exemple, ni de déterminer un raisonnement valable.
EDIT:
Peut-être que je dois être plus clair.
considère la transplantation La question était Comment prouver la procédure ci-dessus n'est pas commutative. (noeud x, nœud y) procédure : Il remplace X avec Y (et son sous-arbre).
Donc, si je veux supprimer un nœud (dire x) qui a deux enfants, je le remplace par le nœud qui détient la clé minimale dans son sous-arbre de droite:
4 Réponses :
Suppression (en général) n'est pas commutative. Voici un contre-exemple: Et si nous supprimons 4, puis 3? Strong> P> Lorsque nous supprimons 4, nous obtenons la nouvelle ROOT: P> 7
/
6
Oh, oui, c'était assez simple. Merci!
Comment la nouvelle racine est-elle devenue 7 dans la 2e cas après avoir supprimé 4? Ne devrait-il pas être 6? Après avoir supprimé 4, l'élément minimum suivant dans le sous-arbre de droite de 4 est 6, de sorte que la racine passe à 6? Dans ce qui précède par exemple. La suppression des 3 et 4 ou la suppression de 4 et 3 donne le même résultat. Cependant, je ne suis pas sûr que cela fonctionne comme une règle générale.
Dans le second cas, vous supprimez 4. 4 est un nœud avec un enfant. Lorsque vous supprimez un nœud avec un enfant (pas besoin de rechercher le nœud droit, car vous pouvez être sûr que le seul enfant est inférieur ou plus grand selon qu'il s'agisse de l'enfant droit ou de gauche), vous pouvez remplacer le nœud avec son enfant. Plus d'informations Ici: en.wikipedia.org/wiki/binary_search_tree#deletion
Comme @vivin a dit, cela ne suit pas la restriction que vous ne supprimez jamais un nœud avec moins de 2 enfants.
MMH, Mad a raison, c'était simple parce que le deuxième nœud n'a pas 2 enfants. Je délie à la réponse de Vivin. Je m'excuse pour mon inattention.
@Metz, je m'excuse pour mon inattention - n'a pas lu la restriction que c'est pour deux enfants. Je pensais que c'était le cas général. :)
@VivinPaliaThe Si vous conservez la même règle dans les deux cas qui choisissent toujours le plus grand sous-arbre gauche ou choisissez le plus petit de la sous-arbre de droite pour le remplacement ..
je réponds ici à la deuxième mise à jour Vivin.
Je pense que cela est une bonne refonte de la question:
est-commutative de suppression lorsque vous êtes compte tenu de la suppression de deux nœuds à partir d'un binaire arbre de recherche qui ont un relation descendant ancêtre l'autre (cela impliquerait qu'ils sont dans le même sous-arbre)?
mais cette phrase en gras ci-dessous n'est pas vrai:
Lorsque vous supprimez un nœud (disons A), vous traversez le sous-arbre droit à trouver l'élément minimum. Ce nœud sera un nœud feuille et ne peut jamais être égal à B
depuis l'élément minimum dans un sous-arbre droit de peut avoir un enfant droit . Donc, ce n'est pas une feuille. Appelons l'élément minimum dans un sous-arbre droit
successeur (A) . Maintenant, il est vrai que B ne peut pas êtresuccesseur (A) , mais il peut être dans son sous-arbre droit. Ainsi, il est un gâchis.J'essaie de résumer.
Hypothesis :
- A et B ont deux enfants chacun.
- A et B sont dans la même sous-arbre.
Autres choses nous pouvons en déduire l'hypothèse:
- B est non
successeur (A) , ni A estsuccesseur (B) .Maintenant, étant donné que, je pense qu'il ya 4 différents cas (comme d'habitude, nous allons être un ancêtre de B):
- B est en sous-arbre gauche de A
- B est un ancêtre de
successeur (A)successeur (A) est un ancêtre de B- B et successeur (A) n'ont aucune relation. (Ils sont différents des sous-arbres de A)
Je pense (mais bien sûr, je ne peux pas le prouver) que les cas 1, 2 et 4 importent peu. Ainsi, seulement dans le cas
successeur (A) est un ancêtre de la procédure de suppression B ne pouvait pas être commutative. Ou pourrait-il?I passer le ballon:)
Cordialement.
Il me semble que le contre-extexample montré dans la réponse de Vivin est le seul cas de non-négutativité, et qu'il est effectivement éliminé par la restriction que seuls les nœuds de deux enfants peuvent être supprimés.
Mais il peut également être éliminé si nous éliminons ce qui semble être l'un des locaux de Vivin, ce qui est que nous devrions traverser le bon sous-arbre à la fois possible pour trouver tout successeur acceptable. Si, au lieu de cela, nous promouvons toujours le noeud le plus petit du sous-arbre de droite comme successeur, peu importe la distance qui s'avère être située, alors même si nous détendons la restriction sur la suppression de nœuds avec moins de deux enfants, le résultat de Vivin
N'a jamais atteint si nous commençons à à la place, nous supprimerons d'abord 3 (sans successeur), puis la suppression de 4 (avec 6 comme successeur) , cédant
lequel est identique à ce que l'ordre de suppression a été inversé. La suppression serait alors commutative, et je pense que c'est toujours commutatif, donné La prémisse que j'ai nommée (le successeur est toujours le plus petit nœud de la sous-arbre de droite du nœud supprimé). Je n'ai pas de preuve formelle à offrir, simplement une énumération de cas: Si les deux nœuds à supprimer sont dans différents sous-arbres, la suppression de l'un n'affecte pas l'autre. Seulement quand ils sont dans le même chemin, l'ordre de suppression affecte éventuellement l'issue.
N'importe quel effet sur la commutativité ne peut venir que lorsqu'un nœud ancêtre et un de ses descendants sont tous deux supprimés. Maintenant, comment leur relation verticale affecte-t-elle la commutativité?
descendant dans le sous-arbre de droite de l'ancêtre. Si le successeur de l'ancêtre est toujours le plus petit nœud de la sous-arbre de droite, alors l'ordre de suppression ne peut pas changer le choix du successeur, peu importe ce que Le descendant est supprimé avant ou après l'ancêtre. Même si le successeur de l'ancêtre s'avère être le nœud descendant qui doit également être supprimé, que le descendant est également remplacé par le nœud le plus proche, et que le descendant ne puisse pas avoir son propre sous-arbre à gauche restant à être traité. . La suppression d'un ancêtre et de tout descendant de la sous-arbre de droite sera toujours commutative.
L'exemple de la non-négocitivité que j'ai fournie est basé sur l'algorithme de suppression standard; Lorsqu'un nœud n'a qu'un seul enfant, il peut être supprimé et remplacé par ce nœud enfant. Dans mon cas 4 n'a qu'un seul enfant (7) et peut donc être remplacé par cet enfant. C'est parce que nous n'avons pas vraiment besoin de traverser toute la hauteur du sous-arbre (coûte O (journal n) dans le pire des cas) sauf si le nœud a deux enfants. Mais avec votre principe, il est vrai que la suppression serait commutative mais avec un coût de performance accru.
Je pense qu'il y a deux façons aussi viables de supprimer un nœud, quand il a 2 enfants:
Skip to case 4 ...
cas 1: Supprimer 3 (nœud feuille)
2 3
/ \ -> / \
1 3 1
cas 2: Supprimer 2 (nœud enfant gauche)
2 3
/ \ -> / \
1 3 1
cas 3: Supprimer 2 (nœud d'enfant droit)
2 2
/ \ -> / \
1 3 3
Cas 4: Supprimer 2 (nœuds d'enfants de gauche et droite)
2 2 3
/ \ -> / \ ou / \
1 3 1 3
travaille à la fois et avoir des arbres différents résultants :)
______________________________________________________________________
Comme algorithme expliqué ici: HTTP : //www.mathcs.emory.edu/~cheung/courses/323/Syllabus/trees/avl-Delete.html
Suppression d'un nœud avec 2 nœuds pour enfants:
1) Remplacez le nœud (TO-Supprimer) avec son prédécesseur dans l'ordre ou son successeur en ordre
2) Supprimez ensuite le prédécesseur ou le successeur dans l'ordre dans l'ordre