C algorithmique, premier semestre, deuxième année, MMIA 2006--2007

vendredi 13 octobre 2006 : pointeurs et passage d'arguments entiers
vendredi 20 octobre 2006 : pointeurs et tableaux
vendredi 27 octobre 2006 : structure, typedef et pointeurs : généalogie et nombres complexes
vendredi 3 novembre 2006 : liste chaînées
vendredi 10 novembre 2006 : tri fusion de liste chaînées
vendredi 17 novembre 2006 : insertion en fin de liste
vendredi 24 novembre 2006 : listes doublement chaînées
vendredi 1 décembre 2006 : arbres binaires de recherche
vendredi 8 décembre 2006 : suppression dans un arbre binaire de recherche
vendredi 15 décembre 2006 : arbre binaire de recherche équilibré
vendredi 22 décembre 2006 : arbre binaire de recherche équilibré : temps de calcul
vendredi 12 janvier 2007 : autre méthode d'équilibrage
vendredi 19 janvier 2007 :
suivant sommaire

vendredi 13 octobre 2006 : pointeurs et passage d'arguments entiers

cours

#include<stdio.h> int main() { int a,b,c,*p,*q,*r; a=1; b=2; c=3; p=&a; q=&b; r=&c; *p=a+b; *q=a+b; *r=a+b; printf("%d %d %d %d %d %d\n",a,b,c,*p,*q,*r); r=p; p=q; a=*p+*q+*r; b=*p+*q+*r; printf("%d %d %d %d %d %d\n",a,b,c,*p,*q,*r); getchar(); return 0; } Ce programe écrit 3 5 8 3 5 8 13 23 8 23 23 13 #include<stdio.h> void ech1(int a, int b) { a+=b; b=a-b; a-=b; } void ech2(int *a, int *b) { *a+=*b; *b=*a-*b; *a-=*b; } int main() { int a=2, b=3; printf("%d %d\n",a,b); ech1(a,b); printf("%d %d\n",a,b); ech2(&a,&b); printf("%d %d\n",a,b); ech2(&a,&a); printf("%d %d\n",a,b); getchar(); return 0; } Ce programe écrit 2 3 2 3 3 2 0 2

TD

Compléter le programme :#include<stdio.h> int max2(int a, int b); int max3(int a, int b, int c); int max4(int a, int b, int c, int d); void tri2(int *a, int *b); void tri3(int *a, int *b, int *c); void tri4(int *a, int *b, int *c, int *d); void tri5(int *a, int *b, int *c, int *d, int *e); solution :int max2(int a, int b) { if(a<b) return b; else return a; } int max3(int a, int b, int c) { return max2(a,max2(b,c)); } int max4(int a, int b, int c, int d) { return max2(max2(a,b),max2(c,d)); } void ech2(int *a, int *b) { int c=*a; *a=*b; *b=c; } void tri2(int *a, int *b) { if(*a>*b) ech2(a,b); } void tri3(int *a, int *b, int *c) { tri2(a,b); // *b=max(*a,*b) tri2(b,c); // *c=max(*a,*b,*c) tri2(a,b); // *a<*b<*c } void tri4(int *a, int *b, int *c, int *d) { tri2(a,b); tri2(c,d); // *a=min(*a,*b) *c=min(*c,*d) *b=max(*a,*b) *d=max(*c,*d) tri2(a,c); tri2(b,d); // *a=min(*a,*b, *c,*d) *d=max(*a,*b, *c,*d) tri2(b,c); // *a<*b<*c<*d } void ins4(int *a, int *b, int *c, int *d) // en entrée *a<*b<*d en sortie *a<*b<*c<*d { if(*c>*b) tri2(c,d); // avant l'appel de tri2 : *a<*b<min(*c,*d) else ech2(b,c),tri2(a,b); // avant l'appel de tri2 : max(*a,*b)<*c<*d } void tri4bis(int *a, int *b, int *c, int *d) { tri3(a,b,d); // *a<*b<*d ins4(a,b,c,d); // *a<*b<*c<*d } void tri5(int *a, int *b, int *c, int *d, int *e) { tri2(a,b); // *a<*b tri2(c,e); // *c<*e if(*b>*e) ech2(a,c), ech2(b,e); // *a<*b<*e et *c<*e ins4(a,b,d,e); // *a<*b<*d<*e et *c<ancien(*e)<*e ins4(a,b,c,d); // *a<*b<*c<*d<*e } int x; int aleat() { x=5*x+1; return (x/11)&63; } int main() { int a,b,c,d,e; printf("Donnez un nombre : "); scanf("%d",&x); a=aleat(); b=aleat(); c=aleat(); d=aleat(); e=aleat(); printf("%d %d %d %d %d\n",a,b,c,d,e); printf("%d %d %d\n",max2(a,b),max3(c,d,e),max4(a,b,c,d)); tri5(&a,&b,&c,&d,&e); printf("%d %d %d %d %d\n",a,b,c,d,e); return 0; } suivant précédent sommaire

vendredi 20 octobre 2006 : pointeurs et tableaux

#include<stdio.h> void afft(int t[], int n) // Affiche les n premiers éléments du tableau t { int i; for(i=0;i<n;i++) printf("%d ",t[i]); // pour i=0, 1, 2, ..., n-1 on affiche t[i] printf("\n"); // puis on passe à la ligne } void afft2(int *t, int n) // Affiche les n premiers éléments du tableau t { for(;n;n--) printf("%d ",*t++); // pour n=n, n-1, n-2, ... 1 on affiche l'élément pointé par t et on fait pointer t sur le suivant printf("\n"); // puis on passe à la ligne } int dichot(int t[],int n,int x) // rend i tel que t[i]==x ou -1 si on ne trouve pas x. t doit être trié. { int a=0, b=n-1; // on cherche x parmi t[a], t[a+1], ... t[b] donc au début parmi t[0], t[1], ... t[n-1] while(a<b) // tant que l'intervalle de recherche contient plusieurs éléments faire { int m=(a+b)/2; // on coupe [a..b] en deux intervalles de longueurs à peu près égales [a..m] et [m+1..b] if(x>t[m]) a=m+1; // x est dans la partie haute. On remplace [a..b] par [m+1..b] else b=m; // x est dans la partie basse. On remplace [a..b] par [a..m] } // fait if(a==b && x==t[a]) return a; // si l'intervalle t[a..b] est de longueur 1 et qu'il contient x, alors on rend a else return -1; // sinon x n'est pas dans le tableau } int *dichot2(int t[],int n,int x) // rend t+i tel que t[i]==x ou NULL si on ne trouve pas x. t doit être trié. { while(n>1) // tant que l'intervalle de recherche t[0], t[1], ... t[n-1] contient plusieurs éléments faire { int m=n/2; // on coupe [0..n-1] en deux intervalles de longueurs à peu près égales [0..m-1] et [m..n-1] if(x<t[m]) n=m; // x est dans la partie basse. On remplace t[0..n-1] par t[0..m-1] else n-=m, t+=m; // x est dans la partie haute. On remplace t[0..n-1] par t[m..n-1] = (t+m)[0..n-m-1] } // fait if(n==1 && x==*t) return t; // si l'intervalle t[0..n-1] est de longueur 1 et qu'il contient x, alors on rend t else return 0; // sinon x n'est pas dans le tableau } void tribulle(int t[],int n) { while(n) { int i,m=0; for(i=1;i<n;i++) if(t[i]<t[i-1]) { int x=t[m=i]; t[i]=t[i-1]; t[i-1]=x; } n=m; } } int main() { int t[]={4,3,10,7,9,5,1,2,6}, i, n=9; afft(t,n); tribulle(t,n); afft2(t,n); for(i=0;i<12;i++) { int *p=dichot2(t,n,i); printf("%2d %2d %2d\n", i, dichot(t,n,i), p?p-t:-1); } return 0; } Le programme précédent écrit 4 3 10 7 9 5 1 2 6 1 2 3 4 5 6 7 9 10 0 -1 -1 1 0 0 2 1 1 3 2 2 4 3 3 5 4 4 6 5 5 7 6 6 8 -1 -1 9 7 7 10 8 8 11 -1 -1 suivant précédent sommaire

vendredi 27 octobre 2006 : structure, typedef et pointeurs : généalogie et nombres complexes

