modifier une valeur dans un arbre binaire de recherche?

Version imprimable

03/02/2012, 23h02
paco_the_king

modifier une valeur dans un arbre binaire de recherche?

Bonjour

je voudrais ecrire un programme en C++ permettant de modifier une valeur dans un arbre binaire de recherche.
je suis quasi nul alors si vous connaissez la solution, merci de me la décrire en entier

Salut,

La première chose qu'il faille faire, c'est de t'assurer que la modification de valeur que tu va apporter ne se répercutera pas sur le tri de ton arbre binaire!!!

Je m'explique:

Chaque fois que l'on va insérer une valeur, on va parcourir une partie de l'arbre en comparant la valeur à rajouter à la valeur du "noeud" en cours et, selon le cas, on décidera de continuer de manière "récursive" soit du coté gauche de l'arbre, soit du coté droit de l'arbre.

Pour mémoire :Il n'est pas impossible que l'arbre soit rééquilibré après chaque inclusion, mais cela n'a comme seul but que d'éviter le "cas peau de banane" de l'insertion d'éléments déjà triés qui ferait que nous nous retrouvions avec un équivalent à une liste simplement chainée ;)

Par contre, la recherche d'un élément va se faire par équivalence sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Node * search(Node * node, T value) { if ( node->value < value) { if( node->left) return search(node->left , value); else retrun 0; } else if value < node->value) { if( node->right) return search(node->right, value); else return 0; } else { return node; } }
Le problème auquel tu risques vraiment d'être confronté, si tu veux modifier la valeur d'un élément, c'est que tu la valeur que tu vas introduire ne corresponde plus effectivement à cet algorithme : quelle soit, par exemple, plus grande que la valeur du noeud parent alors qu'elle se trouve sur la partie qui est sensée contenir une valeur plus petite (ou inversement), voir que la valeur de l'un des noeuds enfant ne corresponde plus (que la valeur du noeud enfant sensé etre plus grande que celle du noeud envisagé soit en réalité plus petite, ou inversement)...

Tu ne peux donc envisager de modifier que la partie de la valeur qui n'intervient pas dans la comparaison !!!

C'est d'ailleurs la raison pour laquelle la classe set fournie par le standard (qui est la classe implémentant un arbre binaire, basée sur le fait que la valeur est la clé de tri et de recherche) fait en sorte d'interdire purement et simplement la modification des éléments déjà ajoutés ;)

Et donc, si la partie que tu veux modifier intervient dans la comparaison, la seule solution pour arriver à un résultat similaire est de supprimer l'élément utilisant l'ancienne valeur et d'ajouter un nouvel élément qui utilise la nouvelle valeur ;)

Une des alternatives éventuelles est de séparer "physiquement" la clé servant au tri et à la recherche de la valeur de l'élément représenté par cette clé.

Cela permet, dans la mesure où les modifications apportées ne touchent pas à la clé permettant d'identifier de manière unique et non ambigüe un élément parmi les autre, d'apporter certains ajustements sans avoir à recalculer la clé et donc sans avoir à supprimer l'ancien élément avant d'en rajouter un ayant les nouvelles valeurs.

C'est, par exemple, ce que fait la classe map fournie par le standard ;)

Comme tu ne nous en as pas dit assez pour t'aider efficacement, j'espère que cette prose te permettra, au moins, de te poser les bonnes questions ;)

merci de m'avoir répondu

en fait, ce que je veux pour être plus précis c'est d'avoir un programme en c++ qui me permet de créer un arbre binaire de recherche, de l'afficher , de pouvoir modifier ses valeurs ensuite et a la fin d'affiché le résultat des changements

voici ce que j'ai pu faire de mon côté
je ne sais pas si c'est juste ou psa

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
 
 
 
 
 
 
 
