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