#include<stdio.h> #include<stdlib.h> struct personne{int age; char nom[40],sexe,prenom[40]; struct personne *pere,*mere;}; void affpersonne(struct personne p) { printf("%s %s est %s de %d ans.\n",p.prenom,p.nom,p.sexe=='M'?"un homme":"une femme",p.age); if(p.pere) printf("Son père est %s %s.\n",p.pere->prenom,p.pere->nom); if(p.mere) printf( "Sa mère est %s %s.\n",p.mere->prenom,p.mere->nom); if(p.pere && p.pere->pere) printf( "Son grand-père paternel est %s %s.\n",p.pere->pere->prenom,p.pere->pere->nom); if(p.pere && p.pere->mere) printf("Sa grand-mère paternelle est %s %s.\n",p.pere->mere->prenom,p.pere->mere->nom); printf("\n"); } int main() { struct personne Alfred ={80,"Martin",'M',"Alfred" ,0,0}, Alphonsine={76,"Duppré",'F',"Alphonsine",0,0}, Jules ={45,"Martin",'M',"Jules" ,&Alfred,&Alphonsine}, Julie ={42,"Dupont",'F',"Julie" ,0,0}, Julien ={18,"Martin",'M',"Julien" ,&Jules,&Julie}, Juliette ={16,"Martin",'F',"Juliette" ,&Jules,&Julie}; affpersonne(Juliette); affpersonne(Julien); affpersonne(Jules); affpersonne(Julie); affpersonne(Alfred); affpersonne(Alphonsine); return 0; } #include<stdio.h> #include<math.h> typedef struct {double re,im;} complexe; void affc(complexe a) {printf("(%0.3lf+%0.3lfi)",a.re,a.im);} complexe lirc() { complexe a; scanf("%lf%lf",&a.re,&a.im); return a; } complexe addc(complexe a,complexe b) { complexe c={a.re+b.re,a.im+b.im}; return c; } complexe subc(complexe a,complexe b) { complexe c={a.re-b.re,a.im-b.im}; return c; } complexe mulc(complexe a,complexe b) { complexe c={a.re*b.re-a.im*b.im,a.re*b.im+a.im*b.re}; return c; } double module2(complexe a) { return a.re*a.re+a.im*a.im; } complexe divc(complexe a,complexe b) { double d=module2(b); // d=b.re²+b.im²=b*conj(b) b.im=-b.im; // b=conj(b) a=mulc(a,b); // a=a*conj(b) a.re/=d; a.im/=d; // a=a*conj(b) / (b*conj(b)) =a/b return a; // a/b } complexe sqrtc(complexe a) { double n=sqrt(module2(a)), x,y; if(!n) x=y=0; else if(a.re>0) x=sqrt((n+a.re)/2), y=a.im/(2*x); else y=sqrt((n-a.re)/2), x=a.im/(2*y); { complexe b={x,y}; return b; } } void eq2c(complexe a,complexe b,complexe c,complexe *z1,complexe *z2) { complexe bp={b.re/-2,b.im/-2}, // b'=-b/2 d=sqrtc(subc(mulc(bp,bp),mulc(a,c))); // d=sqrt(b'²-ac) *z1=divc(addc(bp,d),a); // *z1=(b'+d)/a *z2=divc(subc(bp,d),a); // *z2=(b'-d)/a if(module2(*z1)>module2(*z2)) *z2=divc(c,mulc(*z1,a)); // *z2=(c/a)/*z1 if(module2(*z1)<module2(*z2)) *z1=divc(c,mulc(*z2,a)); // *z1=(c/a)/*z2 } int main() { complexe a={2,3},x1,x2,ma={-a.re,-a.im}; for(x1.re=-1;x1.re<2;x1.re+=2) for(x2.re=-1;x2.re<2;x2.re+=2) for(x1.im=-1;x1.im<2;x1.im+=2) for(x2.im=-1;x2.im<2;x2.im+=2) { complexe z1,z2,b=mulc(ma,addc(x1,x2)), c=mulc(a,mulc(x1,x2)); eq2c(a,b,c,&z1,&z2); affc(a), printf("Z²+"), affc(b), printf("Z+"), affc(c); printf("=0 {"), affc(x1), printf(","), affc(x2); printf("} = {"), affc(z1), printf(","), affc(z2); printf("}\n"); } return 0; } suivant précédent sommaire

vendredi 3 novembre 2006 : listes chaînées

#include<stdio.h> #include<stdlib.h> typedef struct chainon *liste; // Une "liste" est un pointeur sur un charînon. struct chainon{int v; liste suite;}; // Un chaînon contient une valeur entière v et un pointeur sur le chainon suivant, s'il existe. void affrec(liste a) // Pour afficher une liste, { if(a) printf(" %d",a->v), affrec(a->suite); // on affiche le premier chaînon puis le reste de la liste si elle est non vide, else printf("\n"); // sinon on écrit un passage à la ligne. } void affite(liste a) // Pour afficher une liste, { while(a) printf(" %d",a->v), a=a->suite; // on affiche le premier chaînon puis on passe on chaînon suivant et on recommence tant qu'on peut. printf("\n"); // A la fin, on écrit un passage à la ligne. } void aff(liste a) // Pour afficher une liste, { for(;a;a=a->suite) printf(" %d",a->v); // on affiche le premier chaînon puis on passe on chaînon suivant et on recommence tant qu'on peut. printf("\n"); // A la fin, on écrit un passage à la ligne. } void main1() { struct chainon m4={7,0}, // 0 représente la liste vide, &m4 représente la liste (7) m3={1,&m4}, // &m3 représente la liste (1 7) m2={5,&m3}, // &m2 représente la liste (5 1 7) m1={4,&m2}; // &m1 représente la liste (4 5 1 7) affrec(&m1); affite(&m1); aff(&m1); } liste cree(int v, liste suite) // cree(v,suite) est l'adresse d'un nouveau chaînon { liste a=malloc(sizeof(*a)); // situé dans une zone mémoire allouée par malloc a->v=v; // dans laquelle on range v a->suite=suite; // et suite return a; } void main2() { liste l=cree(4,cree(5,cree(1,cree(7,0)))); aff(l); } void main3() { liste l=0; // l=() est la liste vide l=cree(7,l); // on ajoute un nouveau chaînon contenant 7 en tête de l, l=(7) l=cree(1,l); // on ajoute un nouveau chaînon contenant 1 en tête de l, l=(1 7) l=cree(5,l); // on ajoute un nouveau chaînon contenant 5 en tête de l, l=(5 1 7) l=cree(4,l); // on ajoute un nouveau chaînon contenant 4 en tête de l, l=(4 5 1 7) aff(l); } // TD : compléter les cinq procédures suivantes int somme(liste a); // rend la somme des éléments de la liste a liste copie(liste a); // rend une copie avec de nouveaux chaînons de la liste a liste eipoc(liste a); // rend une copie à l'envers avec de nouveaux chaînons de la liste a void libere(liste a); // libère par free la plave occupée par chacun des chaînons de la liste a void add1(liste a); // ajoute 1 à la valeur rangée dans chacun des chaînons de la liste a int somme(liste a) // rend la somme des éléments de la liste a (version itérative) { int s=0; for(;a;a=a->suite) s+=a->v; return s; } int sommerec(liste a) // rend la somme des éléments de la liste a (version récursive) { if(a) return a->v+sommerec(a->suite); // C'est la somme du premier élément et de la somme des suivants si la liste n'est pas vide. else return 0; // La somme des élément d'une liste vide est nulle. } liste copie(liste a) // rend une copie avec de nouveaux chaînons de la liste a { if(a) return cree(a->v,copie(a->suite)); // pointeur sur nouveau chaînon contenant le premier élément de la liste, suivi d'une copie du reste de la liste. else return 0; // La copie d'une liste vide est la liste vide. } liste eipoc(liste a) // rend une copie à l'envers avec de nouveaux chaînons de la liste a { liste l=0; // On parcourt la liste a et on ajoute chacun de ses éléments en tête d'une liste l initialement vide. for(;a;a=a->suite) l=cree(a->v,l); return l; } void libere(liste a) // libère par free la place occupée par chacun des chaînons de la liste a { while(a) { liste b=a; a=a->suite; free(b); } } void add1(liste a) // ajoute 1 à la valeur rangée dans chacun des chaînons de la liste a { for(;a;a=a->suite) a->v++; } liste retourne(liste a) { liste b=0; while(a) // Tant que la liste a n'est pas vide { liste c=a; a=c->suite; // on détache son premier chaînon c c->suite=b; b=c; // et on l'attache en tête de b } return b; } liste copieite(liste a) { return retourne(eipoc(a)); } void main4() { liste l1,l2,l3,l4; l1=cree(5,cree(6,cree(2,0))); l2=copie(l1); add1(l2); l3=eipoc(l2); add1(l3); l4=copieite(l3); add1(l4); printf("%d %d %d %d\n",somme(l1),somme(l2),somme(l3),somme(l4)); aff(l1); libere(l1); aff(l2); libere(l2); aff(l3); libere(l3); aff(l4); libere(l4); } int main() { main1(); // 4 5 1 7 // 4 5 1 7 // 4 5 1 7 main2(); // 4 5 1 7 main3(); // 4 5 1 7 main4(); //13 16 19 22 // 5 6 2 // 6 7 3 // 4 8 7 // 5 9 8 return 0; } suivant précédent sommaire

vendredi 10 novembre 2006 : tri fusion de liste chaînées