typedef struct ABR{
int valeur ;
struct ABR* gauche ;
struct ABR* droite ;
}ABR;
 // procedure pour trouve un noeud//
 void ABR* trouve_noeud ( int n , ABR* arbre ) {
if ( arbre->valeur == n )
return arbre ;
if ( n <=arbre->valeur ) {
if ( arbre->gauche != NULL)
return trouve_noeud ( n , arbre->gauche ) ;
else
return NULL;
} else {
if ( arbre->droite != NULL)
return trouve_noeud ( n , arbre->droite ) ;
else
return NULL; 
}
}
//procedur pour supprimer un noeud //
void supprime_noeud (ABR * * pere , int x ) {
while ( * pere ) {
if ( ( * pere)->valeur==x ) {
ABR * noeudx=*pere ;
if ( noeudx->gauche==NULL) * pere = noeudx->droite ;
else if ( noeudx->droite==NULL) * pere = noeudx->gauche ;
else {
ABR * noeud_droit ;
ABR * * pere_noeud_droit=&noeudx->droite ;
while ( ( * pere_noeud_droit)->gauche )
pere_noeud_droit=&(*pere_noeud_droit)->gauche ;
noeud_droit=*pere_noeud_droit ;
*pere_noeud_droit=noeud_droit->droite ;
noeud_droit->gauche=noeudx->gauche ;
noeud_droit->droite=noeudx->droite ;
* pere=noeud_droit ;
} ;
free ( noeudx ) ;
return ;
} else if ( ( * pere)->valeur <x ) pere =&((* pere)->gauche ) ;
else pere =&((* pere)->droite ) ;
}
//procedur pour l'ajout recurssive d'un entier //
void ABR* ajoute_rec _entier (ABR* nouveau , ABR* arbre , ABR* noeud ) {
if ( arbre == NULL) {
return nouveau ;
}
if ( nouveau->valeur <= noeud->valeur ) {
if ( noeud->gauche == NULL) {
noeud->gauche = nouveau ;
} else {
ajoute_rec_entier ( nouveau , arbre , noeud->gauche ) ;
}
} else {
if ( noeud->droite == NULL) {
noeud->droite = nouveau ;
} else {
ajoute_rec_entier ( nouveau , arbre , noeud->droite ) ;
}
}
return arbre ;
}
 //procedure pour l'ajoute d'entier //
void ABR* ajoute_entier ( int n , ABR* arbre ) {
ABR* nouveau = cree_arbre ( n ) ;
printf ( "%d?:?%p\n" ,n , nouveau ) ;
return ajoute_rec_entier ( nouveau , arbre , arbre ) ;
}
//procedur pour l'affichage recurssive //
 
void affiche_arbre_rec(ABR* arbre ) {
printf ( " ( " ) ;
if ( arbre->gauche != NULL) {
affiche_arbre_rec( a r br e->gauche ) ;
} else {
printf ( "_" ) ;
}
printf ( ",%d , " , arbre->valeur ) ;
if ( arbre->droite != NULL) 
affiche_arbre_rec( arbre->droite ) ;
} else {
printf ( "_" ) ;
}
printf ( " ) " ) ;
}
//procedur pour l'afficharge d'un arbre //
void affiche_arbre (ABR* arbre ) {
affiche_arbre_rec ( arbre ) ;
printf ( "\n" ) ;
}
 
 
int main()
int n,i,val ,val1, val2 ;
{   printf ("salem   /n") ;
     // construction de l'arbre de recherche //
     printf (" entrez le nombre d'elements de cette arbre /n");
      scanf("%d",&n); 
       for(i=1;i<=n;i++){
                     printf("entrez la %d valeur de l'arbre de recherche ",&i)
                     scanf("%d",&val);
                     printf("/n");
                     ajoute_entier  (val , arbre );
                     }
      // affichage de l'arbre de recherche //               
 
         affiche_arbre (arbre );
 
 
         // entrez les valeurs qu'on veut modifier 
            printf ("entrez la valeur que vous voulez modiffier " );
            scanf("%d",&val1);
            printf("/n");
            // suppression de la valeur entre 
          supprime_noeud (arbre , val1 )         
            printf (" maintenant entrez la valeur dans vous voulez la remplacez ");
            scanf("%d",&val2);
            // ajouter le nouveau èlement 
             ajoute_entier  (val2 , arbre );
         // afficher le nouveau arbre 
         affiche_arbre (arbre );
 
 
 
}