Add latest implementation of tree algorithm in TP6 directory

[Algorithmic_C.git] / TP6 / arbres / arbreB / arbreB.c

diff --git a/TP6/arbres/arbreB/arbreB.c b/TP6/arbres/arbreB/arbreB.c
new file mode 100644 (file)
index 0000000..291e949
--- /dev/null
+++ b/TP6/arbres/arbreB/arbreB.c
@@ -0,0 +1,136 @@
+/*****************************************************************************/
+/*                                   arbre B                                 */
+/*                         Insertion dans un B-arbre d'ordre 2               */
+/*****************************************************************************/
+#include <stdio.h>
+#include <stdlib.h>
+
+/* declarations des types C pour definir les B-arbres d'ordre 2 */
+
+#define ORDRE 2
+/* ordre du B-arbre */
+
+typedef int t_cle;
+/* les cles sont des entiers */
+
+typedef struct page    {
+                       t_cle         cle[2*ORDRE+1];
+                       struct page *fils[2*ORDRE+1];
+                       } PAGE;
+
+/* une page contient au maximum 2*ORDRE cles et a 2*ORDRE+1 fils.
+   cle[0] contient le nombre de cles contenues dans la page.
+   ces cles sont rangees dans le tableau cle[1..2*ORDRE]        */
+
+
+/*****************************************************************************/
+/* affichage d'un B-arbre                                                    */
+void affiche_B_arbre(PAGE *p, int l)
+{
+ int i; char esp=' ';
+ if (p) {for (i=1;i<=l;i++) printf("%c",esp);
+         for (i=1;i<=p->cle[0];i++) printf("%6d",p->cle[i]);
+        printf("\n");
+        for (i=0;i<=p->cle[0];i++) affiche_B_arbre(p->fils[i],l+4);
+        }
+}
+
+
+/*****************************************************************************/
+/* insertion de la cle x dans le B-arbre de racine a - v et pv designent 
+   l'element (cle+pointeur) qui remonte au niveau superieur                  */
+int insertion(t_cle x, PAGE *a, t_cle *v, PAGE **pv)
+{
+ int h=0, gauche, droit, milieu, i, m;
+ t_cle u;
+ PAGE *pu, *b;
+ 
+if (a==NULL) {*v=x;*pv=NULL;h=1;}
+else {/*recherche dichotomique */
+      gauche=1; droit=a->cle[0];
+      do {milieu = (gauche+droit)/2;
+          if (x<=a->cle[milieu]) droit=milieu-1;
+         if (x>=a->cle[milieu]) gauche=milieu+1;
+      } while(gauche<=droit);
+      if (gauche-droit==2) /* on a trouve x - on ne fait rien */ h=0;
+      else {/* x n'est pas sur cette page */
+            h=insertion(x,a->fils[droit],&u,&pu);
+           if (h) {/* insertion de u en position droit+1 */
+                   m = a->cle[0];
+                   if (m<2*ORDRE) {m++;h=0;
+                                   for (i=m;i>=droit+2;i--) /*decalage */
+                                       {a->cle[i]=a->cle[i-1];
+                                        a->fils[i]=a->fils[i-1];
+                                       }
+                                   a->cle[droit+1]=u; /* insertion */
+                                   a->fils[droit+1]=pu;
+                                   a->cle[0]=m;
+                                  }
+               else {/* la page est pleine - on la coupe en deux */
+                     b=(PAGE *) malloc(sizeof(PAGE));
+                     if (b==NULL) {printf("Erreur allocation!\n");exit(-1);
+                                  }
+                     if (droit<=ORDRE)
+                        {/* insertion de u dans la page de gauche ie dans a */
+                         if (droit==ORDRE) {*v=u;*pv=pu;}
+                         else {*v=a->cle[ORDRE];*pv=a->fils[ORDRE];
+                               for (i=ORDRE;i>=droit+2;i--) /*decalage */
+                                   {a->cle[i]=a->cle[i-1]; 
+                                    a->fils[i]=a->fils[i-1];
+                                   }
+                               a->cle[droit+1]=u; /* insertion du u dans a */
+                               a->fils[droit+1]=pu;
+                              }
+                         for (i=1;i<=ORDRE;i++) 
+                             {b->cle[i]=a->cle[i+ORDRE];
+                              b->fils[i]=a->fils[i+ORDRE];
+                             }
+                         }
+                     else {/* insertion dans la page droite */
+                           droit=droit-ORDRE;
+                           *v=a->cle[ORDRE+1];*pv=a->fils[ORDRE+1];
+                           for (i=1;i<=droit-1;i++)
+                               {b->cle[i]=a->cle[i+ORDRE+1];
+                                b->fils[i]=a->fils[i+ORDRE+1];
+                               }
+                            b->cle[droit]=u; /* insertion de u dans b */
+                            b->fils[droit]=pu;
+                            for (i=droit+1;i<=ORDRE;i++)
+                               {b->cle[i]=a->cle[i+ORDRE];
+                                b->fils[i]=a->fils[i+ORDRE];
+                               }
+                           }
+                     a->cle[0]=b->cle[0]=ORDRE;
+                     b->fils[0]=*pv; 
+                     *pv=b;
+                    }
+              }
+      }
+}
+return h;
+}
+
+
+/*****************************************************************************/
+int main()
+{
+ PAGE *rac=NULL, *pu, *q;
+ t_cle x,u;
+ int h;
+ do {printf("Entrez une cle: ");scanf("%d",&x);
+     if (x) {printf("Insertion de la cle %6d\n",x);             
+             h = insertion(x,rac,&u,&pu);
+            if (h) {q=rac; 
+                    rac=(PAGE *) malloc(sizeof(PAGE));
+                    if (rac==NULL) {printf("Erreur allocation!\n");exit(-1);
+                                   }
+                    rac->cle[0]=1;rac->fils[0]=q;
+                    rac->cle[1]=u;rac->fils[1]=pu;
+                   }
+            affiche_B_arbre(rac,1);
+     }
+    }
+ while (x);
+}
+/*****************************************************************************/
+