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;
  31     char esp = ' ';
  32     if (p) {
  33         for (i = 1; i <= l; i++)
  34             printf("%c", esp);
  35         for (i = 1; i <= p->cle[0]; i++)
  36             printf("%6d", p->cle[i]);
  37         printf("\n");
  38         for (i = 0; i <= p->cle[0]; i++)
  39             affiche_B_arbre(p->fils[i], l + 4);
  40     }
  41 }
  42
  43
  44 /*****************************************************************************/
  45 /* insertion de la cle x dans le B-arbre de racine a - v et pv designent
  46    l'element (cle+pointeur) qui remonte au niveau superieur                  */
  47 int insertion(t_cle x, PAGE * a, t_cle * v, PAGE ** pv)
  48 {
  49     int h = 0, gauche, droit, milieu, i, m;
  50     t_cle u;
  51     PAGE *pu, *b;
  52
  53     if (a == NULL) {
  54         *v = x;
  55         *pv = NULL;
  56         h = 1;
  57     } else {                    /* recherche dichotomique */
  58         gauche = 1;
  59         droit = a->cle[0];
  60         do {
  61             milieu = (gauche + droit) / 2;
  62             if (x <= a->cle[milieu])
  63                 droit = milieu - 1;
  64             if (x >= a->cle[milieu])
  65                 gauche = milieu + 1;
  66         } while (gauche <= droit);
  67         if (gauche - droit == 2)        /* on a trouve x - on ne fait rien */
  68             h = 0;
  69         else {                  /* x n'est pas sur cette page */
  70             h = insertion(x, a->fils[droit], &u, &pu);
  71             if (h) {            /* insertion de u en position droit+1 */
  72                 m = a->cle[0];
  73                 if (m < 2 * ORDRE) {
  74                     m++;
  75                     h = 0;
  76                     for (i = m; i >= droit + 2; i--) {  /* decalage */
  77                         a->cle[i] = a->cle[i - 1];
  78                         a->fils[i] = a->fils[i - 1];
  79                     }
  80                     a->cle[droit + 1] = u;      /* insertion */
  81                     a->fils[droit + 1] = pu;
  82                     a->cle[0] = m;
  83                 } else {        /* la page est pleine - on la coupe en deux */
  84                     b = (PAGE *) malloc(sizeof(PAGE));
  85                     if (b == NULL) {
  86                         printf("Erreur allocation!\n");
  87                         exit(-1);
  88                     }
  89                     if (droit <= ORDRE) {       /* insertion de u dans la page de gauche ie dans a */
  90                         if (droit == ORDRE) {
  91                             *v = u;
  92                             *pv = pu;
  93                         } else {
  94                             *v = a->cle[ORDRE];
  95                             *pv = a->fils[ORDRE];
  96                             for (i = ORDRE; i >= droit + 2; i--) {      /* decalage */
  97                                 a->cle[i] = a->cle[i - 1];
  98                                 a->fils[i] = a->fils[i - 1];
  99                             }
 100                             a->cle[droit + 1] = u;      /* insertion du u dans a */
 101                             a->fils[droit + 1] = pu;
 102                         }
 103                         for (i = 1; i <= ORDRE; i++) {
 104                             b->cle[i] = a->cle[i + ORDRE];
 105                             b->fils[i] = a->fils[i + ORDRE];
 106                         }
 107                     } else {    /* insertion dans la page droite */
 108                         droit = droit - ORDRE;
 109                         *v = a->cle[ORDRE + 1];
 110                         *pv = a->fils[ORDRE + 1];
 111                         for (i = 1; i <= droit - 1; i++) {
 112                             b->cle[i] = a->cle[i + ORDRE + 1];
 113                             b->fils[i] = a->fils[i + ORDRE + 1];
 114                         }
 115                         b->cle[droit] = u;      /* insertion de u dans b */
 116                         b->fils[droit] = pu;
 117                         for (i = droit + 1; i <= ORDRE; i++) {
 118                             b->cle[i] = a->cle[i + ORDRE];
 119                             b->fils[i] = a->fils[i + ORDRE];
 120                         }
 121                     }
 122                     a->cle[0] = b->cle[0] = ORDRE;
 123                     b->fils[0] = *pv;
 124                     *pv = b;
 125                 }
 126             }
 127         }
 128     }
 129     return h;
 130 }
 131
 132
 133 /*****************************************************************************/
 134 int main()
 135 {
 136     PAGE *rac = NULL, *pu, *q;
 137     t_cle x, u;
 138     int h;
 139     do {
 140         printf("Entrez une cle: ");
 141         scanf("%d", &x);
 142         if (x) {
 143             printf("Insertion de la cle %6d\n", x);
 144             h = insertion(x, rac, &u, &pu);
 145             if (h) {
 146                 q = rac;
 147                 rac = (PAGE *) malloc(sizeof(PAGE));
 148                 if (rac == NULL) {
 149                     printf("Erreur allocation!\n");
 150                     exit(-1);
 151                 }
 152                 rac->cle[0] = 1;
 153                 rac->fils[0] = q;
 154                 rac->cle[1] = u;
 155                 rac->fils[1] = pu;
 156             }
 157             affiche_B_arbre(rac, 1);
 158         }
 159     }
 160     while (x);
 161 }
 162
 163 /*****************************************************************************/