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

/*****************************************************************************/
/* 		                       AVL  	                             */
/*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef int t_cle;

typedef struct noeud {
    t_cle cle;
    int deseq;			/* deseq = hauteur du ss-abre gauche - hauteur du ss-arbre droit */
    struct noeud *gauche, *droit;
} N_AVL, *AVL;

/*****************************************************************************/
AVL RG(AVL a)
{
    AVL b;

    b = a->droit;
    a->droit = b->gauche;
    b->gauche = a;
    return b;
}

/*****************************************************************************/
AVL RD(AVL a)
{
    AVL b;

    b = a->gauche;
    a->gauche = b->droit;
    b->droit = a;
    return b;
}

/*****************************************************************************/
AVL RGD(AVL a)
{
    a->gauche = RG(a->gauche);
    return (RD(a));
}

/*****************************************************************************/
AVL RDG(AVL a)
{
    a->droit = RD(a->droit);
    return (RG(a));
}

/*****************************************************************************/
AVL insere(AVL p, int x, int *verif)
{
    if (p == NULL) {
	p = (N_AVL *) malloc(sizeof(N_AVL));
	if (p == NULL)
	    exit(-1);
	p->cle = x;
	p->gauche = NULL;
	p->droit = NULL;
	p->deseq = 0;
	*verif = 1;
    } else if (x == p->cle)
	printf("Insertion impossible ! %d est deja dans l'arbre\n", x);

    else if (x < p->cle) {
	p->gauche = insere(p->gauche, x, verif);
	if (*verif) {		/* on a insere a gauche */
	    switch (p->deseq) {
	    case -1:
		p->deseq = 0;
		*verif = 0;
		break;
	    case 0:
		p->deseq = 1;
		break;
	    case 1:		// reequilibrage
		if (p->gauche->deseq == 1) {	// rotation droite
		    printf("RD pour %6d\n", p->cle);
		    p = RD(p);
		    p->deseq = p->droit->deseq = 0;
		    *verif = 0;
		} else {	/* rotation gauche droite */
		    printf("RGD pour %6d\n", p->cle);
		    p = RGD(p);
		    switch (p->deseq) {
		    case -1:
			p->droit->deseq = 0;
			p->gauche->deseq = 1;
			break;
		    case 0:
			p->droit->deseq = 0;
			p->gauche->deseq = 0;
			break;
		    case 1:
			p->droit->deseq = -1;
			p->gauche->deseq = 0;
		    }
		    p->deseq = 0;
		    *verif = 0;
		}
		break;
	    }

	}
    } else {
	p->droit = insere(p->droit, x, verif);
	if (*verif) {		/* on a insere a droite */
	    switch (p->deseq) {
	    case 1:
		p->deseq = 0;
		*verif = 0;
		break;
	    case 0:
		p->deseq = -1;
		break;
	    case -1:		// reequilibrage
		if (p->droit->deseq == -1) {	/* rotation gauche */
		    printf("RG pour %6d\n", p->cle);
		    p = RG(p);
		    p->deseq = p->gauche->deseq = 0;
		    *verif = 0;
		} else {	/* rotation droite gauche */
		    printf("RDG pour %6d\n", p->cle);
		    p = RDG(p);
		    switch (p->deseq) {
		    case 1:
			p->droit->deseq = -1;
			p->gauche->deseq = 0;
			break;
		    case 0:
			p->droit->deseq = 0;
			p->gauche->deseq = 0;
			break;
		    case -1:
			p->droit->deseq = 0;
			p->gauche->deseq = 1;
		    }
		    p->deseq = 0;
		    *verif = 0;
		}
		break;
	    }
	}
    }
    return (p);
}

