--- /dev/null
+/*****************************************************************************/
+/* AVL */
+/*****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef int t_cle;
+
+typedef struct noeud {
+ t_cle cle;
+ int deseq; /* deseq = hauteur du ss-abre gauche
+ - hauteur du ss-arbre droit */
+ struct noeud *gauche, *droit;
+ } N_AVL, *AVL;
+
+
+/*****************************************************************************/
+AVL RG(AVL a)
+{
+ AVL b;
+ b = a->droit;
+ a->droit = b->gauche;
+ b->gauche = a;
+ return b;
+}
+
+
+/*****************************************************************************/
+AVL RD(AVL a)
+{
+ AVL b;
+ b = a->gauche;
+ a->gauche = b->droit;
+ b->droit = a;
+ return b;
+}
+
+
+/*****************************************************************************/
+AVL RGD(AVL a)
+{
+ a->gauche=RG(a->gauche);
+ return(RD(a));
+}
+
+
+/*****************************************************************************/
+AVL RDG(AVL a)
+{
+ a->droit=RD(a->droit);
+ return(RG(a));
+}
+
+
+/*****************************************************************************/
+AVL insere(AVL p,int x,int *verif)
+{
+ if (p == NULL)
+ {p = (N_AVL *)malloc(sizeof(N_AVL));
+ if (p==NULL) exit(-1);
+ p->cle = x;p->gauche = NULL;p->droit = NULL;
+ p->deseq = 0; *verif = 1;
+ }
+ else if (x == p->cle)
+ printf("Insertion impossible ! %d est deja dans l'arbre\n",x);
+
+ else if (x < p->cle)
+ {p->gauche = insere(p->gauche,x,verif);
+ if (*verif) {/* on a insere a gauche */
+ switch (p->deseq)
+ {case -1 : p->deseq = 0; *verif = 0; break;
+ case 0 : p->deseq = 1; break;
+ case 1 : // reequilibrage
+ if (p->gauche->deseq==1)
+ {// rotation droite
+ printf("RD pour %6d\n",p->cle);
+ p=RD(p);
+ p->deseq = p->droit->deseq = 0;
+ *verif = 0;
+ }
+ else {/* rotation gauche droite */
+ printf("RGD pour %6d\n",p->cle);
+ p=RGD(p);
+ switch (p->deseq)
+ {case -1 : p->droit->deseq=0;
+ p->gauche->deseq=1;
+ break;
+ case 0 : p->droit->deseq=0;
+ p->gauche->deseq=0;
+ break;
+ case 1 : p->droit->deseq=-1;
+ p->gauche->deseq=0;
+ }
+ p->deseq=0; *verif=0;
+ }
+ break;
+ }
+
+ }
+ }
+ else
+ {p->droit = insere(p->droit,x,verif);
+ if (*verif) {/* on a insere a droite */
+ switch (p->deseq)
+ {case 1 : p->deseq = 0; *verif = 0; break;
+ case 0 : p->deseq = -1; break;
+ case -1 : // reequilibrage
+ if (p->droit->deseq==-1)
+ {/* rotation gauche */
+ printf("RG pour %6d\n",p->cle);
+ p=RG(p);
+ p->deseq = p->gauche->deseq = 0;
+ *verif = 0;
+ }
+ else {/* rotation droite gauche */
+ printf("RDG pour %6d\n",p->cle);
+ p=RDG(p);
+ switch (p->deseq)
+ {case 1 : p->droit->deseq=-1;
+ p->gauche->deseq=0;
+ break;
+ case 0 : p->droit->deseq=0;
+ p->gauche->deseq=0;
+ break;
+ case -1 : p->droit->deseq=0;
+ p->gauche->deseq=1;
+ }
+ p->deseq=0; *verif=0;
+ }
+ break;
+ }
+ }
+ }
+ return(p);
+}
+
+
+/*****************************************************************************/
+AVL equigauche(AVL p,int *verif)
+/* quand on entre dans la fonction, *verif = 1 */
+{
+ switch (p->deseq)
+ {case 1 : p->deseq = 0; break;
+ case 0 : p->deseq = -1; *verif = 0; break;
+ case -1 : /* reequilibrage */
+ if (p->droit->deseq <= 0)
+ {/* rotation gauche */
+ printf("RG pour %6d\n",p->cle);
+ p = RG(p);
+ if (p->deseq == 0) {p->gauche->deseq = -1; p->deseq = 1;
+ *verif=0;}
+ else {//forcement p->deseq = -1
+ p->deseq = p->gauche->deseq = 0; }
+ }
+ else
+ {/* rotation droite gauche */
+ printf("RDG pour %6d\n",p->cle);
+ p = RDG(p);
+ switch (p->deseq)
+ {case 0 : p->droit->deseq = p->gauche->deseq =0; break;
+ case 1 : p->droit->deseq = -1; p->gauche->deseq = 0;
+ break;
+ case -1 : p->droit->deseq = 0; p->gauche->deseq = 1;
+ }
+ p->deseq = 0;
+ }
+ }
+return p;
+}
+
+
+/*****************************************************************************/
+AVL equidroit(AVL p,int *verif) // quand on entre dans la fonction, verif = 1
+{
+ switch (p->deseq)
+ {case -1 : p->deseq = 0; break;
+ case 0 : p->deseq = 1; *verif = 0; break;
+ case 1 : /* reequilibrage */
+ if (p->gauche->deseq >= 0)
+ {/* rotation droite */
+ printf("RD pour %6d\n",p->cle);
+ p = RD(p);
+ if (p->deseq == 0) {p->droit->deseq = 1; p->deseq = -1;
+ *verif=0; }
+ else {/* forcement p->deseq = 1 */
+ p->deseq = p->droit->deseq = 0; }
+ }
+ else
+ {/* rotation gauche droite */
+ printf("RGD pour %6d\n",p->cle);
+ p = RGD(p);
+ switch (p->deseq)
+ {case 0 : p->gauche->deseq = p->droit->deseq =0; break;
+ case 1 : p->gauche->deseq = 0; p->droit->deseq = -1;
+ break;
+ case -1 : p->gauche->deseq = 1; p->droit->deseq = 0;
+ }
+ p->deseq = 0;
+ }
+ }
+return p;
+}
+
+
+/*****************************************************************************/
+AVL supmax(AVL p,AVL r,int *verif)
+{
+ AVL q;
+ if (r->droit == NULL) {p->cle = r->cle;
+ q = r; /* q : l'element a supprimer par free */
+ r = r->gauche;
+ free(q);
+ *verif = 1;
+ }
+ else {r->droit = supmax(p,r->droit,verif);
+ if (*verif) r = equidroit(r,verif);
+ }
+ return r;
+}
+
+
+/*****************************************************************************/
+AVL supprime(AVL p,int x,int *verif)
+{
+ AVL q;
+
+ if (p == NULL)
+ printf( "Suppression impossible ! %d n'est pas dans l'arbre\n",x);
+ else if (x == p->cle) { /* Suppression de p */
+ if (p->droit == NULL) {q = p; p = p->gauche;
+ free(q); *verif = 1; }
+ else if (p->gauche == NULL) {q = p; p = p->droit;
+ free(q); *verif = 1; }
+ else {p-> gauche = supmax(p,p->gauche,verif);
+ if (*verif) p = equigauche(p,verif);
+ }
+ }
+ else if (x < p->cle)
+ {p->gauche = supprime(p->gauche,x,verif);
+ if (*verif) p = equigauche(p,verif);
+ }
+ else {p->droit = supprime(p->droit,x,verif);
+ if (*verif) p = equidroit(p,verif);
+ }
+ return p;
+}
+
+
+/*****************************************************************************/
+void affiche_arbre(AVL p, int col)
+{
+ int i; char esp=' ';
+ if (p)
+ {affiche_arbre(p->droit,col+6);
+ for (i=0;i<col;i++) printf("%c",esp);
+ printf("%6d(%2d)\n",p->cle,p->deseq);
+ affiche_arbre(p->gauche,col+6);
+ };
+ }
+
+
+
+/*****************************************************************************/
+main()
+ {AVL rac=NULL;
+ int x;
+ int verif;
+ do {printf("Entrez une cle: ");scanf("%d",&x);
+ if (x) {printf("Insertion de la cle %6d\n",x);
+ verif = 0;
+ rac = insere(rac,x,&verif);
+ affiche_arbre(rac,0);
+ }
+ }
+ while (x);
+
+ do {printf("Entrez une cle: ");scanf("%d",&x);
+ if (x) {printf("Suppression de la cle %6d\n",x);
+ verif = 0;
+ rac = supprime(rac,x,&verif);
+ affiche_arbre(rac,0);
+ }
+ }
+ while (x);
+ }
+/*****************************************************************************/
+
repositories / Algorithmic_C.git / blobdiff