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;
-
+ 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 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 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));
+ a->gauche = RG(a->gauche);
+ return (RD(a));
}
-
/*****************************************************************************/
AVL RDG(AVL a)
{
- a->droit=RD(a->droit);
- return(RG(a));
+ a->droit = RD(a->droit);
+ return (RG(a));
}
-
/*****************************************************************************/
-AVL insere(AVL p,int x,int *verif)
+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;
+ 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;
}
-
- }
- }
- 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);
-}
+ 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)
+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;
- }
+ 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;
+ }
+ return p;
}
-
/*****************************************************************************/
-AVL equidroit(AVL p,int *verif) // quand on entre dans la fonction, verif = 1
+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;
+ 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 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 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 supprime(AVL p, int x, int *verif)
{
- AVL q;
+ 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;
+ 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);
- };
- }
-
+ 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);
+{
+ AVL rac = NULL;
+ int x;
+ int verif;
- 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);
- }
-/*****************************************************************************/
+ 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);
+}
+
+/*****************************************************************************/
repositories / Algorithmic_C.git / commitdiff