/*****************************************************************************/
AVL equigauche(AVL p, int *verif)
/* quand on entre dans la fonction, *verif = 1 */
{
    switch (p->deseq) {
    case 1:
	p->deseq = 0;
	break;
    case 0:
	p->deseq = -1;
	*verif = 0;
	break;
    case -1:			/* reequilibrage */
	if (p->droit->deseq <= 0) {	/* rotation gauche */
	    printf("RG pour %6d\n", p->cle);
	    p = RG(p);
	    if (p->deseq == 0) {
		p->gauche->deseq = -1;
		p->deseq = 1;
		*verif = 0;
	    } else {		// forcement p->deseq = -1
		p->deseq = p->gauche->deseq = 0;
	    }
	} else {		/* rotation droite gauche */
	    printf("RDG pour %6d\n", p->cle);
	    p = RDG(p);
	    switch (p->deseq) {
	    case 0:
		p->droit->deseq = p->gauche->deseq = 0;
		break;
	    case 1:
		p->droit->deseq = -1;
		p->gauche->deseq = 0;
		break;
	    case -1:
		p->droit->deseq = 0;
		p->gauche->deseq = 1;
	    }
	    p->deseq = 0;
	}
    }
    return p;
}

/*****************************************************************************/
AVL equidroit(AVL p, int *verif)	// quand on entre dans la fonction, *verif = 1
{
    switch (p->deseq) {
    case -1:
	p->deseq = 0;
	break;
    case 0:
	p->deseq = 1;
	*verif = 0;
	break;
    case 1:			/* reequilibrage */
	if (p->gauche->deseq >= 0) {	/* rotation droite */
	    printf("RD pour %6d\n", p->cle);
	    p = RD(p);
	    if (p->deseq == 0) {
		p->droit->deseq = 1;
		p->deseq = -1;
		*verif = 0;
	    } else {		/* forcement p->deseq = 1 */
		p->deseq = p->droit->deseq = 0;
	    }
	} else {		/* rotation gauche droite */
	    printf("RGD pour %6d\n", p->cle);
	    p = RGD(p);
	    switch (p->deseq) {
	    case 0:
		p->gauche->deseq = p->droit->deseq = 0;
		break;
	    case 1:
		p->gauche->deseq = 0;
		p->droit->deseq = -1;
		break;
	    case -1:
		p->gauche->deseq = 1;
		p->droit->deseq = 0;
	    }
	    p->deseq = 0;
	}
    }
    return p;
}

/*****************************************************************************/
AVL supmax(AVL p, AVL r, int *verif)
{
    AVL q;

    if (r->droit == NULL) {
	p->cle = r->cle;
	q = r;			/* q : l'element a supprimer par free */
	r = r->gauche;
	free(q);
	*verif = 1;
    } else {
	r->droit = supmax(p, r->droit, verif);
	if (*verif)
	    r = equidroit(r, verif);
    }
    return r;
}

/*****************************************************************************/
AVL supprime(AVL p, int x, int *verif)
{
    AVL q;

    if (p == NULL)
	printf("Suppression impossible ! %d n'est pas dans l'arbre\n", x);
    else if (x == p->cle) {	/* Suppression de p */
	if (p->droit == NULL) {
	    q = p;
	    p = p->gauche;
	    free(q);
	    *verif = 1;
	} else if (p->gauche == NULL) {
	    q = p;
	    p = p->droit;
	    free(q);
	    *verif = 1;
	} else {
	    p->gauche = supmax(p, p->gauche, verif);
	    if (*verif)
		p = equigauche(p, verif);
	}
    } else if (x < p->cle) {
	p->gauche = supprime(p->gauche, x, verif);
	if (*verif)
	    p = equigauche(p, verif);
    } else {
	p->droit = supprime(p->droit, x, verif);
	if (*verif)
	    p = equidroit(p, verif);
    }
    return p;
}

/*****************************************************************************/
void affiche_arbre(AVL p, int col)
{
    int i;
    char esp = ' ';

    if (p) {
	affiche_arbre(p->droit, col + 6);
	for (i = 0; i < col; i++)
	    printf("%c", esp);
	printf("%6d(%2d)\n", p->cle, p->deseq);
	affiche_arbre(p->gauche, col + 6);
    };
}

