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

[allomona]

j'aurais du me concentrer avant de répondre vous avez raison un graaand merci

[sorari81]

Bonjour

le principe des ABR c'est que les element decote gauche soient inferieur au racine de sous arbre donc on aura :

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
 
   3
  / \
  2  4

puis 2

Code :

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

1
2
3
      3
                \
                 4

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 le meme arbre :

[sorari81]

Bonjour

le principe des ABR c'est que les element de cote gauche soient inferieur au racine de sous arbre donc on aura :

Code :

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

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

on supprime 1

Code :

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

1
2
3
4
5
6
7
 
   2
    \
 
     4
     /
    3

puis 2

Code :

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

1
2
3
      3
                \
                 4

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
4
 
    3
   / \
  1   4

puis 1

Code :

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

1
2
3
    3
     \
      4

On obtient le même arbre :

[kwariz]

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 :

1. Le noeud est un feuille
   Cas simple, on supprime simplement le lien entre le père et la feuille.
   
2. Le noeud a un seul fils
   Cas simple aussi, on remplace le noeud par son fils
   
3. 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 :

Code :

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

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

L'arbre après suppression de 3 puis 4 est différent de l'arbre après suppression de 4 puis 3.
La brisure de symétrie est obtenue en "transformant" une application de la règle 3 par une des règles 1 ou 2

[Youcef DZ]

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