Commit | Line | Data |
---|---|---|
249ff697 JB |
1 | /*****************************************************************************/ |
2 | /* AVL */ | |
3 | /*****************************************************************************/ | |
4 | ||
5 | #include <stdio.h> | |
6 | #include <stdlib.h> | |
7 | ||
8 | typedef int t_cle; | |
9 | ||
10 | typedef struct noeud { | |
7b0cef36 JB |
11 | t_cle cle; |
12 | int deseq; /* deseq = hauteur du ss-abre gauche - hauteur du ss-arbre droit */ | |
13 | struct noeud *gauche, *droit; | |
14 | } N_AVL, *AVL; | |
249ff697 JB |
15 | |
16 | /*****************************************************************************/ | |
17 | AVL RG(AVL a) | |
18 | { | |
7b0cef36 | 19 | AVL b; |
249ff697 | 20 | |
7b0cef36 JB |
21 | b = a->droit; |
22 | a->droit = b->gauche; | |
23 | b->gauche = a; | |
24 | return b; | |
25 | } | |
249ff697 JB |
26 | |
27 | /*****************************************************************************/ | |
28 | AVL RD(AVL a) | |
29 | { | |
7b0cef36 | 30 | AVL b; |
249ff697 | 31 | |
7b0cef36 JB |
32 | b = a->gauche; |
33 | a->gauche = b->droit; | |
34 | b->droit = a; | |
35 | return b; | |
36 | } | |
249ff697 JB |
37 | |
38 | /*****************************************************************************/ | |
39 | AVL RGD(AVL a) | |
40 | { | |
7b0cef36 JB |
41 | a->gauche = RG(a->gauche); |
42 | return (RD(a)); | |
249ff697 JB |
43 | } |
44 | ||
249ff697 JB |
45 | /*****************************************************************************/ |
46 | AVL RDG(AVL a) | |
47 | { | |
7b0cef36 JB |
48 | a->droit = RD(a->droit); |
49 | return (RG(a)); | |
249ff697 JB |
50 | } |
51 | ||
249ff697 | 52 | /*****************************************************************************/ |
7b0cef36 | 53 | AVL insere(AVL p, int x, int *verif) |
249ff697 | 54 | { |
7b0cef36 JB |
55 | if (p == NULL) { |
56 | p = (N_AVL *) malloc(sizeof(N_AVL)); | |
57 | if (p == NULL) | |
58 | exit(-1); | |
59 | p->cle = x; | |
60 | p->gauche = NULL; | |
61 | p->droit = NULL; | |
62 | p->deseq = 0; | |
63 | *verif = 1; | |
64 | } else if (x == p->cle) | |
65 | printf("Insertion impossible ! %d est deja dans l'arbre\n", x); | |
66 | ||
67 | else if (x < p->cle) { | |
68 | p->gauche = insere(p->gauche, x, verif); | |
69 | if (*verif) { /* on a insere a gauche */ | |
70 | switch (p->deseq) { | |
71 | case -1: | |
72 | p->deseq = 0; | |
73 | *verif = 0; | |
74 | break; | |
75 | case 0: | |
76 | p->deseq = 1; | |
77 | break; | |
78 | case 1: // reequilibrage | |
79 | if (p->gauche->deseq == 1) { // rotation droite | |
80 | printf("RD pour %6d\n", p->cle); | |
81 | p = RD(p); | |
82 | p->deseq = p->droit->deseq = 0; | |
83 | *verif = 0; | |
84 | } else { /* rotation gauche droite */ | |
85 | printf("RGD pour %6d\n", p->cle); | |
86 | p = RGD(p); | |
87 | switch (p->deseq) { | |
88 | case -1: | |
89 | p->droit->deseq = 0; | |
90 | p->gauche->deseq = 1; | |
91 | break; | |
92 | case 0: | |
93 | p->droit->deseq = 0; | |
94 | p->gauche->deseq = 0; | |
95 | break; | |
96 | case 1: | |
97 | p->droit->deseq = -1; | |
98 | p->gauche->deseq = 0; | |
249ff697 | 99 | } |
7b0cef36 JB |
100 | p->deseq = 0; |
101 | *verif = 0; | |
102 | } | |
103 | break; | |
104 | } | |
249ff697 | 105 | |
7b0cef36 JB |
106 | } |
107 | } else { | |
108 | p->droit = insere(p->droit, x, verif); | |
109 | if (*verif) { /* on a insere a droite */ | |
110 | switch (p->deseq) { | |
111 | case 1: | |
112 | p->deseq = 0; | |
113 | *verif = 0; | |
114 | break; | |
115 | case 0: | |
116 | p->deseq = -1; | |
117 | break; | |
118 | case -1: // reequilibrage | |
119 | if (p->droit->deseq == -1) { /* rotation gauche */ | |
120 | printf("RG pour %6d\n", p->cle); | |
121 | p = RG(p); | |
122 | p->deseq = p->gauche->deseq = 0; | |
123 | *verif = 0; | |
124 | } else { /* rotation droite gauche */ | |
125 | printf("RDG pour %6d\n", p->cle); | |
126 | p = RDG(p); | |
127 | switch (p->deseq) { | |
128 | case 1: | |
129 | p->droit->deseq = -1; | |
130 | p->gauche->deseq = 0; | |
131 | break; | |
132 | case 0: | |
133 | p->droit->deseq = 0; | |
134 | p->gauche->deseq = 0; | |
135 | break; | |
136 | case -1: | |
137 | p->droit->deseq = 0; | |
138 | p->gauche->deseq = 1; | |
139 | } | |
140 | p->deseq = 0; | |
141 | *verif = 0; | |
142 | } | |
143 | break; | |
144 | } | |
145 | } | |
146 | } | |
147 | return (p); | |
148 | } | |
249ff697 JB |
149 | |
150 | /*****************************************************************************/ | |
7b0cef36 | 151 | AVL equigauche(AVL p, int *verif) |
249ff697 JB |
152 | /* quand on entre dans la fonction, *verif = 1 */ |
153 | { | |
7b0cef36 JB |
154 | switch (p->deseq) { |
155 | case 1: | |
156 | p->deseq = 0; | |
157 | break; | |
158 | case 0: | |
159 | p->deseq = -1; | |
160 | *verif = 0; | |
161 | break; | |
162 | case -1: /* reequilibrage */ | |
163 | if (p->droit->deseq <= 0) { /* rotation gauche */ | |
164 | printf("RG pour %6d\n", p->cle); | |
165 | p = RG(p); | |
166 | if (p->deseq == 0) { | |
167 | p->gauche->deseq = -1; | |
168 | p->deseq = 1; | |
169 | *verif = 0; | |
170 | } else { // forcement p->deseq = -1 | |
171 | p->deseq = p->gauche->deseq = 0; | |
172 | } | |
173 | } else { /* rotation droite gauche */ | |
174 | printf("RDG pour %6d\n", p->cle); | |
175 | p = RDG(p); | |
176 | switch (p->deseq) { | |
177 | case 0: | |
178 | p->droit->deseq = p->gauche->deseq = 0; | |
179 | break; | |
180 | case 1: | |
181 | p->droit->deseq = -1; | |
182 | p->gauche->deseq = 0; | |
183 | break; | |
184 | case -1: | |
185 | p->droit->deseq = 0; | |
186 | p->gauche->deseq = 1; | |
187 | } | |
188 | p->deseq = 0; | |
249ff697 | 189 | } |
7b0cef36 JB |
190 | } |
191 | return p; | |
249ff697 JB |
192 | } |
193 | ||
249ff697 | 194 | /*****************************************************************************/ |
7b0cef36 | 195 | AVL equidroit(AVL p, int *verif) // quand on entre dans la fonction, verif = 1 |
249ff697 | 196 | { |
7b0cef36 JB |
197 | switch (p->deseq) { |
198 | case -1: | |
199 | p->deseq = 0; | |
200 | break; | |
201 | case 0: | |
202 | p->deseq = 1; | |
203 | *verif = 0; | |
204 | break; | |
205 | case 1: /* reequilibrage */ | |
206 | if (p->gauche->deseq >= 0) { /* rotation droite */ | |
207 | printf("RD pour %6d\n", p->cle); | |
208 | p = RD(p); | |
209 | if (p->deseq == 0) { | |
210 | p->droit->deseq = 1; | |
211 | p->deseq = -1; | |
212 | *verif = 0; | |
213 | } else { /* forcement p->deseq = 1 */ | |
214 | p->deseq = p->droit->deseq = 0; | |
215 | } | |
216 | } else { /* rotation gauche droite */ | |
217 | printf("RGD pour %6d\n", p->cle); | |
218 | p = RGD(p); | |
219 | switch (p->deseq) { | |
220 | case 0: | |
221 | p->gauche->deseq = p->droit->deseq = 0; | |
222 | break; | |
223 | case 1: | |
224 | p->gauche->deseq = 0; | |
225 | p->droit->deseq = -1; | |
226 | break; | |
227 | case -1: | |
228 | p->gauche->deseq = 1; | |
229 | p->droit->deseq = 0; | |
230 | } | |
231 | p->deseq = 0; | |
232 | } | |
233 | } | |
234 | return p; | |
249ff697 JB |
235 | } |
236 | ||
249ff697 | 237 | /*****************************************************************************/ |
7b0cef36 | 238 | AVL supmax(AVL p, AVL r, int *verif) |
249ff697 | 239 | { |
7b0cef36 | 240 | AVL q; |
249ff697 | 241 | |
7b0cef36 JB |
242 | if (r->droit == NULL) { |
243 | p->cle = r->cle; | |
244 | q = r; /* q : l'element a supprimer par free */ | |
245 | r = r->gauche; | |
246 | free(q); | |
247 | *verif = 1; | |
248 | } else { | |
249 | r->droit = supmax(p, r->droit, verif); | |
250 | if (*verif) | |
251 | r = equidroit(r, verif); | |
252 | } | |
253 | return r; | |
254 | } | |
249ff697 JB |
255 | |
256 | /*****************************************************************************/ | |
7b0cef36 | 257 | AVL supprime(AVL p, int x, int *verif) |
249ff697 | 258 | { |
7b0cef36 | 259 | AVL q; |
249ff697 | 260 | |
7b0cef36 JB |
261 | if (p == NULL) |
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) { | |
265 | q = p; | |
266 | p = p->gauche; | |
267 | free(q); | |
268 | *verif = 1; | |
269 | } else if (p->gauche == NULL) { | |
270 | q = p; | |
271 | p = p->droit; | |
272 | free(q); | |
273 | *verif = 1; | |
274 | } else { | |
275 | p->gauche = supmax(p, p->gauche, verif); | |
276 | if (*verif) | |
277 | p = equigauche(p, verif); | |
278 | } | |
279 | } else if (x < p->cle) { | |
280 | p->gauche = supprime(p->gauche, x, verif); | |
281 | if (*verif) | |
282 | p = equigauche(p, verif); | |
283 | } else { | |
284 | p->droit = supprime(p->droit, x, verif); | |
285 | if (*verif) | |
286 | p = equidroit(p, verif); | |
287 | } | |
288 | return p; | |
249ff697 JB |
289 | } |
290 | ||
249ff697 JB |
291 | /*****************************************************************************/ |
292 | void affiche_arbre(AVL p, int col) | |
293 | { | |
7b0cef36 JB |
294 | int i; |
295 | char esp = ' '; | |
249ff697 | 296 | |
7b0cef36 JB |
297 | if (p) { |
298 | affiche_arbre(p->droit, col + 6); | |
299 | for (i = 0; i < col; i++) | |
300 | printf("%c", esp); | |
301 | printf("%6d(%2d)\n", p->cle, p->deseq); | |
302 | affiche_arbre(p->gauche, col + 6); | |
303 | }; | |
304 | } | |
249ff697 JB |
305 | |
306 | /*****************************************************************************/ | |
307 | main() | |
7b0cef36 JB |
308 | { |
309 | AVL rac = NULL; | |
310 | int x; | |
311 | int verif; | |
249ff697 | 312 | |
7b0cef36 JB |
313 | do { |
314 | printf("Entrez une cle: "); | |
315 | scanf("%d", &x); | |
316 | if (x) { | |
317 | printf("Insertion de la cle %6d\n", x); | |
318 | verif = 0; | |
319 | rac = insere(rac, x, &verif); | |
320 | affiche_arbre(rac, 0); | |
321 | } | |
322 | } | |
323 | while (x); | |
249ff697 | 324 | |
7b0cef36 JB |
325 | do { |
326 | printf("Entrez une cle: "); | |
327 | scanf("%d", &x); | |
328 | if (x) { | |
329 | printf("Suppression de la cle %6d\n", x); | |
330 | verif = 0; | |
331 | rac = supprime(rac, x, &verif); | |
332 | affiche_arbre(rac, 0); | |
333 | } | |
334 | } | |
335 | while (x); | |
336 | } | |
337 | ||
338 | /*****************************************************************************/ |