| 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 | /*****************************************************************************/ |