void echangeliste(liste *a,liste *b) { liste c=*a; *a=*b; *b=c; } void deplacetete(liste *aa,liste *bb) // si aa=&a et bb=&b alors *aa et *bb sont les variables a et b de type liste. { liste c=*aa; // c pointe sur le chaînon à déplacer, celui qui était en tête de a *aa=c->suite; // a est remplacé par la suite de son premier chaînon. On a donc étété a. c->suite=*bb; // derrière *c on met b *bb=c; // b pointe maintenant sur *c qui est suivi de l'ancienne valeur de b. On a donc ajouté *c en tête de b. } // Notez qu'en fait, on a fait une permutation circulaire des valeurs des 3 variables de type liste : a, c->suite et b liste fusion(liste a,liste b) { if(!a) return b; // cas où a est vide : fusion(0,b)=b if(!b) return a; // cas où b est vide : fusion(a,0)=a if(a->v>b->v) echangeliste(&a,&b); // On échange éventuellement a et b pour que a->v soit plus petit que b->v a->suite=fusion(a->suite,b); // Ex : fusion((2 7 8),(5 6 10))= 2 suivi de fusion((7 8),(5 6 10)). Il est important que 2<5. return a; } liste fusion2(liste a,liste b) { void fusionpp(liste*p, liste b) // *p=fusion(*p,b) { if(!*p) *p=b; else // cas où *p est vide : *p=b car fusion(0,b)=b if(! b) ; else // cas où b est vide : fusion(*p,0)=*p Il n'y a rien à faire. { if((*p)->v>b->v) {liste c=*p; *p=b, b=c;} // On échange éventuellement *p et b pour que (*p)->v soit plus petit que b->v fusionpp(&(*p)->suite,b); // Ex : fusion((2 7 8),(5 6 10))= 2 suivi de fusion((7 8),(5 6 10)). Il est important que 2<5. } } // fin de la procédure fusionpp fusionpp(&a,b); // a=fusion(a,b) return a; } // Dans la procédure récursive fusionpp précédente, on peut remplacer l'appel récursif terminal // fusionpp(&(*p)->suite,b); // par p=&(*p)->suite; suivi d'un retour au début de la procédure. // Le if devient donc un while (ou un for). // On peut aussi sortir le test de la vacuité de b ( if(!b) ) de la boucle, car b peut être vide au début, mais s'il ne l'est pas, // il ne peut pas le devenir. Il est donc inutile de tester la vacuité de b dans la boucle. liste fusion3(liste a,liste b) { liste*p; if(!b) return a; for(p=&a;*p;p=&(*p)->suite) if((*p)->v>b->v) {liste c=*p; *p=b, b=c;} *p=b; return a; } liste trifusion(liste l) { liste l1=0, l2=0; // Au début l1 et l2 sont vides. // Puis on prend les éléments de l un par un, on les enlève de la tête de l et on les met alternativement // en tête de l1 et de l2, en terminant par l1. // Après cela l1 et l2 contiennent chacun à peu près la moitié des éléments de l. Mais l1 en a peut-être un de plus. //while(l) echangeliste(&l1,&l2), deplacetete(&l,&l1); // Cette ligne est équivalente while(l) {liste c=l; l=c->suite, c->suite=l2, l2=l1, l1=c;} // à celle-ci. if(!l2) return l1; // Si l2 est vide, l1 a au plus un élément, elle est triée. return fusion3(trifusion(l1),trifusion(l2)); // On trie les deux moitiés puis on les fusionne. }

TD

