X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=TP6%2Farbres%2FAVL%2FAVL.c;h=dbf991f844927cbac46ef86c357ff8f60d31dd50;hb=26317590ee567f7cd092fc2fa85381545a63c63d;hp=d5f58b851cc9c0ac2b9a28c56f3e0e513c394104;hpb=249ff69760892dc8b5337bee9ad672c79325a42b;p=Algorithmic_C.git

diff --git a/TP6/arbres/AVL/AVL.c b/TP6/arbres/AVL/AVL.c
index d5f58b8..dbf991f 100644
--- a/TP6/arbres/AVL/AVL.c
+++ b/TP6/arbres/AVL/AVL.c
@@ -8,281 +8,331 @@
 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;
-
+    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 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 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));
+    a->gauche = RG(a->gauche);
+    return (RD(a));
 }
 
-
 /*****************************************************************************/
 AVL RDG(AVL a)
 {
- a->droit=RD(a->droit);
- return(RG(a));
+    a->droit = RD(a->droit);
+    return (RG(a));
 }
 
-
 /*****************************************************************************/
-AVL insere(AVL p,int x,int *verif)
+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;
+    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;
 		    }
-		     	       
-	        }
-	       }
-            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);			  
-}
+		    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) 
+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; 
-		  }
+    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;
+    }
+    return p;
 }
 
-
 /*****************************************************************************/
-AVL equidroit(AVL p,int *verif) // quand on entre dans la fonction, verif = 1
+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;
+    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 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 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 supprime(AVL p, int x, int *verif)
 {
- AVL q;
+    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;       
+    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);
-    };  	
- }
-
+    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);
+{
+    AVL rac = NULL;
+    int x;
+    int verif;
 
-  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);
- }
-/*****************************************************************************/
+    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);
+}
+
+/*****************************************************************************/