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.
Version imprimable
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,Citation:
Envoyé par allomona
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:
2
3
4
5
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
Citation:
Envoyé par allomona
on supprime 1Code:
2
3
4
5
puis 2Code:
2
3
4
5
Code:
2
3
Alors que :
on supprime 2Code:
2
3
4
5
puis 1Code:
2
3
On obtient bien deux arbres différents :Code:
2
3
Code:
2
3
:oops: 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 1Code:
2
3
4
5
puis 2Code:
2
3
4
Code:
2
3
Alors que :
on supprime 2Code:
2
3
4
5
puis 1Code:
2
3
On obtient le meme arbre :Code:
2
3
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 1Code:
2
3
4
5
62 / \ 1 4 / 3
puis 2Code:
2
3
4
5
6
7
Code:
2
3
Alors que :
on supprime 2Code:
2
3
4
5
puis 1Code:
2
3
43 / \ 1 4
On obtient le même arbre :Code:
2
3
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:
2
3
4
5
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:roll::roll:
Merci