/*****************************************************************************/
main()
{
    AVL rac = NULL;
    int x;
    int verif;

    do {
	printf("Entrez une cle: ");
	scanf("%d", &x);
	if (x) {
	    printf("Insertion de la cle %6d\n", x);
	    verif = 0;
	    rac = insere(rac, x, &verif);
	    affiche_arbre(rac, 0);
	}
    }
    while (x);

    do {
	printf("Entrez une cle: ");
	scanf("%d", &x);
	if (x) {
	    printf("Suppression de la cle %6d\n", x);
	    verif = 0;
	    rac = supprime(rac, x, &verif);
	    affiche_arbre(rac, 0);
	}
    }
    while (x);
}

/*****************************************************************************/
Commit	Line	Data
249ff697 JB	1	/*****************************************************************************/
	2	/* AVL */
	3	/*****************************************************************************/
	4
	5	#include <stdio.h>
	6	#include <stdlib.h>
	7
	8	typedef int t_cle;
	9
	10	typedef struct noeud {
7b0cef36 JB	11	t_cle cle;
	12	int deseq; /* deseq = hauteur du ss-abre gauche - hauteur du ss-arbre droit */
	13	struct noeud gauche, droit;
	14	} N_AVL, *AVL;
249ff697 JB	15
	16	/*****************************************************************************/
	17	AVL RG(AVL a)
	18	{
7b0cef36	19	AVL b;
249ff697	20
7b0cef36 JB	21	b = a->droit;
	22	a->droit = b->gauche;
	23	b->gauche = a;
	24	return b;
	25	}
249ff697 JB	26
	27	/*****************************************************************************/
	28	AVL RD(AVL a)
	29	{
7b0cef36	30	AVL b;
249ff697	31
7b0cef36 JB	32	b = a->gauche;
	33	a->gauche = b->droit;
	34	b->droit = a;
	35	return b;
	36	}
249ff697 JB	37
	38	/*****************************************************************************/
	39	AVL RGD(AVL a)
	40	{
7b0cef36 JB	41	a->gauche = RG(a->gauche);
7b0cef36 JB	42	return (RD(a));
249ff697 JB	43	}
249ff697 JB	44
249ff697 JB	45	/*****************************************************************************/
	46	AVL RDG(AVL a)
	47	{
7b0cef36 JB	48	a->droit = RD(a->droit);
7b0cef36 JB	49	return (RG(a));
249ff697 JB	50	}
249ff697 JB	51
249ff697	52	/*****************************************************************************/
7b0cef36	53	AVL insere(AVL p, int x, int *verif)
249ff697	54	{
7b0cef36 JB	55	if (p == NULL) {
	56	p = (N_AVL *) malloc(sizeof(N_AVL));
	57	if (p == NULL)
	58	exit(-1);
	59	p->cle = x;
	60	p->gauche = NULL;
	61	p->droit = NULL;
	62	p->deseq = 0;
	63	*verif = 1;
	64	} else if (x == p->cle)
	65	printf("Insertion impossible ! %d est deja dans l'arbre\n", x);
	66
	67	else if (x < p->cle) {
	68	p->gauche = insere(p->gauche, x, verif);
	69	if (verif) { / on a insere a gauche */
	70	switch (p->deseq) {
	71	case -1:
	72	p->deseq = 0;
	73	*verif = 0;
	74	break;
	75	case 0:
	76	p->deseq = 1;
	77	break;
	78	case 1: // reequilibrage
	79	if (p->gauche->deseq == 1) { // rotation droite
	80	printf("RD pour %6d\n", p->cle);
	81	p = RD(p);
	82	p->deseq = p->droit->deseq = 0;
	83	*verif = 0;
	84	} else { /* rotation gauche droite */
	85	printf("RGD pour %6d\n", p->cle);
	86	p = RGD(p);
	87	switch (p->deseq) {
	88	case -1:
	89	p->droit->deseq = 0;
	90	p->gauche->deseq = 1;
	91	break;
	92	case 0:
	93	p->droit->deseq = 0;
	94	p->gauche->deseq = 0;
	95	break;
	96	case 1:
	97	p->droit->deseq = -1;
	98	p->gauche->deseq = 0;
249ff697	99	}
7b0cef36 JB	100	p->deseq = 0;
	101	*verif = 0;
	102	}
	103	break;
	104	}
249ff697	105
7b0cef36 JB	106	}
	107	} else {
	108	p->droit = insere(p->droit, x, verif);
	109	if (verif) { / on a insere a droite */
	110	switch (p->deseq) {
	111	case 1:
	112	p->deseq = 0;
	113	*verif = 0;
	114	break;
	115	case 0:
	116	p->deseq = -1;
	117	break;
	118	case -1: // reequilibrage
	119	if (p->droit->deseq == -1) { /* rotation gauche */
	120	printf("RG pour %6d\n", p->cle);
	121	p = RG(p);
	122	p->deseq = p->gauche->deseq = 0;
	123	*verif = 0;
	124	} else { /* rotation droite gauche */
	125	printf("RDG pour %6d\n", p->cle);
	126	p = RDG(p);
	127	switch (p->deseq) {
	128	case 1:
	129	p->droit->deseq = -1;
	130	p->gauche->deseq = 0;
	131	break;
	132	case 0:
	133	p->droit->deseq = 0;
	134	p->gauche->deseq = 0;
	135	break;
	136	case -1:
	137	p->droit->deseq = 0;
	138	p->gauche->deseq = 1;
	139	}
	140	p->deseq = 0;
	141	*verif = 0;
	142	}
	143	break;
	144	}
	145	}
	146	}
	147	return (p);
	148	}
