Procédure de suppression d'un Arbre de Recherche Binaire
D'envisager la suppression de la procédure sur un BST, lorsque le nœud à supprimer a deux enfants. Disons que j'ai toujours le remplacer par le nœud de la tenue de la clé minimale dans son sous-arbre droit.
La question est: est-ce la procédure commutative? Qui est, la suppression de x puis y a le même résultat que la suppression de la première y puis x?
Je pense que la réponse est non, mais je ne peux pas trouver un contre-exemple, ni la figure hors de tout raisonnement.
EDIT:
Peut-être que je dois être plus clair.
Envisager la transplant(node x, node y) la procédure: il remplacer x par y (et sa descendance).
Donc, si je veux supprimer un nœud (par exemple x), qui a deux enfants-je le remplacer par le nœud de la tenue de la clé minimale dans son sous-arbre droit:
y = minimum(x.right)
transplant(y, y.right) //extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)
La question était de savoir comment prouver la procédure ci-dessus n'est pas commutative.
OriginalL'auteur Metz | 2010-06-07
Vous devez vous connecter pour publier un commentaire.
Suppression (en général) n'est pas commutatif. Voici un contre-exemple:
Que si on supprime les 4 puis 3?
Lorsque nous supprimer 4, nous obtenons 6, comme la nouvelle racine:
La suppression de 3 ne change pas l'arbre, mais nous donne ceci:
Que si on supprime les 3 et 4?
Lorsque nous supprimer 3 l'arbre ne change pas:
Cependant, lorsque nous avons maintenant supprimer 4, la nouvelle racine devient 7:
Les deux arbres ne sont pas les mêmes, donc la suppression n'est pas commutative.
Mise à JOUR
Je n'ai pas lu la restriction que c'est quand vous avez toujours supprimer un nœud avec 2 enfants. Ma solution est pour le cas général. Je vais le mettre à jour si/quand je peux trouver un contre-exemple.
UNE AUTRE MISE À JOUR
Je n'ai pas de preuves concrètes, mais je vais hasarder une conjecture:
Dans le cas général, vous gérez les suppressions de façon différente selon que vous avez deux enfants, un enfant, ou pas d'enfants. Dans le contre-exemple que j'ai fourni, j'ai d'abord supprimer un nœud avec deux enfants et puis un nœud avec un enfant. Après, j'ai supprimer un nœud sans enfants, et puis un autre nœud avec un enfant.
Dans le cas spécial de seulement la suppression de nœuds avec deux enfants, vous voulez envisager le cas où les deux nœuds sont dans le même sous-arbre (car il ne serait pas grave si elles sont dans les différents sous-arbres; vous pouvez être sûr que l'ensemble de la structure ne change pas en fonction de l'ordre de suppression). Ce que vous avez vraiment besoin de le prouver est de savoir si la commande de suppression de nœuds d'un même sous-arbre où chaque nœud a deux enfants, des questions.
Tenir compte de deux nœuds A et B, où A est un ancêtre de B. Ensuite, vous pouvez affiner la question de l'être:
Est la suppression commutatif lorsque vous êtes compte tenu de la suppression de deux nœuds d'un Arbre de Recherche Binaire qui ont un ancêtre-descendant relation les uns avec les autres (ce qui signifierait qu'ils sont dans le même sous-arbre)?
Lorsque vous supprimez un nœud (disons), vous traversez le droit de la sous-arborescence pour trouver le minimum de l'élément. Ce nœud est un nœud feuille et ne peut jamais être égal à B (car B a deux enfants et ne peut pas être un nœud feuille). Vous suffira alors de remplacer la valeur de A avec la valeur de ce nœud feuille. Ce que cela signifie, c'est que le seul changement structurel de l'arbre est le remplacement de la valeur avec la valeur du nœud feuille, et la perte de la feuille-nœud.
Le même processus s'est engagé pour B. C'est, vous remplacez la valeur du nœud et de remplacer un nœud feuille. Donc, en général, lorsque vous supprimez un nœud avec deux enfants, le seul changement structurel est le changement de la valeur du nœud à supprimer, et la suppression de la feuille qui est la valeur que vous utilisez en tant que remplacement de la.
Donc, la question est d'autant plus raffinée:
Pouvez-vous garantir que vous obtiendrez toujours le même nœud de remplacement, indépendamment de la commande de suppression (si vous êtes toujours la suppression d'un nœud avec deux enfants)?
La réponse (je pense) est oui. Pourquoi? Voici quelques observations:
Ce n'est pas une preuve rigoureuse; ce sont juste quelques observations que j'ai fait. Par tous les moyens, n'hésitez pas à faire des trous!
Comment la nouvelle racine devenir 7 dans le 2e cas, après la suppression de 4? Ne devrait-elle pas être de 6? Après la suppression de 4, le prochain élément minimum dans la bonne sous-arbre de 4 à 6, de sorte que la racine des modifications à 6? Dans le ci-dessus par exemple. suppression de 3 et 4 ou la suppression de 4 et 3 donne le même résultat. Cependant, je ne suis pas sûr si cela fonctionne comme une règle générale.
Dans le second cas, vous êtes à la suppression de 4. 4 est un nœud avec un enfant. Lorsque vous supprimez un nœud avec un enfant (plus besoin de chercher le bon nœud, puisque vous pouvez être sûr que le seul enfant est plus ou moins grande selon que c'est la droite ou la gauche de l'enfant), vous pouvez remplacer le noeud avec son enfant. Plus d'informations ici: en.wikipedia.org/wiki/Binary_search_tree#Deletion
Comme @Vivin dit, ce n'est pas la suite de la restriction que vous ne supprimez jamais un nœud avec moins de 2 enfants.
Mmh, qui est Fou est droit, qui a été simple, car le deuxième nœud n'y a pas 2 enfants. j'ai décocher vivin de réponse. Je m'excuse pour mon inattention.
OriginalL'auteur Vivin Paliath
Il me semble que le contre-exemple montré dans Vivin la réponse est le seul cas de non-commutativité, et qu'il est en effet éliminé par la restriction que seuls les nœuds avec deux enfants peut être supprimé.
Mais il peut également être éliminé si nous écartons de ce qui semble être l'un des Vivin locaux, qui est que nous devons parcourir le sous-arbre droit aussi peu que possible pour trouver acceptable successeur. Si, au contraire, nous avons toujours de promouvoir le plus petit nœud du sous-arbre droit, en tant que successeur, peu importe à quelle distance il se révèle être situé, à l'époque, même si nous détendre la restriction sur la suppression de nœuds avec moins de deux enfants, Vivin du résultat
n'est jamais atteint, si l'on commence à
Au lieu de cela, il faudrait d'abord supprimer 3 (sans successeur) et ensuite supprimer 4 (avec le 6 en tant que successeur), produisant de
qui est le même que si la commande de suppression ont été inversés.
Suppression serait alors commutative, et je pense que c'est toujours commutatif, compte tenu de la prémisse j'ai nommé (successeur est toujours plus petit nœud en droit de sous-arbre du nœud supprimé).
Je n'ai pas de preuve formelle à offrir, simplement une énumération de cas:
Si les deux nœuds être supprimés sont dans les différents sous-arbres, puis la suppression de l'un n'affecte pas l'autre. Seulement quand ils sont dans le même chemin de la commande de suppression éventuellement affecter le résultat.
Donc aucun effet sur la commutativité ne peut venir que lorsque un ancêtre du nœud et l'un de ses descendants sont à la fois supprimés. Maintenant, comment leur relation verticale affecter la commutativité?
Descendant dans le sous-arbre gauche de l'ancêtre. Cette situation n'affectera pas la commutativité parce que le successeur vient de la droite de la sous-arborescence et ne peut pas affecter le sous-arbre gauche.
Descendant dans le sous-arbre droit de l'ancêtre. Si l'ancêtre du successeur est toujours le plus petit nœud du sous-arbre droit, puis de l'ordre de suppression ne peut pas modifier le choix du successeur, n'importe quel descendant est supprimé avant ou après l'ancêtre. Même si le successeur de l'ancêtre s'avère être le descendant du nœud, qui doit également être supprimé, descendant trop est remplacé par le suivant le plus grand nœud, et descendant ne peut pas avoir ses propres sous-arbre gauche restant à traiter. Si la suppression d'un ancêtre et le droit-sous-arbre descendant sera toujours commutative.
O(log n)dans le pire des cas), à moins que le nœud a deux enfants. Mais avec votre prémisse, il est vrai que la suppression serait commutative, mais avec une augmentation du rendement-coût.OriginalL'auteur brannerchinese
Je pense qu'il y a deux tout aussi viable pour supprimer un nœud, quand il a 2 enfants:
passer À la case 4...
Cas 1: supprimer 3 (nœud Feuille)
2 3
/\ --> / \
1 3 1
Cas 2: supprimer 2 (à Gauche nœud enfant)
2 3
/\ --> / \
1 3 1
Cas 3: supprimer 2 (Droit nœud enfant)
2 2
/\ --> / \
1 3 3
______________________________________________________________________
Cas 4: supprimer 2 (Gauche & Droit de l'enfant de nœuds)
2 2 3
/\ --> / \ / \
1 3 1 3
À la FOIS le TRAVAIL et les différentes résultant des arbres 🙂
______________________________________________________________________
Comme l'algorithme expliqué ici: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html
Deleting a node with 2 children nodes:
1) Replace the (to-delete) node with its in-order predecessor or in-order successor
2) Then delete the in-order predecessor or in-order successor
OriginalL'auteur Jason
Je réponds ici à Vivin deuxième mise à jour.
Je pense que c'est une bonne refonte de la question:
mais cette phrase en gras ci-dessous n'est pas vrai:
depuis le minimum de l'élément dans le sous-arbre droit peut avoir un droit de l'enfant. Il n'est donc pas une feuille.
Appelons le minimum de l'élément dans le sous-arbre droit
successor(A).Maintenant, il est vrai que B ne peut pas être
successor(A), mais il peut l'être dans son sous-arbre droit. Donc, c'est un gâchis.J'ai essayer de résumer.
Hypothèse:
D'autres choses nous pouvons déduire de l'hypothèse:
successor(A), ni Un estsuccessor(B).Maintenant, étant donné que, je pense qu'il y a 4 cas différents (comme d'habitude, laissez-être Un ancêtre de B):
successor(A)successor(A)est un ancêtre de BJe pense (mais bien sûr je ne peux pas le prouver) que les cas 1, 2 et 4 n'ont pas d'importance.
Alors, seulement dans le cas
successor(A)est un ancêtre de B suppression de la procédure ne pouvait pas être commutative. Ou pourrait-il?Je passe la balle : )
Ce qui concerne.
OriginalL'auteur Metz