La suppression dans un arbre binaire de recherche est-elle commutative dans le sens où la suppression de x puis de y produit le même arbre que la suppression de y puis de x.
La suppression dans un arbre binaire de recherche est-elle commutative dans le sens où la suppression de x puis de y produit le même arbre que la suppression de y puis de x.
Je dirai que ça dépends des cas.
Si x et y sont des feuilles, ça n'a pas d'importance, par contre si ceux sont des noeuds l'ordre a une importance.
merci por votre réponse, je suis d'accord que si les noeuds sont des feuilles la suppression est intuitivement commutative mais si elles sont des racines on dirait qu'elle n'est pa commutative sans aucun doute n'est ce pas??
Bonjour,
le plus simple est d'exhiber un contre exemple par exemple avec :
Quel arbre obtient-on en supprimant d'abord 1 puis 2 ? Obtient-on le même arbre en supprimant d'abord 2 puis 1 ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
Pour cet exemple le resultat est le meme que ce soit on supprime le 1 puis le 2 ou bien le 2 puis le 1 on obtient dans les 2 casun arbre ayant 4 pour racine et 3 feuille de cette racine mais ça ne confirme pas la commutativité faut essayer sur un arbre ayant plusieuurs feuilles
on supprime 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
puis 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 \ 4 / 3
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 4 / 3
Alors que :
on supprime 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
puis 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 / \ 1 4
On obtient bien deux arbres différents :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 \ 4
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 4 \ et / 4 3
j'aurais du me concentrer avant de répondre vous avez raison un graaand merci
Bonjour
le principe des ABR c'est que les element decote gauche soient inferieur au racine de sous arbre donc on aura :
on supprime 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
puis 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 3 / \ 2 4
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 \ 4
Alors que :
on supprime 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
puis 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 / \ 1 4
On obtient le meme arbre :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 \ 4
Bonjour
le principe des ABR c'est que les element de cote gauche soient inferieur au racine de sous arbre donc on aura :
on supprime 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 2 / \ 1 4 / 3
puis 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 2 \ 4 / 3
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 \ 4
Alors que :
on supprime 2
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 2 / \ 1 4 / 3
puis 1
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 3 / \ 1 4
On obtient le même arbre :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 3 \ 4
Bonsoir Sorari81,
Je ne vais prendre en compte que ton dernier post. L'algo classique de suppression d'une valeur dans un ABR se déroule en deux phases : d'abord on cherche le noeud à supprimer, si on le trouve alors on le supprime. La suppression en elle-même prend en compte trois cas de figure :
- Le noeud est un feuille
Cas simple, on supprime simplement le lien entre le père et la feuille.- Le noeud a un seul fils
Cas simple aussi, on remplace le noeud par son fils- Le noeud a deux fils
On cherche la plus petite valeur du sous arbre droit, le noeud à supprimer prend cette plus petite valeur et on supprime le noeud ayant contenu cette plus petite valeur (on se retrouve forcément dans une situation 1 ou 2)
En suivant l'algo classique on obtient bien deux arbres différents dans mon exemple. Le fait de remplacer le choix du plus petit élement du sous arbre droit par le choix du plus grand du sous arbre gauche ne changera pas grand chose ; dans ce cas tu peux essayer avec :
L'arbre après suppression de 3 puis 4 est différent de l'arbre après suppression de 4 puis 3.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 3 / \ 1 4 \ 2
La brisure de symétrie est obtenue en "transformant" une application de la règle 3 par une des règles 1 ou 2
Bonjour à tous
vouse avez un arbre BB comemnt faire la suppression dans cette arbre :::
S.V.P la réponsse aprée 8-12-2014
Merci
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager