#include #include /* Un arbre binaire est défini récursivement comme - ou bien une feuille, appelée aussi arbre vide, - ou bien un noeud, appelé racine de l'arbre, qui contient une clé et deux (sous-)arbres, appelés fils droit et fils gauche. Les noeuds d'un arbres sont les racines de ses sous-arbres. En C en fait un arbre sera un pointeur sur un noeud, et l'arbre vide sera représenté par une valeur spéciale de pointeur, comme le pointeur nul. */ typedef int elem; typedef struct noeud noeud, *abr; struct noeud { elem clef; abr fg,fd; } vide[1]={{0,vide,vide}}; /* La taille d'un arbre binaire est le nombre de ses feuilles. C'est donc un de plus que le nombre de ses noeuds. La taille est toujours un entier naturel strictement positif. La taille d'un arbre représenté par un noeud est la somme des tailles de ses deux fils. La hauteur d'un arbre binaire est la longueur de sa plus longue branche. On peut calculer la taille et la hauteur avec les fonctions suivantes : */ int taille(abr a) { return a==vide ? 1 : taille(a->fg)+taille(a->fd) ; } int maxi(int a,int b) { return a>b?a:b;} int hauteur(abr a) { return a==vide ? 0 : 1+maxi(hauteur(a->fg),hauteur(a->fd)) ; } /* Un arbre binaire est dit «de recherche» si la clé d'un noeud quelconque est toujours strictement plus grande que toutes les clés de son sous-arbre gauche et strictement plus petite que toutes les clés de son sous-arbre droit. Autrement dit, les clés de l'arbre doivent être affichées dans l'ordre croissant par la procédure récursive suivante : */ #define recursif 1 #if recursif void aff(abr a) { if(a!=vide) aff(a->fg), printf(" %d",a->clef), aff(a->fd); } /* Dans cette procédure, on peut remplacer le dernier appel récursif par une itération : */ #else void aff(abr a) { for(;a!=vide;a=a->fd) aff(a->fg), printf(" %d",a->clef); } #endif void affln(abr a) {aff(a),printf("\n");} /* recherche du noeud contenant une clé donnée */ #if recursif abr recherche(abr a,elem x) { vide->clef=x; return x==a->clef ? a : // Si x est dans un noeud, on rend son adresse. x> a->clef ? recherche(a->fd,x) : // On cherche x à droite ou à gauche recherche(a->fg,x) ; // selon qu'il est plus grand ou plus petit } // que la clé de la racine. #else abr recherche(abr a,elem x) { vide->clef=x; while(x!=a->clef) a=x>a->clef ? a->fd : a->fg; return a; } #endif int ta=1; // ta contient la taille de l'arbre abr nn(abr fg,elem clef,abr fd) // nouveau noeud { abr a=malloc(sizeof(*a)); // a est l'adresse d'un nouveau noeud *a=(noeud){clef,fg,fd}; // dans lequel on range les 3 arguments de la fonction. ++ta; // La taille l'arbre augmente. return a; // On rend l'adresse de ce nouveau noeud. } abr n2(elem x) { return nn(vide,x,vide); }// Nouvel arbre de taille 2 abr copie(abr a) // Crée un nouvel arbre de même forme, avec les mêmes clés { return a==vide ? a : nn(copie(a->fg),a->clef,copie(a->fd)) ; } abr eipoc(abr a) // crée un arbre contenant des clés de signe opposé { return a==vide ? a : nn(eipoc(a->fd),-a->clef,eipoc(a->fg)) ; } void test(abr b,abr a) // vérifie que b->clef < a->clef si b est non nul { if(b!=vide && b->clef>=a->clef) printf("raté %d<%d\n",b->clef,a->clef), exit(1); } void verif(abr a) { abr b=vide; // dernier noeud visité. void ver(abr a) // procédure récursive de parcours infixe de l'arbre. { for(;a!=vide;a=a->fd) test(a->fg,a), // Cette ligne arrête le programme quand par exemple a->fg->fg==a ver(a->fg), test(b,a), b=a;// On vérifie que les clés sont dans l'ordre croissant. } ver(a); // Unique instruction de verif. } void affarbre(abr r) // affichage sous forme d'arbre couché vers la gauche { void af(abr a) // procédure récursive qui affiche le sous-arbre a de l'arbre r { for(;a!=vide;a=a->fg) { int dd,d=2; abr p=a->fg; a->fg=vide, af(a->fd), a->fg=p; // pendant l'appel récursif à droite, on ôte le fils gauche for(p=r;p!=a;p=d?p->fd:p->fg) dd=d,d=p->fg==vide,printf(dd-!d?" ":"| "); printf("%c--+ %d\n","\\/-"[d],a->clef); } } af(r); // unique instruction de affarbre } void Aff (abr a) { affln(a), affarbre(a), verif(a); } void libere(abr a) { if(a!=vide) libere(a->fg), libere(a->fd), free(a), --ta; } abr rotg (abr a) { abr b=a->fd; a->fd=b->fg, b->fg=a; return b; } abr rotd (abr a) { abr b=a->fg; a->fg=b->fd, b->fd=a; return b; } #if recursif abr linearise(abr a) // rend un arbre linéaire, c'est-à-dire, avec une seule branche { if(a==vide) return a; // Si l'arbre est vide, il n'y a rien à faire. while(a->fd!=vide) a=rotg(a);// Tant qu'il y a un fils droit, on fait des rotations à gauche. a->fg=linearise(a->fg); // Puis on linéarise le fils gauche. return a; } #else abr linearise(abr a) { abr *b; for(b=&a;*b!=vide;b=&(*b)->fg) while((*b)->fd!=vide) *b=rotg(*b); return a; } #endif /* Pour rééquilibrer un arbre de taille n, on fait d'abord une liste chaînée de ses n feuilles. Puis on fusionne deux par deux ces arbres de taille 1 pour obtenir une liste d'arbres de taille 2, (sauf peut-être le dernier de la liste qui sera de taille 1 si n est impair). Puis on fusionne ces arbres deux par deux pour obtenir une liste d'arbres équilibrés de taille 4, etc.. On s'arrête quand la liste ne contient plus qu'un arbre équilibré de taille n. La liste chaînée est obtenue en chaînant les noeuds selon le fils gauche. Les arbres équilibrés sont rangés dans les fils droits des maillons. Donc la liste d'arbres vides initiale s'obtient en linéarisant l'arbre initial. L'unique maillon de la liste finale doit être retiré. On ne garde que son fils droit qui est l'arbre final. Il faut donc au début rajouter un noeud dont la clé est virtuellement plus petite que toutes les clés de l'arbre initial. C'est pourquoi avant la linéarisation, on ajoute un noeud z qui a pour fils droit l'arbre initial. La liste est de longueur 1 quand son premier maillon est z. Le test a!=&z est donc équivalent à a->fg. Dans la discution précédente, n est bien la taille de l'arbre a initial, c'est-à-dire son nombre de noeuds augmenté d'un. C'est donc bien le nombre de noeuds de l'arbre (linéarisé ou pas) augmenté du noeud z. On aurait pu allouer z par un appel à malloc (ou à nn), mais il aurait fallu faire un appel à free à la fin de la procédure. Il est donc plus simple, et un peu plus efficace, de déclarer z comme une variable de type noeud locale à la procédure, qui est automatiquement détruite à la sortie de la procédure. b est un pointeur sur un pointeur sur un noeud, autrement dit un pointeur sur un abr, comme dans la procédure précédente. La fusion de deux arbres de taille 2^k en un arbre de taille 2^{k+1} se fait par une rotation à droite : *b=rotd(*b) */ abr equilibre(abr a) // Rééquilibre l'arbre a en un temps proportionnel à sa taille { noeud z={0,vide,a}, **b; a=linearise(&z); // a représente une liste chaînée par les fils gauches { int n=taille(a)-1, m, x; // n est la longueur de cette liste for(m=1;m=n if(nfg) if(x+=n,x>=m) *b=rotd(*b),x-=m; } // a est une liste de taille m/2 formée d'arbres de taille 1 ou 2, bien répartis. while(a!=&z) // à chaque itération sa longueur est divisée par 2. for(b=&a;(*b)->fg!=vide;b=&(*b)->fg) *b=rotd(*b); return z.fd; } /* Arbre é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 longue branche, qui est la hauteur de l'arbre. Un arbre binaire de recherche de taille n a une hauteur comprise entre n-1, dans le cas où il ne comporte qu'une seule branche et l'entier le plus proche au dessus du logarithme binaire de n, 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. On doit donc «équilibrer» les arbres binaires de recherche, ce que l'on fait en général, en imposant à chacun de ses noeuds une certaine inégalité portant sur sa taille, sa hauteur et celles de ses fils. On en déduit un algorithme pour insérer (et un pour supprimer) un élément dans un arbre équilibré de telle sorte qu'il reste équilibré. Cette description est assez vague et correspond à des dizaines de méthodes connues différentes. Temps de calcul d'un bon algorithme : O(ln n) ou O(ln n) amorti. Puisque la hauteur d'un arbre de taille n est supérieure à log2(n), la recherche d'un élément dans un arbre binaire de recherche dans le pire des cas prend au moins un temps en O(ln n). Une méthode d'équilibrage peut donc être considérée comme satisfaisante si elle nous assure que toute insertion ou suppression dans un arbre équilibré de taille n se fait en un temps en O(ln n). Mais elle sera aussi satisfaisante si elle a un temps «amorti» en O(ln n), c'est-à-dire si toute suite de k recherches, insertions et suppressions dans un arbre initialement vide et dont la taille ne dépasse jamais n prend un temps total en O(k ln n). Donc le temps moyen pris par une insertion, une suppression ou une recherche est en O(ln n). Attention, ce n'est pas une espérance, ce n'est pas une propriété probabiliste. La majoration porte sur le temps total pris par toute exécution d'un programme. La méthode du bouc émissaire a été inventée par Igal Galperin et Ronald L. Rivest. Scapegoat trees, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pages 165-174 (http://portal.acm.org/citation.cfm?id=313676) Selon cette méthode, un arbre est équilibré si chaque sous-arbre a vérifie hauteur(a)<= log(taille a)/log k pour un certain réel k dans ]1,2[. Le plus petit sous-arbre non équilibré est le bouc émissaire. Il est évidemment sacrifié. Sa structure d'arbre est détruite, et ses noeuds sont réutilisés pour reconstruire un nouvel arbre dont toutes les branches ont presque la même longueur. D'après Q. F Stout et B. L Warren, "Tree rebalancing in optimal time and space" Communications of the ACM, Volume 29 , Issue 9 (Septembre 1986) pp: 902-908, cette opération prend un temps proportionnel à la taille du bouc émissaire, mais elle se fait rarement sur de gros arbres, et la méthode donne quand même un temps amorti en O(ln n). Galperin et Rivest proposaient de noter dans chaque noeud, sa taille, sa hauteur et s'il a été effacé ou non. Dans : General balanced trees. Journal of Algorithms, 30: 1-28, 1999. Arne Andersson explique que tout cela est inutile : On peut supprimer les noeuds dès qu'ils sont inutiles. On peut se passer de la hauteur, car au lieu de comparer le logarithme de la taille à la hauteur, on peut le comparer à la longueur de la branche que l'on vient de rallonger. On peut aussi se passer de la taille de chaque noeud, en ne gardant que la taille totale de l'arbre. On ne cherche un bouc émissaire que lorsque l'on tombe sur une branche trop longue par rapport à la taille totale de l'arbre. On calcule alors la taille des noeuds le long de cette branche, en partant de la feuille au bout de la branche et en ajoutant à chaque fois la taille du frère, que l'on obtient en comptant ses feuilles une par une. On s'arrête dès qu'on trouve un noeud de taille trop petite par rapport à la longueur de la branche déjà parcourue. Ce noeud sera le bouc émissaire. La relation h<=log(t)/log(k) peut se réécrire t>=k^h ou t>=s en posant s=k^h. On peut remplacer la variable h par la variable s. Donc h=1 devient s=k et ++h devient s*=k. En fait pour éviter de faire des calculs sur des nombres réels on prendra plutôt s=2 et s+=(s+1)/2 avec s entier. Cela correspond à peu près à k=1.5 On peut aussi prendre s=2 et s+=s*2/3 qui correspond à k=5./3. */ abr bouc(abr a,elem x) { int ta=2, s=2; abr arrange(abr a) { if(x>a->clef) a->fd=arrange(a->fd), ta+=s?taille(a->fg):0; else if(xclef) a->fg=arrange(a->fg), ta+=s?taille(a->fd):0; else return a; s+=(s+1)/2; if(s && s>ta) a=equilibre(a), s=0; // on a touvé un bouc émissaire, s nul arrête tout. return a; } return arrange(a); } /* abr insere(abr a,elem x) // rend l'arbre obtenu en insérant x dans a { if(a==vide ) a=n2(x) ; else // Si a est vide on rend un nouvel arbre de taille 2 if(xclef) a->fg=insere(a->fg,x); else // On insère x dans le fils gauche if(x>a->clef) a->fd=insere(a->fd,x); // ou le droit. return a; } */ abr insere(abr a,elem x) { int s=2; abr *b=&a; // *b est l'arbre dans lequel insérer x : *b=insere(*b,x) vide->clef=x; while((*b)->clef!=x) s+=(s+1)/2, b=x>(*b)->clef? &(*b)->fd : &(*b)->fg; if(*b!=vide) return a; // *b est non vide quand x==(*b)->cle : x est déjà dans l'arbre *b=n2(x); return s>ta ? bouc(a,x) : a; // si la branche est trop longue, on cherche un bouc émissaire } elem pluspetit(abr a) { while(a->fg!=vide) a=a->fg; return a->clef; } abr enleve(abr a,elem x) { abr *b=&a; // *b est l'arbre duquel enlever x : *b=enleve(*b,x) vide->clef=x; while((*b)->clef!=x) b=x>(*b)->clef? &(*b)->fd : &(*b)->fg; if(*b!=vide) // *b est non vide donc (*b)->cle==x, c'est le noeud à supprimer. { abr c=*b; if(c->fd==vide) *b=c->fg, free(c), --ta; else // Si *b n'a qu'un fils on le remplace par ce fils. if(c->fg==vide) *b=c->fd, free(c), --ta; else // Cette ligne limite la récursivité à 2 niveaux. c->fd=enleve(c->fd,c->clef=pluspetit(c->fd)); } return a; } int main1() { int i; abr a=nn(n2(1),2,n2(3)), b=copie(a), c=eipoc(a); Aff(a); Aff(b); libere(b); Aff(c); libere(c); for(i=0;i<10;i++) a=insere(a,i*3%10*2), Aff(a); Aff(a); a=equilibre(a); Aff(a); for(i=0;i<30;i+=3) printf("%d %s\n",i,recherche(a,i)?"oui":"non"); for(i=0;i<10;i++) a=enleve(a,i*3%10*2), Aff(a); return 0; } int main() { int i, n=100000; abr a=vide; for(i=n;i--;) a=insere(a,i); for(i=n;i--;) a=enleve(a,i); return !a; } /* 1) Compléter la fonction bouc. 2) L'arbre vide ne doit plus être représenté par le pointeur nul mais par : noeud vide[1]={{0,vide,vide}}; Remplacer dans tous le programme les tests !a par a==vide etc. Dans n2 remplacer 0 par vide. Dans recherche, insere et enleve commencer par vide->clef=x; et remplacer les tests a && a->clef!=x par a->clef!=x 3) Ecrire un programme qui insère dans un arbre initialement vide tous les entiers de 1 à 10^k puis les enlève. Regarder le temps de calcul pour k -O0 -O1 -O2 -O3 4 0.02 0.01 5 0.44 0.33 0.32 0.30 */