Commit | Line | Data |
---|---|---|
249ff697 JB |
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 | ||
760a8310 JB |
16 | typedef struct page { |
17 | t_cle cle[2 * ORDRE + 1]; | |
18 | struct page *fils[2 * ORDRE + 1]; | |
19 | } PAGE; | |
249ff697 JB |
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 */ | |
760a8310 | 28 | void affiche_B_arbre(PAGE * p, int l) |
249ff697 | 29 | { |
760a8310 JB |
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 | } | |
249ff697 JB |
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 */ | |
760a8310 | 47 | int insertion(t_cle x, PAGE * a, t_cle * v, PAGE ** pv) |
249ff697 | 48 | { |
760a8310 JB |
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; | |
249ff697 JB |
130 | } |
131 | ||
132 | ||
133 | /*****************************************************************************/ | |
134 | int main() | |
135 | { | |
760a8310 JB |
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 | } | |
249ff697 | 159 | } |
760a8310 | 160 | while (x); |
249ff697 | 161 | } |
249ff697 | 162 | |
760a8310 | 163 | /*****************************************************************************/ |