TP6: Use K&R coding style

[Algorithmic_C.git] / TP6 / arbres / arbreB / arbreB.c

/*****************************************************************************/
/*                                   arbre B                                 */
/*                         Insertion dans un B-arbre d'ordre 2               */
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>

/* declarations des types C pour definir les B-arbres d'ordre 2 */

#define ORDRE 2
/* ordre du B-arbre */

typedef int t_cle;
/* les cles sont des entiers */

typedef struct page {
    t_cle cle[2 * ORDRE + 1];
    struct page *fils[2 * ORDRE + 1];
} PAGE;

/* une page contient au maximum 2*ORDRE cles et a 2*ORDRE+1 fils.
   cle[0] contient le nombre de cles contenues dans la page.
   ces cles sont rangees dans le tableau cle[1..2*ORDRE]        */


/*****************************************************************************/
/* affichage d'un B-arbre                                                    */
void affiche_B_arbre(PAGE * p, int l)
{
    int i;
    char esp = ' ';
    if (p) {
	for (i = 1; i <= l; i++)
	    printf("%c", esp);
	for (i = 1; i <= p->cle[0]; i++)
	    printf("%6d", p->cle[i]);
	printf("\n");
	for (i = 0; i <= p->cle[0]; i++)
	    affiche_B_arbre(p->fils[i], l + 4);
    }
}


/*****************************************************************************/
/* insertion de la cle x dans le B-arbre de racine a - v et pv designent 
   l'element (cle+pointeur) qui remonte au niveau superieur                  */
int insertion(t_cle x, PAGE * a, t_cle * v, PAGE ** pv)
{
    int h = 0, gauche, droit, milieu, i, m;
    t_cle u;
    PAGE *pu, *b;

    if (a == NULL) {
	*v = x;
	*pv = NULL;
	h = 1;
    } else {			/* recherche dichotomique */
	gauche = 1;
	droit = a->cle[0];
	do {
	    milieu = (gauche + droit) / 2;
	    if (x <= a->cle[milieu])
		droit = milieu - 1;
	    if (x >= a->cle[milieu])
		gauche = milieu + 1;
	} while (gauche <= droit);
	if (gauche - droit == 2)	/* on a trouve x - on ne fait rien */
	    h = 0;
	else {			/* x n'est pas sur cette page */
	    h = insertion(x, a->fils[droit], &u, &pu);
	    if (h) {		/* insertion de u en position droit+1 */
		m = a->cle[0];
		if (m < 2 * ORDRE) {
		    m++;
		    h = 0;
		    for (i = m; i >= droit + 2; i--) {	/* decalage */
			a->cle[i] = a->cle[i - 1];
			a->fils[i] = a->fils[i - 1];
		    }
		    a->cle[droit + 1] = u;	/* insertion */
		    a->fils[droit + 1] = pu;
		    a->cle[0] = m;
		} else {	/* la page est pleine - on la coupe en deux */
		    b = (PAGE *) malloc(sizeof(PAGE));
		    if (b == NULL) {
			printf("Erreur allocation!\n");
			exit(-1);
		    }
		    if (droit <= ORDRE) {	/* insertion de u dans la page de gauche ie dans a */
			if (droit == ORDRE) {
			    *v = u;
			    *pv = pu;
			} else {
			    *v = a->cle[ORDRE];
			    *pv = a->fils[ORDRE];
			    for (i = ORDRE; i >= droit + 2; i--) {	/* decalage */
				a->cle[i] = a->cle[i - 1];
				a->fils[i] = a->fils[i - 1];
			    }
			    a->cle[droit + 1] = u;	/* insertion du u dans a */
			    a->fils[droit + 1] = pu;
			}
			for (i = 1; i <= ORDRE; i++) {
			    b->cle[i] = a->cle[i + ORDRE];
			    b->fils[i] = a->fils[i + ORDRE];
			}
		    } else {	/* insertion dans la page droite */
			droit = droit - ORDRE;
			*v = a->cle[ORDRE + 1];
			*pv = a->fils[ORDRE + 1];
			for (i = 1; i <= droit - 1; i++) {
			    b->cle[i] = a->cle[i + ORDRE + 1];
			    b->fils[i] = a->fils[i + ORDRE + 1];
			}
			b->cle[droit] = u;	/* insertion de u dans b */
			b->fils[droit] = pu;
			for (i = droit + 1; i <= ORDRE; i++) {
			    b->cle[i] = a->cle[i + ORDRE];
			    b->fils[i] = a->fils[i + ORDRE];
			}
		    }
		    a->cle[0] = b->cle[0] = ORDRE;
		    b->fils[0] = *pv;
		    *pv = b;
		}
	    }
	}
    }
    return h;
}


/*****************************************************************************/
int main()
{
    PAGE *rac = NULL, *pu, *q;
    t_cle x, u;
    int h;
    do {
	printf("Entrez une cle: ");
	scanf("%d", &x);
	if (x) {
	    printf("Insertion de la cle %6d\n", x);
	    h = insertion(x, rac, &u, &pu);
	    if (h) {
		q = rac;
		rac = (PAGE *) malloc(sizeof(PAGE));
		if (rac == NULL) {
		    printf("Erreur allocation!\n");
		    exit(-1);
		}
		rac->cle[0] = 1;
		rac->fils[0] = q;
		rac->cle[1] = u;
		rac->fils[1] = pu;
	    }
	    affiche_B_arbre(rac, 1);
	}
    }
    while (x);
}

/*****************************************************************************/