d5f58b851cc9c0ac2b9a28c56f3e0e513c394104
1 /*****************************************************************************/
3 /*****************************************************************************/
10 typedef struct noeud
{
12 int deseq
; /* deseq = hauteur du ss-abre gauche
13 - hauteur du ss-arbre droit */
14 struct noeud
*gauche
, *droit
;
18 /*****************************************************************************/
29 /*****************************************************************************/
40 /*****************************************************************************/
43 a
->gauche
=RG(a
->gauche
);
48 /*****************************************************************************/
51 a
->droit
=RD(a
->droit
);
56 /*****************************************************************************/
57 AVL
insere(AVL p
,int x
,int *verif
)
60 {p
= (N_AVL
*)malloc(sizeof(N_AVL
));
61 if (p
==NULL
) exit(-1);
62 p
->cle
= x
;p
->gauche
= NULL
;p
->droit
= NULL
;
63 p
->deseq
= 0; *verif
= 1;
66 printf("Insertion impossible ! %d est deja dans l'arbre\n",x
);
69 {p
->gauche
= insere(p
->gauche
,x
,verif
);
70 if (*verif
) {/* on a insere a gauche */
72 {case -1 : p
->deseq
= 0; *verif
= 0; break;
73 case 0 : p
->deseq
= 1; break;
74 case 1 : // reequilibrage
75 if (p
->gauche
->deseq
==1)
77 printf("RD pour %6d\n",p
->cle
);
79 p
->deseq
= p
->droit
->deseq
= 0;
82 else {/* rotation gauche droite */
83 printf("RGD pour %6d\n",p
->cle
);
86 {case -1 : p
->droit
->deseq
=0;
89 case 0 : p
->droit
->deseq
=0;
92 case 1 : p
->droit
->deseq
=-1;
103 {p
->droit
= insere(p
->droit
,x
,verif
);
104 if (*verif
) {/* on a insere a droite */
106 {case 1 : p
->deseq
= 0; *verif
= 0; break;
107 case 0 : p
->deseq
= -1; break;
108 case -1 : // reequilibrage
109 if (p
->droit
->deseq
==-1)
110 {/* rotation gauche */
111 printf("RG pour %6d\n",p
->cle
);
113 p
->deseq
= p
->gauche
->deseq
= 0;
116 else {/* rotation droite gauche */
117 printf("RDG pour %6d\n",p
->cle
);
120 {case 1 : p
->droit
->deseq
=-1;
123 case 0 : p
->droit
->deseq
=0;
126 case -1 : p
->droit
->deseq
=0;
129 p
->deseq
=0; *verif
=0;
139 /*****************************************************************************/
140 AVL
equigauche(AVL p
,int *verif
)
141 /* quand on entre dans la fonction, *verif = 1 */
144 {case 1 : p
->deseq
= 0; break;
145 case 0 : p
->deseq
= -1; *verif
= 0; break;
146 case -1 : /* reequilibrage */
147 if (p
->droit
->deseq
<= 0)
148 {/* rotation gauche */
149 printf("RG pour %6d\n",p
->cle
);
151 if (p
->deseq
== 0) {p
->gauche
->deseq
= -1; p
->deseq
= 1;
153 else {//forcement p->deseq = -1
154 p
->deseq
= p
->gauche
->deseq
= 0; }
157 {/* rotation droite gauche */
158 printf("RDG pour %6d\n",p
->cle
);
161 {case 0 : p
->droit
->deseq
= p
->gauche
->deseq
=0; break;
162 case 1 : p
->droit
->deseq
= -1; p
->gauche
->deseq
= 0;
164 case -1 : p
->droit
->deseq
= 0; p
->gauche
->deseq
= 1;
173 /*****************************************************************************/
174 AVL
equidroit(AVL p
,int *verif
) // quand on entre dans la fonction, verif = 1
177 {case -1 : p
->deseq
= 0; break;
178 case 0 : p
->deseq
= 1; *verif
= 0; break;
179 case 1 : /* reequilibrage */
180 if (p
->gauche
->deseq
>= 0)
181 {/* rotation droite */
182 printf("RD pour %6d\n",p
->cle
);
184 if (p
->deseq
== 0) {p
->droit
->deseq
= 1; p
->deseq
= -1;
186 else {/* forcement p->deseq = 1 */
187 p
->deseq
= p
->droit
->deseq
= 0; }
190 {/* rotation gauche droite */
191 printf("RGD pour %6d\n",p
->cle
);
194 {case 0 : p
->gauche
->deseq
= p
->droit
->deseq
=0; break;
195 case 1 : p
->gauche
->deseq
= 0; p
->droit
->deseq
= -1;
197 case -1 : p
->gauche
->deseq
= 1; p
->droit
->deseq
= 0;
206 /*****************************************************************************/
207 AVL
supmax(AVL p
,AVL r
,int *verif
)
210 if (r
->droit
== NULL
) {p
->cle
= r
->cle
;
211 q
= r
; /* q : l'element a supprimer par free */
216 else {r
->droit
= supmax(p
,r
->droit
,verif
);
217 if (*verif
) r
= equidroit(r
,verif
);
223 /*****************************************************************************/
224 AVL
supprime(AVL p
,int x
,int *verif
)
229 printf( "Suppression impossible ! %d n'est pas dans l'arbre\n",x
);
230 else if (x
== p
->cle
) { /* Suppression de p */
231 if (p
->droit
== NULL
) {q
= p
; p
= p
->gauche
;
232 free(q
); *verif
= 1; }
233 else if (p
->gauche
== NULL
) {q
= p
; p
= p
->droit
;
234 free(q
); *verif
= 1; }
235 else {p
-> gauche
= supmax(p
,p
->gauche
,verif
);
236 if (*verif
) p
= equigauche(p
,verif
);
240 {p
->gauche
= supprime(p
->gauche
,x
,verif
);
241 if (*verif
) p
= equigauche(p
,verif
);
243 else {p
->droit
= supprime(p
->droit
,x
,verif
);
244 if (*verif
) p
= equidroit(p
,verif
);
250 /*****************************************************************************/
251 void affiche_arbre(AVL p
, int col
)
255 {affiche_arbre(p
->droit
,col
+6);
256 for (i
=0;i
<col
;i
++) printf("%c",esp
);
257 printf("%6d(%2d)\n",p
->cle
,p
->deseq
);
258 affiche_arbre(p
->gauche
,col
+6);
264 /*****************************************************************************/
269 do {printf("Entrez une cle: ");scanf("%d",&x
);
270 if (x
) {printf("Insertion de la cle %6d\n",x
);
272 rac
= insere(rac
,x
,&verif
);
273 affiche_arbre(rac
,0);
278 do {printf("Entrez une cle: ");scanf("%d",&x
);
279 if (x
) {printf("Suppression de la cle %6d\n",x
);
281 rac
= supprime(rac
,x
,&verif
);
282 affiche_arbre(rac
,0);
287 /*****************************************************************************/