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 { | |
11 | t_cle cle; | |
12 | int deseq; /* deseq = hauteur du ss-abre gauche | |
13 | - hauteur du ss-arbre droit */ | |
14 | struct noeud *gauche, *droit; | |
15 | } N_AVL, *AVL; | |
16 | ||
17 | ||
18 | /*****************************************************************************/ | |
19 | AVL RG(AVL a) | |
20 | { | |
21 | AVL b; | |
22 | b = a->droit; | |
23 | a->droit = b->gauche; | |
24 | b->gauche = a; | |
25 | return b; | |
26 | } | |
27 | ||
28 | ||
29 | /*****************************************************************************/ | |
30 | AVL RD(AVL a) | |
31 | { | |
32 | AVL b; | |
33 | b = a->gauche; | |
34 | a->gauche = b->droit; | |
35 | b->droit = a; | |
36 | return b; | |
37 | } | |
38 | ||
39 | ||
40 | /*****************************************************************************/ | |
41 | AVL RGD(AVL a) | |
42 | { | |
43 | a->gauche=RG(a->gauche); | |
44 | return(RD(a)); | |
45 | } | |
46 | ||
47 | ||
48 | /*****************************************************************************/ | |
49 | AVL RDG(AVL a) | |
50 | { | |
51 | a->droit=RD(a->droit); | |
52 | return(RG(a)); | |
53 | } | |
54 | ||
55 | ||
56 | /*****************************************************************************/ | |
57 | AVL insere(AVL p,int x,int *verif) | |
58 | { | |
59 | if (p == NULL) | |
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; | |
64 | } | |
65 | else if (x == p->cle) | |
66 | printf("Insertion impossible ! %d est deja dans l'arbre\n",x); | |
67 | ||
68 | else if (x < p->cle) | |
69 | {p->gauche = insere(p->gauche,x,verif); | |
70 | if (*verif) {/* on a insere a gauche */ | |
71 | switch (p->deseq) | |
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) | |
76 | {// rotation droite | |
77 | printf("RD pour %6d\n",p->cle); | |
78 | p=RD(p); | |
79 | p->deseq = p->droit->deseq = 0; | |
80 | *verif = 0; | |
81 | } | |
82 | else {/* rotation gauche droite */ | |
83 | printf("RGD pour %6d\n",p->cle); | |
84 | p=RGD(p); | |
85 | switch (p->deseq) | |
86 | {case -1 : p->droit->deseq=0; | |
87 | p->gauche->deseq=1; | |
88 | break; | |
89 | case 0 : p->droit->deseq=0; | |
90 | p->gauche->deseq=0; | |
91 | break; | |
92 | case 1 : p->droit->deseq=-1; | |
93 | p->gauche->deseq=0; | |
94 | } | |
95 | p->deseq=0; *verif=0; | |
96 | } | |
97 | break; | |
98 | } | |
99 | ||
100 | } | |
101 | } | |
102 | else | |
103 | {p->droit = insere(p->droit,x,verif); | |
104 | if (*verif) {/* on a insere a droite */ | |
105 | switch (p->deseq) | |
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); | |
112 | p=RG(p); | |
113 | p->deseq = p->gauche->deseq = 0; | |
114 | *verif = 0; | |
115 | } | |
116 | else {/* rotation droite gauche */ | |
117 | printf("RDG pour %6d\n",p->cle); | |
118 | p=RDG(p); | |
119 | switch (p->deseq) | |
120 | {case 1 : p->droit->deseq=-1; | |
121 | p->gauche->deseq=0; | |
122 | break; | |
123 | case 0 : p->droit->deseq=0; | |
124 | p->gauche->deseq=0; | |
125 | break; | |
126 | case -1 : p->droit->deseq=0; | |
127 | p->gauche->deseq=1; | |
128 | } | |
129 | p->deseq=0; *verif=0; | |
130 | } | |
131 | break; | |
132 | } | |
133 | } | |
134 | } | |
135 | return(p); | |
136 | } | |
137 | ||
138 | ||
139 | /*****************************************************************************/ | |
140 | AVL equigauche(AVL p,int *verif) | |
141 | /* quand on entre dans la fonction, *verif = 1 */ | |
142 | { | |
143 | switch (p->deseq) | |
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); | |
150 | p = RG(p); | |
151 | if (p->deseq == 0) {p->gauche->deseq = -1; p->deseq = 1; | |
152 | *verif=0;} | |
153 | else {//forcement p->deseq = -1 | |
154 | p->deseq = p->gauche->deseq = 0; } | |
155 | } | |
156 | else | |
157 | {/* rotation droite gauche */ | |
158 | printf("RDG pour %6d\n",p->cle); | |
159 | p = RDG(p); | |
160 | switch (p->deseq) | |
161 | {case 0 : p->droit->deseq = p->gauche->deseq =0; break; | |
162 | case 1 : p->droit->deseq = -1; p->gauche->deseq = 0; | |
163 | break; | |
164 | case -1 : p->droit->deseq = 0; p->gauche->deseq = 1; | |
165 | } | |
166 | p->deseq = 0; | |
167 | } | |
168 | } | |
169 | return p; | |
170 | } | |
171 | ||
172 | ||
173 | /*****************************************************************************/ | |
174 | AVL equidroit(AVL p,int *verif) // quand on entre dans la fonction, verif = 1 | |
175 | { | |
176 | switch (p->deseq) | |
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); | |
183 | p = RD(p); | |
184 | if (p->deseq == 0) {p->droit->deseq = 1; p->deseq = -1; | |
185 | *verif=0; } | |
186 | else {/* forcement p->deseq = 1 */ | |
187 | p->deseq = p->droit->deseq = 0; } | |
188 | } | |
189 | else | |
190 | {/* rotation gauche droite */ | |
191 | printf("RGD pour %6d\n",p->cle); | |
192 | p = RGD(p); | |
193 | switch (p->deseq) | |
194 | {case 0 : p->gauche->deseq = p->droit->deseq =0; break; | |
195 | case 1 : p->gauche->deseq = 0; p->droit->deseq = -1; | |
196 | break; | |
197 | case -1 : p->gauche->deseq = 1; p->droit->deseq = 0; | |
198 | } | |
199 | p->deseq = 0; | |
200 | } | |
201 | } | |
202 | return p; | |
203 | } | |
204 | ||
205 | ||
206 | /*****************************************************************************/ | |
207 | AVL supmax(AVL p,AVL r,int *verif) | |
208 | { | |
209 | AVL q; | |
210 | if (r->droit == NULL) {p->cle = r->cle; | |
211 | q = r; /* q : l'element a supprimer par free */ | |
212 | r = r->gauche; | |
213 | free(q); | |
214 | *verif = 1; | |
215 | } | |
216 | else {r->droit = supmax(p,r->droit,verif); | |
217 | if (*verif) r = equidroit(r,verif); | |
218 | } | |
219 | return r; | |
220 | } | |
221 | ||
222 | ||
223 | /*****************************************************************************/ | |
224 | AVL supprime(AVL p,int x,int *verif) | |
225 | { | |
226 | AVL q; | |
227 | ||
228 | if (p == NULL) | |
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); | |
237 | } | |
238 | } | |
239 | else if (x < p->cle) | |
240 | {p->gauche = supprime(p->gauche,x,verif); | |
241 | if (*verif) p = equigauche(p,verif); | |
242 | } | |
243 | else {p->droit = supprime(p->droit,x,verif); | |
244 | if (*verif) p = equidroit(p,verif); | |
245 | } | |
246 | return p; | |
247 | } | |
248 | ||
249 | ||
250 | /*****************************************************************************/ | |
251 | void affiche_arbre(AVL p, int col) | |
252 | { | |
253 | int i; char esp=' '; | |
254 | if (p) | |
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); | |
259 | }; | |
260 | } | |
261 | ||
262 | ||
263 | ||
264 | /*****************************************************************************/ | |
265 | main() | |
266 | {AVL rac=NULL; | |
267 | int x; | |
268 | int verif; | |
269 | do {printf("Entrez une cle: ");scanf("%d",&x); | |
270 | if (x) {printf("Insertion de la cle %6d\n",x); | |
271 | verif = 0; | |
272 | rac = insere(rac,x,&verif); | |
273 | affiche_arbre(rac,0); | |
274 | } | |
275 | } | |
276 | while (x); | |
277 | ||
278 | do {printf("Entrez une cle: ");scanf("%d",&x); | |
279 | if (x) {printf("Suppression de la cle %6d\n",x); | |
280 | verif = 0; | |
281 | rac = supprime(rac,x,&verif); | |
282 | affiche_arbre(rac,0); | |
283 | } | |
284 | } | |
285 | while (x); | |
286 | } | |
287 | /*****************************************************************************/ | |
288 |