1 /*****************************************************************************/
3 /*****************************************************************************/
10 typedef struct noeud
{
12 int deseq
; /* deseq = hauteur du ss-abre gauche - hauteur du ss-arbre droit */
13 struct noeud
*gauche
, *droit
;
16 /*****************************************************************************/
27 /*****************************************************************************/
38 /*****************************************************************************/
41 a
->gauche
= RG(a
->gauche
);
45 /*****************************************************************************/
48 a
->droit
= RD(a
->droit
);
52 /*****************************************************************************/
53 AVL
insere(AVL p
, int x
, int *verif
)
56 p
= (N_AVL
*) malloc(sizeof(N_AVL
));
64 } else if (x
== p
->cle
)
65 printf("Insertion impossible ! %d est deja dans l'arbre\n", x
);
67 else if (x
< p
->cle
) {
68 p
->gauche
= insere(p
->gauche
, x
, verif
);
69 if (*verif
) { /* on a insere a gauche */
78 case 1: // reequilibrage
79 if (p
->gauche
->deseq
== 1) { // rotation droite
80 printf("RD pour %6d\n", p
->cle
);
82 p
->deseq
= p
->droit
->deseq
= 0;
84 } else { /* rotation gauche droite */
85 printf("RGD pour %6d\n", p
->cle
);
108 p
->droit
= insere(p
->droit
, x
, verif
);
109 if (*verif
) { /* on a insere a droite */
118 case -1: // reequilibrage
119 if (p
->droit
->deseq
== -1) { /* rotation gauche */
120 printf("RG pour %6d\n", p
->cle
);
122 p
->deseq
= p
->gauche
->deseq
= 0;
124 } else { /* rotation droite gauche */
125 printf("RDG pour %6d\n", p
->cle
);
129 p
->droit
->deseq
= -1;
130 p
->gauche
->deseq
= 0;
134 p
->gauche
->deseq
= 0;
138 p
->gauche
->deseq
= 1;
150 /*****************************************************************************/
151 AVL
equigauche(AVL p
, int *verif
)
152 /* quand on entre dans la fonction, *verif = 1 */
162 case -1: /* reequilibrage */
163 if (p
->droit
->deseq
<= 0) { /* rotation gauche */
164 printf("RG pour %6d\n", p
->cle
);
167 p
->gauche
->deseq
= -1;
170 } else { // forcement p->deseq = -1
171 p
->deseq
= p
->gauche
->deseq
= 0;
173 } else { /* rotation droite gauche */
174 printf("RDG pour %6d\n", p
->cle
);
178 p
->droit
->deseq
= p
->gauche
->deseq
= 0;
181 p
->droit
->deseq
= -1;
182 p
->gauche
->deseq
= 0;
186 p
->gauche
->deseq
= 1;
194 /*****************************************************************************/
195 AVL
equidroit(AVL p
, int *verif
) // quand on entre dans la fonction, verif = 1
205 case 1: /* reequilibrage */
206 if (p
->gauche
->deseq
>= 0) { /* rotation droite */
207 printf("RD pour %6d\n", p
->cle
);
213 } else { /* forcement p->deseq = 1 */
214 p
->deseq
= p
->droit
->deseq
= 0;
216 } else { /* rotation gauche droite */
217 printf("RGD pour %6d\n", p
->cle
);
221 p
->gauche
->deseq
= p
->droit
->deseq
= 0;
224 p
->gauche
->deseq
= 0;
225 p
->droit
->deseq
= -1;
228 p
->gauche
->deseq
= 1;
237 /*****************************************************************************/
238 AVL
supmax(AVL p
, AVL r
, int *verif
)
242 if (r
->droit
== NULL
) {
244 q
= r
; /* q : l'element a supprimer par free */
249 r
->droit
= supmax(p
, r
->droit
, verif
);
251 r
= equidroit(r
, verif
);
256 /*****************************************************************************/
257 AVL
supprime(AVL p
, int x
, int *verif
)
262 printf("Suppression impossible ! %d n'est pas dans l'arbre\n", x
);
263 else if (x
== p
->cle
) { /* Suppression de p */
264 if (p
->droit
== NULL
) {
269 } else if (p
->gauche
== NULL
) {
275 p
->gauche
= supmax(p
, p
->gauche
, verif
);
277 p
= equigauche(p
, verif
);
279 } else if (x
< p
->cle
) {
280 p
->gauche
= supprime(p
->gauche
, x
, verif
);
282 p
= equigauche(p
, verif
);
284 p
->droit
= supprime(p
->droit
, x
, verif
);
286 p
= equidroit(p
, verif
);
291 /*****************************************************************************/
292 void affiche_arbre(AVL p
, int col
)
298 affiche_arbre(p
->droit
, col
+ 6);
299 for (i
= 0; i
< col
; i
++)
301 printf("%6d(%2d)\n", p
->cle
, p
->deseq
);
302 affiche_arbre(p
->gauche
, col
+ 6);
306 /*****************************************************************************/
314 printf("Entrez une cle: ");
317 printf("Insertion de la cle %6d\n", x
);
319 rac
= insere(rac
, x
, &verif
);
320 affiche_arbre(rac
, 0);
326 printf("Entrez une cle: ");
329 printf("Suppression de la cle %6d\n", x
);
331 rac
= supprime(rac
, x
, &verif
);
332 affiche_arbre(rac
, 0);
338 /*****************************************************************************/