Arbre binaire [Résolu/Fermé]

Signaler
Messages postés
9
Date d'inscription
mardi 29 janvier 2013
Statut
Membre
Dernière intervention
30 janvier 2013
-
 guywiz -
Bonjour,
l'opération de suppression dans un arbre binaire de recherche est-elle commutative dans le sens ou la suppression de x puis y dans un arbre binaire de recherche produit le meme arbre que la suppression de y puis de x.


4 réponses

Messages postés
16055
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 octobre 2020
2 696
Ça dépend comment tu fais ton équilibrage, mais je dirais que dans le cas général cette propriété n'est pas garantie par les seules propriétés des arbres de recherche.

Exemple (suppression de 2 et 4)

   4         4        5   
 2   6     1   6    1   6 
1 3 5 7     3 5 7    3   7
                          
   4         3        3   
 2   6     2   6    1   6 
1 3 5 7   1   5 7      5 7
La confiance n'exclut pas le contrôle
Messages postés
9
Date d'inscription
mardi 29 janvier 2013
Statut
Membre
Dernière intervention
30 janvier 2013

merciii kx
Bonjour , Mais pourquoi il a choisi de remplacer le noeud 2 par le fils gauche (1), pouquoi pas le fils droit ..???
Messages postés
16055
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 octobre 2020
2 696
peu importe, le but de mon exemple était justement de montrer qu'il y avait plusieurs solutions possibles. Si tu remplaces le noeud 2 par le fils droit 3 tu vas te retrouver avec un 3è résultat correct, mais il y a encore d'autres résultats possibles.

   4         4        5   
 2   6     3   6    3   6 
1 3 5 7   1   5 7  1     7
mais on doit suivre le même algo de suppression de deux noeuds successifs !!!!
Messages postés
16055
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 octobre 2020
2 696
"on doit suivre le même algo de suppression"
Dans le cas général, rien ne t'y oblige...

On pourrait très bien coder la suppression d'un noeud dans un arbre de plusieurs méthodes différentes (par exemple en suivant les ordres préfixe, infixe et suffixe). L'utilisation de l'une ou l'autre ne changera pas grand chose, le noeud sera toujours supprimé et l'arbre restera un arbre binaire de recherche. En revanche les arbres obtenus pourront être différents.
L'exemple donné ne répond pas à la question posée (telle que je la comprend). IL faut préciser la "règle" (l'algorithme) qu'on se donne pour supprimer un sommet et s'y tenir. Deux algos sont possibles: on fait remonter en priorité le min du sous-arbre droit (ou le max du sous-arbre gauche) et on s'y tient, dès lors que c'est possible.

L'exemple qui est donné pour mettre en faute la commutativité de la suppression utilise les deux règles en alternance. Le problème reste donc entier: et si on "fixe" la règle, a t-on commutativité de la suppression ?
Messages postés
16055
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 octobre 2020
2 696
"IL faut préciser la "règle" (l'algorithme) qu'on se donne pour supprimer un sommet et s'y tenir"
Pas forcément, regarde ma réponse #4.

Les arbres de recherche sont définis par des propriétés qui doivent toujours être vérifiées, mais "garder toujours le même algorithme" n'en fait pas partie. Il faut se limiter aux seuls règles de la définition, ce qui ne garantit pas la commutativité.

"si on "fixe" la règle, a t-on commutativité de la suppression ?"
C'est difficile d'imposer à utiliser toujours le même algorithme, il faudrait déjà se mettre d'accord sur la notion "d'algorithme unique". En gros je pourrais dire que mon algorithme c'est d'alterner les deux méthodes une fois sur deux. C'est un algorithme, je pourrais très bien m'y tenir ça ne changerai rien.

Au mieux, on pourrait imposer une propriété supplémentaire pour que l'insertion soit commutative, mais alors on se retrouvera dans un cas particulier d'arbre binaire de recherche, et les nouvelles contraintes devant êtres respectées, alors l'insertion sera commutative.
Mais imposer que l'insertion soit commutative ne veut pas dire pour autant que l'algorithme sera "fixé", en cherchant bien on pourra toujours trouver deux algorithmes qu'on pourrait utiliser en alternance tout en conservant la commutativité...
Bonjour KX,

je vois le point que vous faites. Mais ma question demeure. Mettons nous d'accord sur un algorithme de suppression. Observez aussi que l'algorithme, récursif, peut se limiter à supprimer la racine d'un ABR (au départ on cherche l'élément à supprimer et on l'appelle sur le sous-arbre qu'il induit, et récursivement ...).

Ainsi, on peut se donner l'algorithme (celui qui m'intéresse):

- si l'élément à supprimer est stocké dans une feuille de l'arbre
--- on supprime la feuille
- sinon
--- si le sous-arbre droit n'est pas vide
----- on remplace la valeur de la racine par le minimum m du sous-arbre droit
----- et on supprime la racine du sous-arbre induit par m
--- sinon (c'est que le sous-arbre gauche n'est pas vide)
----- on remplace la valeur de la racine par le maximum M du sous-arbre gauche
----- et on supprime la racine du sous-arbre induit par M

L'important est de se tenir à cet algo. Bien sûr, je suis d'accord avec vous que si je varie l'effet gauche/droite je maintiens la propriété ABR sans avoir la commutativité. Ce qui m'intéresse ici, est de savoir si je peux garantir la commutativité en fixant l'algo de suppression comme j'ai indiqué.

Vous me suivez ?