1 /*****************************************************************************/
3 /* Insertion dans un B-arbre d'ordre 2 */
4 /*****************************************************************************/
8 /* declarations des types C pour definir les B-arbres d'ordre 2 */
11 /* ordre du B-arbre */
14 /* les cles sont des entiers */
18 struct page
*fils
[2*ORDRE
+1];
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] */
26 /*****************************************************************************/
27 /* affichage d'un B-arbre */
28 void affiche_B_arbre(PAGE
*p
, int l
)
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
]);
34 for (i
=0;i
<=p
->cle
[0];i
++) affiche_B_arbre(p
->fils
[i
],l
+4);
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
)
44 int h
=0, gauche
, droit
, milieu
, i
, m
;
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 */
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];
65 a
->cle
[droit
+1]=u
; /* insertion */
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);
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];
81 a
->cle
[droit
+1]=u
; /* insertion du u dans a */
84 for (i
=1;i
<=ORDRE
;i
++)
85 {b
->cle
[i
]=a
->cle
[i
+ORDRE
];
86 b
->fils
[i
]=a
->fils
[i
+ORDRE
];
89 else {/* insertion dans la page droite */
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];
96 b
->cle
[droit
]=u
; /* insertion de u dans b */
98 for (i
=droit
+1;i
<=ORDRE
;i
++)
99 {b
->cle
[i
]=a
->cle
[i
+ORDRE
];
100 b
->fils
[i
]=a
->fils
[i
+ORDRE
];
103 a
->cle
[0]=b
->cle
[0]=ORDRE
;
114 /*****************************************************************************/
117 PAGE
*rac
=NULL
, *pu
, *q
;
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
);
124 rac
=(PAGE
*) malloc(sizeof(PAGE
));
125 if (rac
==NULL
) {printf("Erreur allocation!\n");exit(-1);
127 rac
->cle
[0]=1;rac
->fils
[0]=q
;
128 rac
->cle
[1]=u
;rac
->fils
[1]=pu
;
130 affiche_B_arbre(rac
,1);
135 /*****************************************************************************/