Discussion :

[allomona]

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.

[LinuxUser]

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.

[allomona]

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??

[kwariz]

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 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    2
   / \
  1   4
     /
    3

Quel arbre obtient-on en supprimant d'abord 1 puis 2 ? Obtient-on le même arbre en supprimant d'abord 2 puis 1 ?

[allomona]

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

[kwariz]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    2
   / \
  1   4
     /
    3

on supprime 1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    2
     \
      4
     /
    3

puis 2

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
      4
     /
    3

Alors que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    2
   / \
  1   4
     /
    3

on supprime 2

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    3
   / \
  1   4

puis 1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    3
     \
      4

On obtient bien deux arbres différents :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
3         4
 \  et   /
  4     3