Arbre binaire
Résolu/Fermé
lahouma1987
Messages postés
9
Date d'inscription
mardi 29 janvier 2013
Statut
Membre
Dernière intervention
30 janvier 2013
-
29 janv. 2013 à 21:37
guywiz - 7 déc. 2013 à 08:31
guywiz - 7 déc. 2013 à 08:31
A voir également:
- Arbre binaire
- Codage binaire - Guide
- Arbre généalogique famille michelin - Télécharger - Généalogie
- Glandier arbre ✓ - Forum Loisirs / Divertissements
- Alphabet binaire ✓ - Forum Programmation
- Printf binaire ✓ - Forum C
4 réponses
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 018
Modifié par KX le 29/01/2013 à 21:55
Modifié par KX le 29/01/2013 à 21:55
Ç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)
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 7La confiance n'exclut pas le contrôle
mais on doit suivre le même algo de suppression de deux noeuds successifs !!!!
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 018
7 mars 2013 à 18:24
7 mars 2013 à 18:24
"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.
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 ?
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 ?
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 018
Modifié par KX le 6/12/2013 à 19:04
Modifié par KX le 6/12/2013 à 19:04
"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é...
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 ?
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 ?
29 janv. 2013 à 22:44
20 mars 2013 à 15:12
20 mars 2013 à 18:45