249ff697 JB	149
249ff697 JB	150	/*****************************************************************************/
7b0cef36	151	AVL equigauche(AVL p, int *verif)
249ff697 JB	152	/* quand on entre dans la fonction, verif = 1 /
249ff697 JB	153	{
7b0cef36 JB	154	switch (p->deseq) {
	155	case 1:
	156	p->deseq = 0;
	157	break;
	158	case 0:
	159	p->deseq = -1;
	160	*verif = 0;
	161	break;
	162	case -1: /* reequilibrage */
	163	if (p->droit->deseq <= 0) { /* rotation gauche */
	164	printf("RG pour %6d\n", p->cle);
	165	p = RG(p);
	166	if (p->deseq == 0) {
	167	p->gauche->deseq = -1;
	168	p->deseq = 1;
	169	*verif = 0;
	170	} else { // forcement p->deseq = -1
	171	p->deseq = p->gauche->deseq = 0;
	172	}
	173	} else { /* rotation droite gauche */
	174	printf("RDG pour %6d\n", p->cle);
	175	p = RDG(p);
	176	switch (p->deseq) {
	177	case 0:
	178	p->droit->deseq = p->gauche->deseq = 0;
	179	break;
	180	case 1:
	181	p->droit->deseq = -1;
	182	p->gauche->deseq = 0;
	183	break;
	184	case -1:
	185	p->droit->deseq = 0;
	186	p->gauche->deseq = 1;
	187	}
	188	p->deseq = 0;
249ff697	189	}
7b0cef36 JB	190	}
7b0cef36 JB	191	return p;
249ff697 JB	192	}
249ff697 JB	193
249ff697	194	/*****************************************************************************/
26317590	195	AVL equidroit(AVL p, int verif) // quand on entre dans la fonction, verif = 1
249ff697	196	{
7b0cef36 JB	197	switch (p->deseq) {
	198	case -1:
	199	p->deseq = 0;
	200	break;
	201	case 0:
	202	p->deseq = 1;
	203	*verif = 0;
	204	break;
	205	case 1: /* reequilibrage */
	206	if (p->gauche->deseq >= 0) { /* rotation droite */
	207	printf("RD pour %6d\n", p->cle);
	208	p = RD(p);
	209	if (p->deseq == 0) {
	210	p->droit->deseq = 1;
	211	p->deseq = -1;
	212	*verif = 0;
	213	} else { /* forcement p->deseq = 1 */
	214	p->deseq = p->droit->deseq = 0;
	215	}
	216	} else { /* rotation gauche droite */
	217	printf("RGD pour %6d\n", p->cle);
	218	p = RGD(p);
	219	switch (p->deseq) {
	220	case 0:
	221	p->gauche->deseq = p->droit->deseq = 0;
	222	break;
	223	case 1:
	224	p->gauche->deseq = 0;
	225	p->droit->deseq = -1;
	226	break;
	227	case -1:
	228	p->gauche->deseq = 1;
	229	p->droit->deseq = 0;
	230	}
	231	p->deseq = 0;
	232	}
	233	}
	234	return p;
249ff697 JB	235	}
249ff697 JB	236
249ff697	237	/*****************************************************************************/
7b0cef36	238	AVL supmax(AVL p, AVL r, int *verif)
249ff697	239	{
7b0cef36	240	AVL q;
249ff697	241
7b0cef36 JB	242	if (r->droit == NULL) {
	243	p->cle = r->cle;
	244	q = r; /* q : l'element a supprimer par free */
	245	r = r->gauche;
	246	free(q);
	247	*verif = 1;
	248	} else {
	249	r->droit = supmax(p, r->droit, verif);
	250	if (*verif)
	251	r = equidroit(r, verif);
	252	}
	253	return r;
	254	}