Écrire une procédure qui ajoute un élément en fin de liste et une qui enlève un élément en fin de liste. liste ajoutequeue(liste a,int v) { liste q=cree(v,0), p=a; // nouveau chaînon. if(!a) return q; // Si la liste était vide, elle ne contient que le nouveau chaînon. while(p->suite) p=p->suite; // On fait avancer p jusqu'au dernier chaînon. p->suite=q; // On met le nouveau chaînon derrière le dernier chaînon. return a; // Le premier chaînon est toujours le même. } liste ajoutequeue2(liste a,int v) { liste *p=&a; // p pointe d'abord sur la variable de type liste qui contient l'adresse du premier chaînon, while(*p) p=&(*p)->suite; // puis celle qui contient l'adresse du second, etc., jusqu'à ce que *p pointe sur la variable contenant *p=cree(v,0); // le pointeur nul, à remplacer par l'adresse du nouveau chaînon. return a; } liste enlevequeue(liste a) { if(!a) return 0; // Si la liste est vide, on la garde. if(!a->suite) { free(a); return 0; } // Si la liste n'a qu'un seul chaînon, on le détruit et on rend la liste vide. { liste p=a; // La liste a plusieurs chaînons. p part du premier chaînon et while(p->suite->suite) p=p->suite; // avance j'usqu'à l'avant dernier. free(p->suite); // On détruit le dernier chaînon. p->suite=0; // L'avant dernier chaînon n'a plus de successeur. return a; // Le premier chaînon est toujours le même. } } liste enlevequeue2(liste a) { if(!a) return 0; // Si la liste est vide, on la garde. { liste *p=&a; // p pointe d'abord sur la variable de type liste qui contient l'adresse du premier chaînon, while((*p)->suite) p=&(*p)->suite; // puis celle qui contient l'adresse du second, etc., jusqu'à ce que *p pointe sur la variable contenant free(*p); // le pointeur sur le dernier chaînon, que l'on détruit. *p=0; // Puis on remplace son adresse par le pointeur nul. return a; // a est le pointeur sur le premier chaînon ou le pointeur nul si p=&a (la boucle while s'est faite 0 fois) } } void main5() { liste a=0; int j; for(j=0;j<10;j++) a=cree(j*3%10,a); a=ajoutequeue(a,12); a=ajoutequeue2(a,11); aff(a); a=trifusion(a); aff(a); a=enlevequeue(a); a=enlevequeue2(a); aff(a); } int main() { main5(); // 7 4 1 8 5 2 9 6 3 0 12 11 // 0 1 2 3 4 5 6 7 8 9 11 12 // 0 1 2 3 4 5 6 7 8 9 return 0; } suivant précédent sommaire

vendredi 17 novembre 2006 : insertion en fin de liste

Voici cinq versions différentes d'une procédure qui insère un élément à la fin d'une liste chaînée.
Les versions 1, 4 et 5 sont itératives. Les 2 et 3 sont récursives.
Les versions 3 et 4 contiennent une procédure interne à une autre (comme en pascal). Cela ne marche qu'en C gnu et non en C++ gnu.
Les versions 3, 4 et 5 font intervenir des pointeurs sur des listes, qui sont donc des pointeurs sur des pointeurs sur des chaînons. liste inserefin1(liste a,int x) { if(!a) return cree(x,0); // Si la liste était vide, elle contiendra maintenant uniquement le nouveau chaînon. { liste p=a; // p pointe sur le premier chaînon, while(p->suite) p=p->suite; // puis sur le second, puis le troisième, etc.. A la fin p pointe sur le dernier chaînon. p->suite=cree(x,0); // On rajoute un nouveau chaînon derrière le dernier. return a; // Le premier chaînon est toujours le même. } } liste inserefin2(liste a,int x) { if(!a) return cree(x,0); // Si la liste était vide, elle contiendra maintenant uniquement le nouveau chaînon. { a->suite=inserefin2(a->suite,x); // On ajoute un nouveau chaînon à la fin de la liste qui suit le premier chaînon. return a; // Le premier chaînon est toujours le même. } } liste inserefin3(liste a,int x) { void ins(liste *aa) // ins(&b) est équivalent à b=inserefin(b,x) { if(!*aa) *aa=cree(x,0); // On récrit la procédure précédente (inserefin2) en remplaçant a par *aa et return xx; par *aa=xx; else ins(&(*aa)->suite); // Mais on supprime le return a; qui devrait se transformer en *aa=*aa; qui est donc inutile. } ins(&a); // a=inserefin(a,x); return a; } Dans la procédure précédente on remplace l'appel récursif terminal ins(&(*aa)->suite); par a=&(*aa)->suite; suivi d'un retour au début de la procédure. C'est pourquoi le if devient un while. liste inserefin4(liste a,int x) { void ins(liste *aa) // ins(&b) ~ b=inserefin(b,x) { while(*aa) aa=&(*aa)->suite; *aa=cree(x,0); } ins(&a); return a; } liste inserefin5(liste a,int x) // Puisque ins n'est appelée qu'une fois et n'est plus récursive, on peut remplacer l'appel à ins par son corps. { liste *aa=&a; while(*aa) aa=&(*aa)->suite; // Cette boucle est faite zéro fois si la liste est vide. *aa=cree(x,0); // aa vaut &a si la liste est vide et sinon l'adresse du champ suite du dernier chaînon. return a; } typedef struct{liste deb,fin;} liste2; // deb et fin pointent respectivement sur le premier et le dernier chaînon d'une même liste chaînée. void insdeb(liste2 *a,int x) { if(!a->deb) a->deb=a->fin=cree(x,0); // Si la liste était vide, le nouveau chaînon est à la fois le premier et le dernier. else a->deb= cree(x,a->deb);// Sinon seul le premier chaînon change. } void insfin(liste2 *a,int x) { if(!a->deb) a->fin=a->deb =cree(x,0); // Si la liste était vide, le nouveau chaînon est à la fois le premier et le dernier. else a->fin=a->fin->suite=cree(x,0); // Sinon seul le dernier chaînon change. } int otedeb(liste2 *a) { if(!a->deb) printf("non !\n"), exit(1); // C'est une erreur d'essayer d'enlever un chaînon d'une liste vide. On arrête le programme. { liste p=a->deb; // On ne s'occupe pas du dernier chaînon : Il est inchangé ou indéfini si la liste devient vide. int x=p->v; a->deb=p->suite; free(p); return x; } } Les procédures précédentes peuvent être testées avec le programme suivant : void main6() { int j; liste b=cree(4,cree(7,cree(3,0))); liste2 a={0}; aff(b); b=inserefin1(b,51); b=inserefin2(b,52); b=inserefin3(b,53); b=inserefin4(b,54); b=inserefin5(b,55); aff(b); for(j=2;j<10;j+=3) insdeb(&a,j); aff(a.deb); printf("%d\n",otedeb(&a)); insdeb(&a,23); insfin(&a,23); aff(a.deb); a.fin=cree(7,0); a.deb=cree(10,cree(8,a.fin)); aff(a.deb); } qui écrit : 4 7 3 4 7 3 51 52 53 54 55 8 5 2 8 23 5 2 23 10 8 7

TD : listes doublement chaînées (anneaux)

Compléter :typedef struct chainon *anneau; struct chainon {int v; anneau avant, arriere;}; void aff(anneau a); anneau cree(int v); void croise(anneau a,anneau b); Dans une liste doublement chaînée, chaque chaînon contient un pointeur sur le suivant et sur le précédent.
Il est beaucoup plus pratique de faire en sorte que a->avant->arriere et a->arriere->avant soient toujours égaux à a. Donc il n'y a jamais de pointeur nul dans les champs avant ou arriere. Pour cela on fait boucler la liste sur elle-même : après le dernier chaînon, il y a le premier, et avant le premier il y a le dernier. De cette façon il n'y a pas vraiment de bout, on a plutôt des anneaux que des listes.
La procédure d'affichage ne peut pas être récursive, elle est forcément itérative et elle comporte une boucle do...while(...);. En effet, on doit recopier dans une autre variable le pointeur sur le premier chaînon et parcourir la liste jusqu'à ce que l'on revienne à ce premier chaînon. Si on mettait un while le test d'arrêt serait vrai avant de commencer la boucle qui ne se ferait donc pas du tout.
L'appel croise(a,b) échange les successeurs de a et b et donc aussi les prédécessurs de ces successeurs. Si a et b étaient dans deux anneaux différents, ces deux anneaux n'en forment plus qu'un. Réciproquemennt si a et b étaient dans le même anneau, cet anneau est séparé en deux anneaux.
cree(14) fabrique un nouveau chaînon (obtenu par malloc) contenant 14, qui forme un anneau à lui tout seul (il est son propre successeur et son propre prédécesseur.
croise(a,cree(12)) insère un nouveau chaînon contenant 12 juste après a. void aff(anneau a) { anneau b=a; do printf(" %d",a->v), a=a->avant; while(a!=b); printf("\n"); } anneau cree(int v) { anneau a=malloc(sizeof(*a)); a->v=v; return a->avant=a->arriere=a; } void croise(anneau a,anneau b) { anneau c=a->avant, d=b->avant; a->avant=d, d->arriere=a; b->avant=c, c->arriere=b; } suivant précédent sommaire

vendredi 24 novembre 2006 : listes doublement chaînées

#include<stdio.h> #include<stdlib.h> typedef struct chainon *anneau; struct chainon {int v; anneau avant, arriere;}; void aff(anneau a) { anneau b=a; // chaînon de départ do printf(" %d",a->v), // On affiche le contenu d'un chaînon, a=a->avant; // puis on avance au chaînon suivant while(a!=b); // et on recomence jusqu'à ce qu'on soit revenu au point de départ. printf("\n"); // Après tout cela on écrit un passage à la ligne. } anneau cree(int v) // cree(v) rend l'adresse { anneau a=malloc(sizeof(*a)); // d'un nouveau chaînon a->v=v; // contenant le nombre passé en argument. return a->avant=a->arriere=a;// Ce chaînon forme un anneau à lui tout seul : Il est son propre successeur et son propre prédécesseur. } void croise(anneau a,anneau b) // croise(a,b) casse les deux liens qui suivent les chaînons a et b et les reforme en échangeant leur successeurs. { anneau c=a->avant, d=b->avant;// Avant le changement, on a les liens a ---> c et b ---> d a->avant=d, d->arriere=a; // On les remplace par a ---> d b->avant=c, c->arriere=b; // et b ---> c } void croise2(anneau a,anneau b) // Autre version de croise. { anneau x=a->avant; // On échange les valeurs de a->avant a->avant=b->avant; // et b->avant. b->avant=x; a->avant->arriere=a; // a->avant->arriere est maintenant d->arriere qui vaut b. Il faut le remplacer par a. b->avant->arriere=b; // b->avant->arriere est maintenant c->arriere qui vaut a. Il faut le remplacer par b. } int longueur(anneau a) // Nombre de chaînons de l'anneau contenant le chaînon a. { int i=0; // Compteur de chaînons. anneau b=a; // Point de départ do i++, a=a->avant; while(a!=b);// On compte un chaînon de plus et on avance puis on recommence jusqu'à ce qu'on revienne au point de départ. return i; // Nombre de pas en avant à faire pour revenir à son point de départ. } void retourne(anneau a) // Change le sens de parcours d'un anneau. { anneau x,b=a; // Pour cela on échange le successeur et le prédécesseur de chacun des chaînons de l'anneau. do x=a->avant, a->avant=a->arriere, a=a->arriere=x; while(a!=b); } int memeanneau(anneau a,anneau b) // rend vrai (1) si a et b sont deux chaînons d'un même anneau, et sinon faux (0). { anneau d=a; // Point de départ. for(;;) // Tant qu'on ne connaît pas la réponse, on avance. { if(a==b) return 1; // Si on tombe sur b, alors on sait que a et b sont dans le même anneau. a=a->avant; // On avance. if(a==d) return 0; // On est revenu au point de départ : On a fait tout le tour de l'anneau sans trouver b. Donc a et b ne } // sont pas sur le même anneau. } int dist(anneau a,anneau b) // Nombre de pas en avant à faire à partir de a pour atteindre b. -1 si ils ne sont pas sur le même anneau. { anneau d=a; // Point de départ. int i=0; // Nombre de pas en avant déjà faits. for(;;) // Tant qu'on ne connaît pas la réponse, on avance. { if(a==b) return i; // Si on tombe sur b, alors on sait que a et b sont dans le même anneau et on connaît leur distance. a=a->avant; // On avance. i++; // On compte donc un pas de plus. if(a==d) return -1; // On est revenu au point de départ : On a fait tout le tour de l'anneau sans trouver b. Donc a et b ne } // sont pas sur le même anneau. } int dist2(anneau a,anneau b) // Nombre minimal de pas à faire en avant ou en arrière à partir de a pour atteindre b. -1 si ils ne sont pas sur le même anneau. { anneau ar=a; // a va aller en avant tandis que ar va aller en arrière. int i=0; // Nombre de pas en avant ou en arrière déjà faits. for(;;) // Tant qu'on ne connaît pas la réponse, on avance. { if(a==b) return i; // On a trouvé b après i pas en avant. i++; // On compte un oas de plus ar=ar->arriere; // en arrière. if(ar==b) return i; // On a trouvé b après i pas en arrière. if(ar==a) return -1; // En faisant i pas en arrière on arrive au même point qu'en faisant i-1 pas en avant. L'anneau est de longueur 2i-1 et il ne contient pas b. a=a->avant; // On fait aussi un pas en avant. On a donc fait maintenant autant de pas en avant qu'en arrière. if(ar==a) return -1; // En faisant i pas en arrière on arrive au même point qu'en faisant i pas en avant. L'anneau est de longueur 2i et il ne contient pas b. } } void test(anneau a,anneau b) { printf("%d :",longueur(a)), aff(a); printf("%d :",longueur(b)), aff(b); printf("%d min(%d,%d)=%d\n",memeanneau(a,b),dist(a,b),dist(b,a),dist2(a,b)); } int main() { anneau a,b; int i; a=cree(10); for(i=2;i<7;i++) croise(a,cree(i)); test(a,a); b=a->avant->avant; test(a,b); croise(a,b); test(a,b); retourne(a); test(a,b); croise(a,b); test(a,b); return 0; } suivant précédent sommaire

vendredi 1 décembre 2006 : arbres binaires de recherche

Un arbre binaire peut être vide. Il est alors représenté par le pointeur nul. Sinon il est représenté par un pointeur sur un noeud (sa racine) qui contient une valeur (la clé) et deux autres arbres, qui sont ses fils gauche et droit. #include<stdio.h> #include<stdlib.h> typedef struct noeud *arbin; struct noeud{int v; arbin fg,fd;}; arbin cree(arbin fg, int v, arbin fd) { arbin a=malloc(sizeof(*a)); a->v=v; a->fg=fg; a->fd=fd; return a; } arbin feuille(int v) { return cree(0,v,0); } void affpref(arbin a) { if(a) printf(" %d",a->v), affpref(a->fg), affpref(a->fd); } void affpost(arbin a) { if(a) affpost(a->fg), affpost(a->fd), printf(" %d",a->v); } void affinf (arbin a) { if(a) affinf (a->fg), printf(" %d",a->v), affinf (a->fd); } int taille(arbin a) { if(a) return 1+taille(a->fg)+taille(a->fd); else return 0; } int somme(arbin a) { if(a) return a->v+somme(a->fg)+somme(a->fd); else return 0; } int recherche(arbin a,int x) { if(!a) return 0; if(a->v==x) return 1; return recherche(x>a->v?a->fd:a->fg,x); } arbin ajoute(arbin a,int x) { if(!a) return feuille(x); if(x<a->v) a->fg=ajoute(a->fg,x); else if(x>a->v) a->fd=ajoute(a->fd,x); return a; } int main() { arbin a=cree(cree(feuille(1),3,feuille(5)),10, cree(feuille(11),13,feuille(51))); int j; affpref(a); printf("\n"); affpost(a); printf("\n"); affinf (a); printf("\n"); printf("La sommes des %d clés est %d.\n",taille(a),somme(a)); for(j=0;j<20;j++) if(recherche(a,j)) printf(" %d est là. ",j); printf("\n"); for(j=0;j<13;j++) a=ajoute(a,j*5%13); affinf(a); printf("\n"); return 0; } suivant précédent sommaire

vendredi 8 décembre 2006 : suppression dans un arbre binaire de recherche

int rechercheite(arbin a,int x) { while(a && x!=a->v) a= x>a->v ? a->fd : a->fg; return !!a; } void ajouteite(arbin *aa,int x) { while(*aa && x!=(*aa)->v) aa= x>(*aa)->v ? &(*aa)->fd : &(*aa)->fg; if(!*aa) *aa=cree(0,x,0); } arbin enleve(arbin a,int x) { arbin b=a; if(!a) ; else // Si l'arbre est vide, on ne le modifie pas. if(x<a->v) a->fg=enleve(a->fg,x); else // Si x est plus petit que la clé de la racine, on essaye de l'enlever du sous-arbre gauche. if(x>a->v) a->fd=enleve(a->fd,x); else // Si x est plus grand que la clé de la racine, on essaye de l'enlever du sous-arbre droit. if(!a->fd) a=a->fg, free(b); else // Si le noeud à enlever n'a pas de fils droit, on le remplace par son fils gauche. if(!a->fd) a=a->fg, free(b); else // Si le noeud à enlever n'a pas de fils gauche, on le remplace par son fils droit. { for(b=a->fd;b->fg;) b=b->fg; // Le noeud à enlever a deux fils. On va à droite une fois, puis à gauche tant qu'on peut. a->fd=enleve(a->fd,a->v=b->v); // b->v est le plus petit élément du sous-arbre droit. On le copie dans le noeud à enlever, puis } // on l'enlève du sous-arbre droit. return a; } void aff(arbin a,int marge) { if(a) aff(a->fd,marge+3), printf("%*s%d\n",marge,"",a->v), aff(a->fg,marge+3); } void Aff(arbin a) { printf("\n"), aff(a,0);} arbin tourneg(arbin a) /* A B */ { arbin b=a->fd; /* B est l'ancien fils droit de A / \ / \ */ a->fd=b->fg; /* y change de père x B devient A z */ b->fg=a; /* A est le nouveau fils gauche de B / \ / \ */ return b; /* C'est B naintenant qui représente y z x y */ } /* l'arbre complet. */ arbin tourned(arbin a) { arbin b=a->fg; a->fg=b->fd; b->fd=a; return b; } arbin linearise(arbin a) { if(!a) return 0; while(a->fd) a=tourneg(a); a->fg=linearise(a->fg); return a; } int main() { arbin a=cree(cree(feuille(1),3,feuille(5)),10, cree(feuille(11),13,feuille(51))); int j; affpref(a); printf("\n"); affpost(a); printf("\n"); affinf (a); printf("\n"); Aff(a); printf("La somme des %d clés est %d.\n",taille(a),somme(a)); for(j=0;j<20;j++) if(rechercheite(a,j)) printf(" %d est là. ",j); printf("\n"); for(j=0;j<13;j++) ajouteite(&a,j*5%13); Aff(a); for(j=0;j<8;j++) a=enleve(a,j*5%13); Aff(a); a=linearise(a); Aff(a); return 0; } suivant précédent sommaire

vendredi 15 décembre 2006 : arbre binaire de recherche équilibré

Pour regarder si un élément se trouve dans un arbre binaire de recherche, ou pour y ajouter ou en enlever un élément, on parcourt une seule branche de cette arbre. Le temps pris par cette opération est donc proportionnel à la longueur de cette branche. Donc l'insertion d'un élément dans un arbre binaire de recherche, peut prendre dans le pire des cas, un temps proportionnel à la longueur de sa plus grande branche, qu'on appelle aussi la hauteur de l'arbre. Un arbre binaire de recherche contenant n éléments a une hauteur comprise entre n, dans le cas où il ne comporte qu'une seule branche (de longueur n) et log2n dans le cas où toutes les branches ont à peu près la même longueur. Pour que la recherche dans un arbre binaire de recherche soit la plus rapide possible, on a donc intérêt à éviter qu'il y ait des branches trop longues. Pour cela on peut équilibrer l'arbre, c'est-à-dire s'arranger pour que les deux fils de chaque noeud soient de tailles comparables.
Il existe plein de méthodes différentes pour équilibrer un arbre binaire de recherche, comme les AVL, les arbres rouges-noirs, les slpay trees, la méthode du bouc émissaire, etc.. La plupart de ces méthodes définissent les propriétés que doivent vérifier un arbre pour être équilibré, et donnent des algorithmes pour inséser ou supprimer un élément dans un arbre équilibré de tel sorte qu'il reste équilibré.
Toutes ces méthodes utilisent la rotation simple et la rotation double qui sont des réarrangements simples des arbres binaires qui conservent l'ordre infixe des clés, et qui transforment donc un arbre binaire de recherche en un autre arbre binaire de recherche contenant les mêmes clés, mais avec des branches de longueur différentes.

rotation simple

A B / \ ---> / \ x B A z / \ / \ y z x y A et B sont des noeuds, x, y et z sont des arbres qui peuvent contenir chacun 0, 1, 2 ou beaucoup de noeuds. Les deux arbres ont le même feuillage : x A y B z.
Cette transformation est appelée rotation simple à gauche, car l'arête A-B tourne à gauche (dans le sens contraire aux aiguilles d'une montre).
Si le sous-arbre z est beaucoup plus gros que les sous-arbres x et y, alors l'arbre final est plus équilibré que l'arbre initial. Cette transformation doit être appliquée quand le petit fils droit-droit est le plus gros de tous les petits-fils.
En fait cette transformation est intéressante si un petit-fils externe (droit-droit ou gauche-gauche) est plus grand que son frère et son oncle.

rotation double

A A B / \ ---> / \ ---> / \ x C x B A C / \ / \ / \ / \ B t y C x y z t / \ / \ y z z t La rotation double peut se faire en deux rotations simples : une rotation simple à droite autour de B-C suivi d'une rotation simple à gauche autour de A-B. Le petit-fils B devient la racine.
Si le sous-arbre B est beaucoup plus gros que les sous-arbres x et t, alors l'arbre final est plus équilibré que l'arbre initial. Cette transformation doit être appliquée quand le petit fils droit-gauche est le plus gros de tous les petits-fils.
En fait cette transformation est intéressante si un petit-fils interne (droit-gauche ou gauche-droit) est plus grand que son frère et son oncle.

taille

Pour simplifier les calculs, on va définir la taille d'un arbre binaire comme le nombre de sous-arbre vide qu'il contient.
Avec cette définition : Pour équilibrer un arbre, on va comparer les tailles de ses différents sous-arbres. Donc pour éviter de la recalculer, on notera dans chaque noeud la taille de l'arbre ayant ce noeud pour racine.

description sommaire de la procédure d'équilibrage et définition d'un arbre équilibré

Dans la description précédente des rotations simples et doubles, on considèrera qu'un sous-arbre est plus gros qu'un autre si sa taille est plus grande. La procédure pour équilibrer un arbre est donc la suivante :
Tant qu'il existe un noeud qui a une taille plus grande que son frère et que son oncle, on fait une rotation simple ou double selon que ce noeud est un petit-fils externe ou interne.
Un arbre est équilibré quand la procédure précédente ne le modifie pas, autrement dit, quand il ne contient aucun noeud plus gros que son oncle.

procédure d'équilibrage

Pour être sûr de trouver rapidement tous les noeuds plus grands que leur oncle, sans avoir à parcourir tout l'arbre, il vaut mieux utiliser une procédure d'équilibrage qui s'applique seulement à un arbre binaire de recherche dont les deux fils sont déjà des arbres équilibrés. equi(a) On cherche b le plus gros des quatre petits fils de a. Si b est plus gros que son oncle alors : On fait une rotation simple ou double selon que b est un petit fils externe ou interne. On appelle equi récursivement sur chacun des nouveaux sous-arbres qui sont apparus. On appelle equi récursivement sur l'arbe complet sinon Il n'y a rien a faire, l'arbre est déjà équilibré. finsi Cette procédure est écrite en C, dans le programme suivant, avec certaines simplifications : #include<stdio.h> #include<stdlib.h> typedef struct noeud *abr; struct noeud{int v; abr fg,fd;int taille;} f={0,&f,&f,1}; int taille(abr a) {return a ? a->taille : 1 ;} abr cree(abr fg, int v, abr fd) { abr a=malloc(sizeof(*a)); a->v=v; a->taille=taille(a->fg=fg)+taille(a->fd=fd); return a; } abr feuille(int v) { return cree(0,v,0); } void affinf (abr a) { if(a) affinf (a->fg), printf(" %d",a->v), affinf (a->fd); } int somme(abr a) { if(a) return a->v+somme(a->fg)+somme(a->fd); else return 0; } void aff(abr a,int marge) { if(a) aff(a->fd,marge+3), printf("%*s%2d %d\n",marge,"",a->taille,a->v), aff(a->fg,marge+3); } void Aff(abr a) { printf("\n"), aff(a,0);} int recherche(abr a,int x) { while(a && x!=a->v) a= x>a->v ? a->fd : a->fg; return !!a; } abr equi(abr a); abr tourneg(abr a) /* A B */ { abr b=a->fd; /* B est l'ancien fils droit de A / \ / \ */ a->fd=b->fg; /* y change de père x B devient A z */ b->fg=equi(a); /* A est le nouveau fils gauche de B / \ / \ */ return b; /* C'est B naintenant qui représente y z x y */ } /* l'arbre complet. */ abr tourned(abr a) { abr b=a->fg; a->fg=b->fd; b->fd=equi(a); return b; } int maxi(int a,int b) {return a>b ? a : b;} int mt(abr a) { return maxi(taille(a->fd),taille(a->fg));} // taille du plus gros fils int dt(abr a) { return taille(a->fd)-taille(a->fg) ;} // différence entre les tailles des fils abr equi(abr a) { if(dt(a)>0 && mt(a->fd)>taille(a->fg)) { if(dt(a->fd)<0) a->fd=tourned(a->fd); a=tourneg(a); } else if(dt(a)<0 && mt(a->fg)>taille(a->fd)) { if(dt(a->fg)>0) a->fg=tourneg(a->fg); a=tourned(a); } a->taille=taille(a->fg)+taille(a->fd); return a; } abr ajoute(abr a,int x) { if(!a) return feuille(x); if(x<a->v) a->fg=ajoute(a->fg,x); else if(x>a->v) a->fd=ajoute(a->fd,x); return equi(a); } int minv(abr a) // élément le plus à gauche de l'arbre (donc le plus petit, si c'est un arbre de recherche) { while(a->fg) a=a->fg; return a->v; } abr enleve(abr a,int x) { if(!a) return a; // Si l'arbre est vide, on ne le modifie pas. if(x==a->v && !a->fd) {abr b=a->fg; free(a); return b;} // Si l'élément à enlever n'a pas de fils doit, on ne garde que son fils gauche. if(x==a->v) a->v =x=minv(a->fd); // On remplace l'élément à enlever par le plus petit élément de son fils droit qui va être enlevé. if(x>=a->v) a->fd=enleve(a->fd,x);// Si x est plus grand que la clé de la racine, on essaye de l'enlever du sous-arbre droit. else a->fg=enleve(a->fg,x);// Si x est plus petit que la clé de la racine, on essaye de l'enlever du sous-arbre gauche. return equi(a); } void verif(abr a) { abr x=0; void ver(abr a) { if(!a) return; ver(a->fg); if(a->fd && mt(a->fd)>taille(a->fg) ) printf("neveu plus gros que son oncle %d>%d\n",mt(a->fd) ,taille(a->fg)),exit(1); if(a->fg && mt(a->fg)>taille(a->fd) ) printf("neveu plus gros que son oncle %d>%d\n",mt(a->fg) ,taille(a->fd)),exit(1); if(a->taille!=taille(a->fg)+taille(a->fd)) printf("taille fausse %d!=%d+%d\n",a->taille,taille(a->fg),taille(a->fd)),exit(1); if(x && x->v>=a->v ) printf("clés non croissantes %d>=%d\n",x->v ,a->v ),exit(1); x=a; ver(a->fd); } ver(a); } // // TD du 15 décembre // int maxv(abr a) // élément le plus à droite de l'arbre (donc le plus grand, si c'est un arbre de recherche) { while(a->fd) a=a->fd; return a->v; } int kieme(abr a,int k) { if(!a) printf("erreur kieme k=%d\n",k), exit(1); if(k>taille(a->fg)) return kieme(a->fd,k-taille(a->fg)); if(k<taille(a->fg)) return kieme(a->fg,k); return a->v; } int mediane(abr a) {return kieme(a,(1+taille(a))/2);} // // TD du 22 décembre // void libere(abr a) { if(a) libere(a->fg), libere(a->fd), free(a); } void tri(int t[], int n) { void relit(abr a) { if(a) relit(a->fg), t[n++]=a->v, relit(a->fd); } abr a=0; while(n) a=ajoute(a,t[--n]); relit(a); libere(a); } void afft(int *t,int n) { for(;n;n--) printf(" %d",*t++); printf("\n"); } // // TD du 15 décembre // int main() { abr a=0; int i,x=0,t[10]; for(i=0;i<20;i++) a=ajoute(a,i), Aff(a), verif(a); for(i=0;i<20;i++) a=enleve(a,i), Aff(a), verif(a); for(i=x=0;i<=8000;i++) a=ajoute(a,x), x=5*x+1, verif(a); verif(a); printf("%d %d %d\n",minv(a),mediane(a),maxv(a)); for(i=x=0;i<=8000;i++) a=enleve(a,x), x=5*x+1, verif(a); // // TD du 22 décembre // for(i=0;i<10;i++) t[i]=i*3%10; afft(t,10); tri (t,10); afft(t,10); return 0; }

TD : plus petit élément, plus grand et médian

Compléter les quatre fonctions suivantes : int minv(abr a); // élément le plus à gauche de l'arbre (donc le plus petit, si c'est un arbre de recherche) int maxv(abr a); // élément le plus à droite de l'arbre (donc le plus grand, si c'est un arbre de recherche) int kieme(abr a,int k); // rend le k-ième de l'arbre a, les éléments étant pris dans l'ordre infixe à partir de la gauche (donc dans l'ordre croissant) int mediane(abr a); // =kieme(a,6) si a est de taille 12, par exemple. suivant précédent sommaire

vendredi 22 décembre 2006 : arbre binaire de recherche équilibré : temps de calcul

déséquilibre d'un arbre

On appellera déséquilibre d'un arbre la somme des tailles de tous ses noeuds.
C'est aussi la somme des longueurs de toutes les branches de l'arbre, qui vont de la racine à un sous-arbre vide (considéré comme une feuille).
Par exemple dans l'arbre 5 / \ 3 7 / \ \ 1 4 8 on peut noter sous chaque noeud sa taille, et dessiner et nommer les feuilles : 5 / 7 \ 3 7 / 4 \ /3\ 1 4 e 8 /2\ /2\ /2\ a b c d f g Les noeuds 1, 3, 4, 5, 7 et 8 ont pour taille 2, 4, 2, 7, 3 et 2. La somme de ces tailles est 20. Les sept branches et leur longueurs sont :
5->3->1->a3
5->3->1->b3
5->3->4->c3
5->3->4->d3
5->7->e 2
5->7->4->f3
5->7->4->g3
La somme des longueurs des branches est 20.
Le déséquilibre de cet arbre vaut donc 20.

utilité du déséquilibre

Si on insère un nouvel élément dans un arbre binaire de recherche à une place aléatoire, toutes les places étant équiprobables, alors l'espérance de la longueur du chemin allant de la racine à ce nouvel élément (et donc du temps pris par la procédure d'insertion) est égale au déséquilibre de l'arbre divisé par sa taille. On a donc intérêt à avoir des arbres dont le déséquilibre est le plus petit possible.
Le déséquilibre d'un arbre de taille n est maximal quand tous ses noeuds sont sur une seule branche. On dit alors que l'arbre est linéaire. Ses noeud ont pour taille n, n-1, n-2, ..., 4, 3 et 2. Le déséquilibre de l'arbre est donc n(n+1)/2-1.
Le déséquilibre d'un arbre de taille n est minimal quand toutes ses branches ont à peu près la même longueur. Par exemple un arbre de taille 16, aurait deux fils de taille 8, quatre petits fils de taille 4 et huit arrière petits fils de taille 2. Son déséquilibre serait 16+2x8+4x4+8x2=4x16=64 (=16 log2 16). Quand n est une puissance de 2, on peut équilibrer parfaitement l'arbre, de sorte que toutes ses branches ont pour longueur log2 n et son déséquilibre est n log2 n.
Si 2k<n<2k+1 alors l'arbre le plus équilibré possible n'a que des branches de longueur k et k+1. Soient a le nombre de branches de longueur k et b le nombre de branches de longueur k+1. Puisque a+b=n et que a+b/2=2k, on obtient que a=2k+1-n et b=2n-2k+1. Donc le déséquilibre de l'arbre est ak+b(k+1)=(a+b)k+b=nk+b=n(k+2)-2k+1=n(log2 n+O(1)).
Nous allons étudier les variations du déséquilibre, lors des différentes opérations faites sur un abre binaire de recherche.

hauteur d'un arbre équilibré et temps d'une recherche

Soient t0=1 < t1 < t2 < t3 < ... < tk=n les tailles des sous-arbres rencontrés le long d'une branche de longueur k allant d'une feuille (de taille 1) jusqu'à la racine (de taille n).
Le sous-arbre de taille ti a un père de taille ti+1 et un grand père de taille ti+2. Donc son oncle a pour taille ti+2-ti+1. Puisque l'arbre est équilibré il est moins gros que son oncle : ti≤ti+2-ti+1. Donc
ti+2≥ti+ti+1.
La suite ti croît plus vite qu'une suite de Fibonacci. Plus précisément si on définit F0=0, F1=1 et Fi=Fi-1+Fi-2 pour i>1. De t0=1=F2, t1≥2=F3 et ti+2≥ti+ti+1 on peut déduire que ti≥Fi+2 et donc n≥Fk+2=(φk+2-φ'k+2)/√5 en notant φ=(1+√5)/2 le nombre d'or et φ'=(1-√5)/2 son conjugué.
Donc k≤3+logφ n.
Cette égalité est valable pour toute branche et en particulier pour la plus longue. Cela montre que la hauteur d'un arbre équilibré de taille n (qui est la longueur de sa plus longue branche) est inférieure à 3+logφ n.
Puisque la recherche dans arbre binaire de recherche, prend un temps proportionnel à la longueur de la branche allant de la racine à l'élément cherché, cela montre que la recherche dans un arbre équilibré de taille n, prend un temps en O(ln n).

insertion et déséquilibre

Lors de l'insertion d'un élément dans un arbre binaire de recherche (non nécessairement équilibré et sans faire de rééquilibrage) un nouveau noeud sans fils, donc de taille 2, est créé. La taille de chacun des anciens noeuds se trouvant sur la branche allant de la racine à ce nouveau noeud augmente d'un. La taille de tous les autres noeuds est inchangée. Le déséquilibre de l'arbre complet augmente donc de 2 plus la longueur de la branche allant au nouveau noeud. Si avant l'insertion l'arbre était équilibré et de taille n, alors le déséquilibre augmente au plus de 5+logφ n.

suppression et déséquilibre

Lors de la suppression d'un élément d'un arbre binaire de recherche, le déséquilibre diminue.

rotation simple et déséquilibre

A B /x+y+z\ ---> /x+y+z\ * B A * x /y+z\ /x+y\ z * * * * y z x y Le déséquilibre passe de
D(X)+x+y+z+D(Y)+y+z+D(Z) à
D(X)+x+y+D(Y)+x+y+z+D(Z)
Il diminue donc de z-x qui est bien strictement positif si z>x.

rotation double et déséquilibre

A B /x+y+z+t\ ---> /x+y+z+t\ * C A C x /y+z+t\ /x+y\ /z+t\ B * * * * * /y+z\ t x y z t * * y z Le déséquilibre passe de
D(X)+x+y+z+t+D(Y)+y+z+D(Z)+y+z+t+D(T) à
D(X)+x+y+D(Y)+x+y+z+t+D(Z)+z+t+D(T)
Il diminue donc de y+z-x qui est bien strictement positif si y+z>x.

temps de calcul

Supposons que l'on parte d'un arbre vide, et que l'on fasse une suite de recherche, d'insertions et de suppressions avec rééquilibrage. Soient n la taille maximale de l'arbre, ni le nombre d'insertions, ns le nombre de suppressions et nr le nombre total de rotations (simples ou doubles) faites lors de tous les rééquilibrages suivant les insertions et les suppressions. En remarquant que : On en déduit que nr≤ni(5+logφ n).
En moyenne donc chaque insertion ou suppression prend un temps en O(ln n).

optimisation : choix du plus gros petit fils

Lorsque deux frères de tailles w et t sont tous les deux plus gros que leur oncle de taille x, une des rotations gagnera w-x sur le déséquilibre et l'autre gagnera t-x. On gagnera plus si on fait monter le plus gros frère. C'est pourquoi on impose qu'un noeud doit être plus gros que son oncle et que son frère pour faire une rotation. Mais cela ne changerait pas grand chose si on oubliait la contrainte que le noeud doit être plus gros que son frère : Dans l'exemple suivant on suppose que y+z>t>x. A C B / \ ---> / \ ---> / \ * C A * A C x / \ / \ t / \ / \ B * * B * * * * / \ t x / \ x y z t * * * * y z y z Si on fait d'abord une rotation simple à gauche qui gagne t-x, on sera sûrement amené ensuite à faire une rotation double qui gagnera y+z-t. Le résultat final sera le même que si on avait tout de suite décidé de faire une rotation double qui gagne y+z-x.
Imposer que le noeud qui monte soit plus gros que son frère accélère donc les choses en évitant de faire plusieurs rotations consécutives sur le même noeud.
Dans l'arbre * /x+y+z+t\ * * /x+y\ /z+t\ * * * * x y z t si y>z+t alors x+y>z+t et donc z et t sont plus petits que x+y. Donc parmi les quatre petits fils d'un noeud donné, il y en a au plus un qui est plus gros que son frère et que son oncle. S'il existe, c'est à la fois le plus gros des quatre petits fils et le plus gros fils du plus gros fils.

comparaison des tailles d'un noeud et de ses fils dans un arbre équilibré

Dans un arbre équilibré la taille de chacun des deux fils d'un noeud n'excède pas la taille de son frère. On en déduit donc que la taille d'un noeud n'excéde pas le double de la taille de son frère. Et donc la taille d'un noeud n'excède pas le triple de la taille de chacun de ses fils.
Avec un schéma cela donne : * /x+y\ * * / x \ y * * s t Si cet arbre est équilibré, alors s≤y et t≤y donc x=s+t≤2y et donc x+y≤3y. De même y≤2x et x+y≤3x.

taille du plus gros fils et arbre presque équilibré

On dira qu'un arbre est presque équilibré si ses deux fils sont équilibrés et que la taille de son plus gros fils n'excède pas le triple de la taille de l'autre fils.
On peut montrer par récurence que quand on applique la procédure de rééquilibrage à un arbre presque équilibré, alors :
  1. Tous les appels récursifs de cette procédure se font sur des arbres presque équilibrés.
  2. Le rééquilibrage d'un arbre n'augmente jamais la taille de son plus gros fils.
  3. Après une rotation, il est inutile de rééquilibrer l'arbre complet.

démonstration dans le cas de la rotation simple

A B B /x+y+z\ ---> /x+y+z\ ---> /x+y+z\ * B A * A' * x /y+z\ /x+y\ z /x+y\ z * * * * * * y z x y x' y' Hypothèses : Conclusions :

démonstration dans le cas de la rotation double

A B B /x+y+z+t\ ---> /x+y+z+t\ ---> /x+y+z+t\ * C A C A' C' x /y+z+t\ /x+y\ /z+t\ /x+y\ /z+t\ B * * * * * * * * * /y+z\ t x y z t x' y' z' t' * * y z Hypothèses : Conclusions :

insertion ou suppression d'un élément dans un arbre équilibré

La procédure qui insère ou supprime un élément dans un arbre équilibré commence en général par l'insérer ou le supprimer, par un appel récursif, dans un des fils, qui reste donc équilibré. Après cela il n'y plus qu'à rééquilibrer éventuellement l'arbre complet.
Soient x et y les tailles des deux fils avant l'insertion ou la suppression et x' et y les nouvelles tailles. On a x≤2y , y≤2x , |x-x'|=1 , x>0 , y>0 et x'>0. On peut en déduire que x'≤3y et y≤3x' et donc l'arbre à rééquilibrer est presque équilibré, sauf si x=2, y=4 et x'=1.
Il n'existe qu'une seule forme d'arbre équilibré de taille 4. On peut donc regarder l'effet dune rotation simple ou double sur un arbre dont les deux fils sont équilibrés et de taille 1 et 4 : A C B / 5 \ ---> / 5 \ ou / 5 \ * C A D A C 1 / 4 \ / 3 \ / 2 \ / 2 \ / 3 \ B D * B * * * * * D / 2 \ / 2 \ 1 /2\ 1 1 1 1 1 /2\ * * * * * * * * 1 1 1 1 1 1 1 1 La rotation simple et la rotation double donnent des arbres équilibrés.
On peut donc définir un arbre quasi-équilibré comme un arbre presque équilibré ou un arbre de taille 5 dont les deux fils sont équilibrés et de taille 1 et 4.
Alors lors d'une insertion ou d'une suppression dans un arbre équilibré tous les arbres passés à la procédure de rééquilibrage sont quasi-équilibrés et il est inutile de rappeler la procédure de rééquilibrage sur l'arbre complet après une rotation simple ou double. Au lieu de abr equi(abr a) { if(dt(a)>0 && mt(a->fd)>taille(a->fg)) { if(dt(a->fd)<0) a->fd=tourned(a->fd); a=equi(tourneg(a)); } else if(dt(a)<0 && mt(a->fg)>taille(a->fd)) { if(dt(a->fg)>0) a->fg=tourneg(a->fg); a=equi(tourned(a)); } a->taille=taille(a->fg)+taille(a->fd); return a; } on peut écrire abr equi(abr a) { if(dt(a)>0 && mt(a->fd)>taille(a->fg)) { if(dt(a->fd)<0) a->fd=tourned(a->fd); a=tourneg(a); } else if(dt(a)<0 && mt(a->fg)>taille(a->fd)) { if(dt(a->fg)>0) a->fg=tourneg(a->fg); a=tourned(a); } a->taille=taille(a->fg)+taille(a->fd); return a; }

arbres équilibrés : variante 1

Soit p∈{0,1,2}. On peut affaiblir la définition d'un arbre équilibré en demandant simplement que la taille d'un noeud doit être au plus égale à la taille de son oncle augmentée de p.
Avec cette définition, tous les algorithmes, résultats et démonstrations vus précédemment marchent encore avec les modifications suivantes : Ces modifications augmentent donc de p, la hauteur des arbres, mais divise par p+1 le majorant du nombre de rotations faites.

TD : tri d'un tableau en utilisant un arbre binaire de recherche

Compléter la procédure void tri(int t[], int n); qui permute les n éléments du tableau t en les mettant dans l'ordre croissant. suivant précédent sommaire

vendredi 12 janvier 2007 : autre méthode d'équilibrage

arbres équilibrés : variante 2

On peut changer la définition d'un arbre équilibré en demandant simplement que la taille d'un noeud soit au plus égale à la taille de son oncle multipliée par un paramètre k réel fixé supérieur à 2.
On doit alors définir le déséquilibre comme la somme des logarithmes des tailles des noeuds.
On peut alors démontrer que le déséquilibre augmente d'une quantité bornée lors d'une insertion, et diminue d'une quantité minorée par un nombre strictement positif lors de toute rotation. On peut donc en déduire que le nombre total de rotations effectuées lors d'une suite d'insertions et de suppressions appliquées à un arbre initialement vide est en O du nombre d'insertions.

hauteur d'un arbre équilibré et temps d'une recherche

Soient t0=1 < t1 < t2 < t3 < ... < tk=n les tailles des sous-arbres rencontrés le long d'une branche de longueur k allant d'une feuille (de taille 1) jusqu'à la racine (de taille n).
Le sous-arbre de taille ti a un père de taille ti+1 et un grand père de taille ti+2. Donc son oncle a pour taille ti+2-ti+1. Puisque l'arbre est équilibré il est moins gros que k fois son oncle : ti≤k(ti+2-ti+1). Donc
ti+2≥ti+1+ti/k.
La suite ti croît plus vite que la suite récurente définie par G0=1, G1=2 et Gi=Gi-1+Gi-2/k pour i>1. De t0=1=G0, t1≥2=G1 et ti+2≥ti+1+ti/k on peut déduire que ti≥Gi et donc n≥Gk∼cλk où λ=(1+√(1+4/k))/2 est la plus grande racine de l'équation λ2=λ+1/k
Donc k≤c'+logλ n.
Cette égalité est valable pour toute branche et en particulier pour la plus longue. Cela montre que la hauteur d'un arbre équilibré de taille n (qui est la longueur de sa plus longue branche) est inférieure à c'+logλ n.
Puisque la recherche dans arbre binaire de recherche, prend un temps proportionnel à la longueur de la branche allant de la racine à l'élément cherché, cela montre que la recherche dans un arbre équilibré de taille n, prend un temps en O(ln n).

insertion et déséquilibre

Lors de l'insertion d'un élément dans un arbre binaire de recherche équilibré sans faire de rééquilibrage, un nouveau noeud sans fils, donc de taille 2, est créé. La taille de chacun des anciens noeuds se trouvant sur la branche allant de la racine à ce nouveau noeud augmente d'un. La taille de tous les autres noeuds est inchangée. Le déséquilibre de l'arbre complet augmente donc de
δD=ln 2+ln(t0+1)/t0 +ln(t1+1)/t1 +ln(t2+1)/t2 +ln(t3+1)/t3 +... +ln(tk+1)/tk =ln 2+∑0≤i≤kln(1+1/ti) <ln 2+∑0≤i1/ti ≤M=ln 2+∑0≤i1/Gi Cette série converge bien puisque Gi est équivalent à une série géométrique de raison λ>1.

suppression et déséquilibre

Lors de la suppression d'un élément d'un arbre binaire de recherche, le déséquilibre diminue.

comparaison des tailles d'un noeud et de ses fils dans un arbre équilibré

* /x+y\ * * / x \ y * * s t Si cet arbre est équilibré, alors s≤ky et t≤ky donc x=s+t≤2ky et donc x+y≤(2k+1)y. De même y≤2kx et x+y≤(2k+1)x.

taille du plus gros fils et arbre presque équilibré

On dira qu'un arbre est presque équilibré si ses deux fils sont équilibrés et que la taille de son plus gros fils n'excède pas la taille de l'autre fils multipliée par 2k+1.
On peut montrer par récurence que quand on applique la procédure de rééquilibrage à un arbre presque équilibré, alors :
  1. Tous les appels récursifs de cette procédure se font sur des arbres presque équilibrés.
  2. Le rééquilibrage d'un arbre n'augmente jamais la taille de son plus gros fils.

rotation simple et déséquilibre

A B /x+y+z\ ---> /x+y+z\ * B A * x /y+z\ /x+y\ z * * * * y z x y Le déséquilibre passe de
D(X)+ln(x+y+z)+D(Y)+ln(y+z)+D(Z) à
D(X)+ln(x+y)+D(Y)+ln(x+y+z)+D(Z)
Il diminue donc de -δD=ln (y+z)/(x+y) = ≥ ln 2z/(z+x) ≥ ln 2k/(k+1)
car (y+z)/(x+y) est une fonction décroissante de y qui est donc minimale quand y est maximale c'est-à-dire quand y=z.
De même z/(z+x) est une fonction décroissante de z/x qui est donc minimale quand z/x est maximal c'est-à-dire quand z=kx.

rotation double et déséquilibre

A B /x+y+z+t\ ---> /x+y+z+t\ * C A C x /y+z+t\ /x+y\ /z+t\ B * * * * * /y+z\ t x y z t * * y z Le déséquilibre passe de
D(X)+ln(x+y+z+t)+D(Y)+ln(y+z)+D(Z)+ln(y+z+t)+D(T) à
D(X)+ln(x+y)+D(Y)+ln(x+y+z+t)+D(Z)+ln(z+t)+D(T)
Il diminue de -δD=ln (y+z)(y+z+t)/(x+y)(z+t) Il faut donc chercher le minimum m de (y+z)(y+z+t)/(x+y)(z+t) sous les contraintes : Pour x et y fixés, 1/(x+y) est minimal quand x est maximal c'est-à-dire x=(y+z)/k de même que (y+z+t)/(z+t)=1+y/(z+t) est minimal quand t est maximal c'est-à-dire quand t=y+z.
Donc m est le minimum de 2(y+z)2/((y+z)/k+y)(y+2z) sous les contraintes : y>0 et z>0
Pour y+z fixé, la somme des deux facteurs du dénominateur (y+z)(2+1/k) est constante. Ce produit est donc maximal quand ces deux facteurs sont égaux. Donc m=2/(1+1/2k)2
Cela montre que lors d'une rotation double, le déséquilibre augmente d'au moins ln m=ln 2/(1+1/2k)2
Ce minorant est une fonction croissante positive de k qui pour k=2 vaut ln 32/25 et qui tend vers ln 2 quand k tend vers l'infini.
On peut remarquer que pour k=1 m=8/9 et donc ln m<0. On ne peut donc pas démontrer dans ce cas que le nombre moyen de rotations effectuées à chaque insertion ou suppression est borné.

nombre de rotations

Supposons que l'on parte d'un arbre vide, et que l'on fasse une suite de recherche, d'insertions et de suppressions avec rééquilibrage. Soient n la taille maximale de l'arbre, ni le nombre d'insertions, ns le nombre de suppressions et nr le nombre total de rotations (simples ou doubles) faites lors de tous les rééquilibrages suivant les insertions et les suppressions. En remarquant que : On en déduit que nr≤ni M/ln m.
Le nombre moyen de rotations effectuées lors d'une insertion est donc inférieur à M/ln m.

TD

Modifier le programme pour qu'il compte les rotations effectuées lors de l'insertion de 20000 éléments dans un arbre initialement vide, pour des valeurs de k valant 1, 1.1, 1.2, 1.3, ... 2.8, 2.9, 3
précédent sommaire

vendredi 19 janvier 2007 :