TP6/arbres/arbreB/arbreB.c

   1 /*****************************************************************************/
   2 /*                                   arbre B                                 */
   3 /*                         Insertion dans un B-arbre d'ordre 2               */
   4 /*****************************************************************************/
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 /* declarations des types C pour definir les B-arbres d'ordre 2 */
   9
  10 #define ORDRE 2
  11 /* ordre du B-arbre */
  12
  13 typedef int t_cle;
  14 /* les cles sont des entiers */
  15
  16 typedef struct page     {
  17                         t_cle         cle[2*ORDRE+1];
  18                         struct page *fils[2*ORDRE+1];
  19                         } PAGE;
  20
  21 /* une page contient au maximum 2*ORDRE cles et a 2*ORDRE+1 fils.
  22    cle[0] contient le nombre de cles contenues dans la page.
  23    ces cles sont rangees dans le tableau cle[1..2*ORDRE]        */
  24
  25
  26 /*****************************************************************************/
  27 /* affichage d'un B-arbre                                                    */
  28 void affiche_B_arbre(PAGE *p, int l)
  29 {
  30  int i; char esp=' ';
  31  if (p) {for (i=1;i<=l;i++) printf("%c",esp);
  32          for (i=1;i<=p->cle[0];i++) printf("%6d",p->cle[i]);
  33          printf("\n");
  34          for (i=0;i<=p->cle[0];i++) affiche_B_arbre(p->fils[i],l+4);
  35         }
  36 }
  37
  38
  39 /*****************************************************************************/
  40 /* insertion de la cle x dans le B-arbre de racine a - v et pv designent
  41    l'element (cle+pointeur) qui remonte au niveau superieur                  */
  42 int insertion(t_cle x, PAGE *a, t_cle *v, PAGE **pv)
  43 {
  44  int h=0, gauche, droit, milieu, i, m;
  45  t_cle u;
  46  PAGE *pu, *b;
  47
  48 if (a==NULL) {*v=x;*pv=NULL;h=1;}
  49 else {/*recherche dichotomique */
  50       gauche=1; droit=a->cle[0];
  51       do {milieu = (gauche+droit)/2;
  52           if (x<=a->cle[milieu]) droit=milieu-1;
  53           if (x>=a->cle[milieu]) gauche=milieu+1;
  54       } while(gauche<=droit);
  55       if (gauche-droit==2) /* on a trouve x - on ne fait rien */ h=0;
  56       else {/* x n'est pas sur cette page */
  57             h=insertion(x,a->fils[droit],&u,&pu);
  58             if (h) {/* insertion de u en position droit+1 */
  59                     m = a->cle[0];
  60                     if (m<2*ORDRE) {m++;h=0;
  61                                     for (i=m;i>=droit+2;i--) /*decalage */
  62                                         {a->cle[i]=a->cle[i-1];
  63                                          a->fils[i]=a->fils[i-1];
  64                                         }
  65                                     a->cle[droit+1]=u; /* insertion */
  66                                     a->fils[droit+1]=pu;
  67                                     a->cle[0]=m;
  68                                    }
  69                 else {/* la page est pleine - on la coupe en deux */
  70                       b=(PAGE *) malloc(sizeof(PAGE));
  71                       if (b==NULL) {printf("Erreur allocation!\n");exit(-1);
  72                                    }
  73                       if (droit<=ORDRE)
  74                          {/* insertion de u dans la page de gauche ie dans a */
  75                           if (droit==ORDRE) {*v=u;*pv=pu;}
  76                           else {*v=a->cle[ORDRE];*pv=a->fils[ORDRE];
  77                                 for (i=ORDRE;i>=droit+2;i--) /*decalage */
  78                                     {a->cle[i]=a->cle[i-1];
  79                                      a->fils[i]=a->fils[i-1];
  80                                     }
  81                                 a->cle[droit+1]=u; /* insertion du u dans a */
  82                                 a->fils[droit+1]=pu;
  83                                }
  84                           for (i=1;i<=ORDRE;i++)
  85                               {b->cle[i]=a->cle[i+ORDRE];
  86                                b->fils[i]=a->fils[i+ORDRE];
  87                               }
  88                           }
  89                       else {/* insertion dans la page droite */
  90                             droit=droit-ORDRE;
  91                             *v=a->cle[ORDRE+1];*pv=a->fils[ORDRE+1];
  92                             for (i=1;i<=droit-1;i++)
  93                                 {b->cle[i]=a->cle[i+ORDRE+1];
  94                                  b->fils[i]=a->fils[i+ORDRE+1];
  95                                 }
  96                              b->cle[droit]=u; /* insertion de u dans b */
  97                              b->fils[droit]=pu;
  98                              for (i=droit+1;i<=ORDRE;i++)
  99                                 {b->cle[i]=a->cle[i+ORDRE];
 100                                  b->fils[i]=a->fils[i+ORDRE];
 101                                 }
 102                             }
 103                       a->cle[0]=b->cle[0]=ORDRE;
 104                       b->fils[0]=*pv;
 105                       *pv=b;
 106                      }
 107                }
 108       }
 109 }
 110 return h;
 111 }
 112
 113
 114 /*****************************************************************************/
 115 int main()
 116 {
 117  PAGE *rac=NULL, *pu, *q;
 118  t_cle x,u;
 119  int h;
 120  do {printf("Entrez une cle: ");scanf("%d",&x);
 121      if (x) {printf("Insertion de la cle %6d\n",x);
 122              h = insertion(x,rac,&u,&pu);
 123              if (h) {q=rac;
 124                      rac=(PAGE *) malloc(sizeof(PAGE));
 125                      if (rac==NULL) {printf("Erreur allocation!\n");exit(-1);
 126                                     }
 127                      rac->cle[0]=1;rac->fils[0]=q;
 128                      rac->cle[1]=u;rac->fils[1]=pu;
 129                     }
 130              affiche_B_arbre(rac,1);
 131      }
 132     }
 133  while (x);
 134 }
 135 /*****************************************************************************/
 136