249ff697 JB	255
249ff697 JB	256	/*****************************************************************************/
7b0cef36	257	AVL supprime(AVL p, int x, int *verif)
249ff697	258	{
7b0cef36	259	AVL q;
249ff697	260
7b0cef36 JB	261	if (p == NULL)
	262	printf("Suppression impossible ! %d n'est pas dans l'arbre\n", x);
	263	else if (x == p->cle) { /* Suppression de p */
	264	if (p->droit == NULL) {
	265	q = p;
	266	p = p->gauche;
	267	free(q);
	268	*verif = 1;
	269	} else if (p->gauche == NULL) {
	270	q = p;
	271	p = p->droit;
	272	free(q);
	273	*verif = 1;
	274	} else {
	275	p->gauche = supmax(p, p->gauche, verif);
	276	if (*verif)
	277	p = equigauche(p, verif);
	278	}
	279	} else if (x < p->cle) {
	280	p->gauche = supprime(p->gauche, x, verif);
	281	if (*verif)
	282	p = equigauche(p, verif);
	283	} else {
	284	p->droit = supprime(p->droit, x, verif);
	285	if (*verif)
	286	p = equidroit(p, verif);
	287	}
	288	return p;
249ff697 JB	289	}
249ff697 JB	290
249ff697 JB	291	/*****************************************************************************/
	292	void affiche_arbre(AVL p, int col)
	293	{
7b0cef36 JB	294	int i;
7b0cef36 JB	295	char esp = ' ';
249ff697	296
7b0cef36 JB	297	if (p) {
	298	affiche_arbre(p->droit, col + 6);
	299	for (i = 0; i < col; i++)
	300	printf("%c", esp);
	301	printf("%6d(%2d)\n", p->cle, p->deseq);
	302	affiche_arbre(p->gauche, col + 6);
	303	};
	304	}
249ff697 JB	305
	306	/*****************************************************************************/
	307	main()
7b0cef36 JB	308	{
	309	AVL rac = NULL;
	310	int x;
	311	int verif;
249ff697	312
7b0cef36 JB	313	do {
	314	printf("Entrez une cle: ");
	315	scanf("%d", &x);
	316	if (x) {
	317	printf("Insertion de la cle %6d\n", x);
	318	verif = 0;
	319	rac = insere(rac, x, &verif);
	320	affiche_arbre(rac, 0);
	321	}
	322	}
	323	while (x);
249ff697	324
7b0cef36 JB	325	do {
	326	printf("Entrez une cle: ");
	327	scanf("%d", &x);
	328	if (x) {
	329	printf("Suppression de la cle %6d\n", x);
	330	verif = 0;
	331	rac = supprime(rac, x, &verif);
	332	affiche_arbre(rac, 0);
	333	}
	334	}
	335	while (x);
	336	}
	337
	338	/*****************************************************************************/