Arbres

Th_Info_B - 1M. BENJELLOUN 2003-2004

ArbresUn arbre est soit un arbre atomique (une feuille), soit un noeud et une suite de sous-arbres.

racine

feuilles

noeud interne

fils droit

fils gauche

père

L'ensemble des noeuds est constitué des nœuds internes et des feuilles


L’intérêt de cette organisation est de laisser à l’utilisateur le soin de regrouper les fichiers à sa convenance tout en maintenant une structure hiérarchique.


Représentation symbolique des arbres

Arbre vide Arbre singleton Arbre quelconque

Arbre binaire CECI N'EST PAS UN ARBRE

deux pères


Par définition un arbre est une structure de données constituée d’un nœud appelé racine et de sous-arbres fils de la racine. C’est donc une définition récursive.

Un nœud peut contenir une ou plusieurs valeurs, et on parlera alors d'arbres étiquetés et de la valeur (ou des valeurs) d'un nœud.

racine


Les caractéristiques d’un arbre sont :

La taille de l’arbre est le nombre total de nœuds. La hauteur ou niveau d’un nœud x est le nombre de liens sur l’unique chemin allant de la racine à x, notée h(x).

La hauteur ou profondeur de l’arbre A, h(A) = max { h(x) }

x

racine

x


La longueur de cheminement de l’arbre A, LC(A) = h(x) x

hauteur d'un nœud dans un arbre de racine r:

si x = r h(x) = 0

sinon h(x) = 1 + h(père(x))

La profondeur d'un nœud est la longueur du chemin qui le joint à la racine.La racine est de hauteur 0, ses fils de hauteur 1 et les k autres nœuds de hauteur supérieure à 1.


Exemple de mesuresprofondeur # noeuds # feuilles

0 1 0

1 2 0

2 3 2

3 1 0

4 2 1

5 1 0

6 2 2

Taille = 12 Nbrf = 5h = 6 LC(A) = h(x) x


a

b

c

d

e

f

g

La recherche d'une clé d'un côté sera plus lente qu'une recherche de l'autre côté.

Arbres binaires

a

b

c

d

e

f

g

arbre équilibré

La différence entre la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit est d'au plus une unité.


Arbre binaire typedef struct cellule { int data; struct noeud *fils_gauche; struct noeud *fils_droit; } nœud;


• Un Arbre est un pointeur sur un nœud, la racine de l’arbre :

typedef nœud *arbre;

• Un Arbre vide est un pointeur NULL : arbre = NULL; • Nouveau : il faut faire une allocation mémoire et placer l’étiquette. En cas d’erreur d’allocation le pointeur renvoyé est NULL (l’arbre est vide) :

arbre nouveau_binaire(int elt, arbre racine) { racine = (nœud *) malloc(sizeof (nœud ));

if (racine != NULL)){racinedata = elt;racine fils_gauche= NULL;racine fils_droit=NULL;}

return(racine);}

NULLNULLelt


Il faut relier un noeud à un ou plusieurs sous arbres.

arbre cons_binaire(arbre racine, arbre s_arb_g, arbre s_arb_d)

{racine fils_gauche = s_arb_g;racine fils_droit = s_arb_d;return(racine);

}


Hauteurint HauteurArbre(arbre A) { if(A non vide) return (1 + Max(HauteurArbre(Ag), HauteurArbre(Ad)) );

else return 0;} Complexité : O(n)

Nombre noeudint NbrNoeud(arbre A) { if(A non vide) return (1 + NbrNoeud(Ag) + NbrNoeud(Ad) ); else return 0;}


Max noeudint MaxNoeud(arbre A) { if(A non vide) return Max(data, MaxNoeud(Ag), MaxNoeud(Ad)); else return 0;}

Min noeudint MinNoeud(arbre A) { if(A non vide) return Min(data, MinNoeud (Ag), MinNoeud (Ad)) ; else return 0;}


Arbre binaire de recherche ABR

Un arbre binaire de recherche est un arbre binaire tel que pour tout nœud x , les nœuds de son sous arbre-gauche s’ils en existent ont des valeurs inférieures ou égales à celle de x, et les nœuds de son sous arbre-droit des valeurs strictement supérieures.

X

<=X >X

Ce que l’on traduit par g(A) racine(A) < d(A).

Utilisation importante en Info pour la localisation, +, -, tri …

24

10 37


Un arbre binaire est soit vide, noté Ø, soit de la

forme < r, Ag, Ad > où r est la racine et

où Ag et Ad sont des arbres binaires.

r

<= r > r

Ag Ad


24

29

35

16

1

2720 8

15

Exemple d’arbre binaire de recherche

Tout sous-arbre d’un ABR est un ABR

Ag Ad


test si arbre binaire et de recherche

bool TestABR(arbre T){ if(T non vide){ if( TestABR(Td) est un ABR && TestABR(Tg) est un ABR) {

if((Td pas vide) && (Tddata <= Tdata)) return (probleme) else { if((Tg pas vide) && (Tgdata > Tdata)) return (probleme)

else return (OK) } } else return (???) } else return (???)}

Complexité : O(2n+1) * O(1) = O(n)

x

<= x > xTg Td

racine


12

23

78

9

-77

2210 -2

9

Parcours en profondeur d'un arbre binaire de recherche

On considère l’opération de parcours d’un arbre binaire qui consiste à examiner systématiquement dans un certain ordre tous les nœuds de l’arbres pour effectuer un traitement de données.


Parcours préfixe : 12, 9, -2, -77, 9, 10, 23, 22, 78

12

23

78

9

-77

2210 -2

9

Parcours préfixe

Le parcours en profondeur à gauche consiste à partir de la racine et à tourner autour de l’arbre en allant toujours le plus à gauche possible.

void Prefixe(arbre racine) {

if (! vide(racine)) {

printf(“%d\t”,racinedata);

Prefixe(racinefils_gauche);

Prefixe(racinefils_droit);

}

}

Lister Père

Prefixe(Fils_G)

Prefixe(Fils_autres)


I III

II

SI ABR

Le parcours infixe affiche les

éléments dans l’ordre croissant.

12

23

78

9

-77

2210 -2

9

Parcours infixe

infixe : -77, -2, 9, 9, 10, 12, 22, 23, 78

void infixe(arbre racine) {


infixe(racinefils_gauche);


infixe(racinefils_droit);

}

}

Infixe(Fils_G)

Lister Père

Infixe(Fils_autres)


III

III

Parcours Postfixe :

-77, 9, -2, 10, 9, 22, 78, 23, 12

12

23

78

9

-77

2210 -2

9

Parcours suffixeou Postfixe

void Postfixe(arbre racine) {


Postfixe(racinefils_gauche);

Postfixe(racinefils_droit);


}

}


Exemple: Parcours

3

1 5

0 2 6

Parcours préfixe :

Parcours infixe :

Infixe(Fils_G)Lister PèreInfixe(Fils_autres)

0, 1, 2, 3, 4, 5, 6

3, 1, 0, 2, 5, 4, 6

Parcours postfixe : 0, 2, 1, 4, 6, 5, 3

Posfixe(Fils_G)Posfixe(Fils_autres)Lister Père

4


Exemple: Parcours

1

2 3 4

5 6 7

Parcours préfixe :

Parcours infixe :

Infixe(Fils_G)Lister PèreInfixe(Fils_autres)

Parcours postfixe :

Posfixe(Fils_G)Posfixe(Fils_autres)Lister Père


rechercher : valeur x dans arbre == Rech(x,arbre) booléen

On compare l’élément à la valeur de la racine :

- si le sous-arbre sélectionné est vide, l’élément est absent échecrechercher ( x , ) = faux

- si égalité succès x = r rechercher (x ,<r , g , d > ) = vraie

Recherche d’un élément Recherche dichotomoque

- si la valeur est plus petite, on recommence récursivement dans le sous-arbre gauche ; et réciproquement si la valeur est plus grande dans le sous-arbre droit

x < r rechercher (x , < r , g , d > ) = rechercher (x , g ) x > r rechercher (x , < r , g , d > ) = rechercher (x , d )

Complexité : La complexité au pire est en O ( hauteur de l’arbre ).

24

29

35

16

2720 3

5

1


24

29

35

16

1

2720 3

5

Soit à rechercher 20 dans l'arbre suivant

20 est plus petit que 24

20 est plus grand que 16

20 est trouvé


Adjonction d’un élément aux feuilles

L’adjonction aux feuilles d’un élément se réalise en deux étapes : - étape de recherche pour savoir où insérer le nouvel élément ;- adjonction elle-même.

arbre ajout_feuille (arbre A, int e ) {if (A== )

return < e , , >else if ( e racine(A) )

return < racine(A) , ajout_feuille( g(A) , e ) , d(A) > else

return < racine(A) ,g(A) , ajout_feuille( d(A) , e ) >}

La complexité d’une adjonction est O ( h(A) ).

e


arbre insert(arbre T, int x) {if(T vide) { //sommet vide T = (struct nœud *) malloc(sizeof(struct nœud)) Tdata = x Tdroit = NULL Tgauche = NULL}else{ //sommet non vide if(Tdata == x) //ne rien faire !! else { if(x < Tdata) //inserer ds arbre gauche Tg = insert(Tg, x) else //inserer ds arbre droit Td = insert(Td, x) }}return T

}

NULLNULLx


ABR réduire la complexité en temps

Alors que l’insertion dans un tableau nécessite de déterminer sa place, en parcourant le tableau depuis le début (k comparaisons) puis de décaler les (n-k) éléments successeurs pour ménager une place. Donc une complexité en O(n) avec n le nombre d’éléments du tableau.

La complexité d’un ajout est O ( h(A) ).

mais pas la complexité de la programmation !!!


soit on remplace le nœud à supprimer par le plus grand élément de son sous-arbre gauche, soit on le remplace par le plus petit élément de son sous-arbre droit.

Suppression d’un élément

arbre supprimer (arbre , valeur) arbre

• recherche de l’élément à supprimer

• suppression qui dépend de la place de l’élément

nœud sans filsnœud avec un seul filsnoeud avec deux fils

immédiate

remplace le nœud par son fils


arbre suppression ( arbre A , int e ) {

if (A== ) // recherche de l’élément à supprimer return erreur; if ( e < racine(A) ) return < racine(A), suppression( g(A) , e ) , d(A) ); else if ( e > racine(A) ) return < racine(A), g(A) , suppression( d(A) , e ) ); else { // on l’a trouver donc suppression

if est_feuille(A)

return ( );

else if (g(A) == ) return d(A);

else if (d(A) == ) return g(A); else { // on ajoute l’élément le plus à droite du sous-arbre gauche retourner < max_noeud(g(A)) , retire_max(g(A)), d(A) > }

}}


int max_noeud ( arbre A) { // retourne le plus grand élément de l’arbre A, le plus à droite

if ( d(A) == ) return racine(A);else return max_noeud(d(A)) ;

}

// retourne l’arbre privé de son plus grand élément

arbre retire_max ( arbre A ) {

if ( d(A) == ) return g(A);

else return < racine(A) , g(A) , retire_ max(d(A)) >;

}

La complexité est O ( h(A) ).


La structure de tas est un arbre vérifiant les deux propriétés suivantes:• L’arbre est un arbre binaire parfait• La valeur de tout nœud est >= à celle de ses descendants

La structure de tas

Arbres binaires completsUn arbre binaire est complet si tous les nœuds qui ne sont pas des feuilles ont 2 fils.

15

14 2

8 13

7 5


Arbres binaires parfaits, ordre hiérarchique

Un arbre binaire est parfait si toutes ses feuilles sont situées sur les deux derniers niveaux, l’avant dernier étant complet, et les feuilles du dernier sont le plus à gauche possible. Attention ! un arbre binaire parfait n’est pas forcément complet.

tas 15

14 2

8 13


Tas = arbre binaire parfait partiellement ordonné

arbre parfait:

– toutes les feuilles sont sur les deux derniers niveaux,

– l'avant dernier niveau est complet

– les feuilles du dernier niveau sont le plus à gauche possible

partiellement ordonné:

– tout nœud est plus grand que ses deux fils

24

23

7

16

1

2210 8

5 4


15

14 2

8

7 5


Tests !!

Arbre binaire complet ?


15

14 2

8 13

7 5


9


Tests !!


Arbres binaires parfaits, ordre hiérarchiqueUn arbre binaire est parfait si toutes ses feuilles sont situées sur les deux derniers niveaux, l’avant dernier étant complet, et les feuilles du dernier sont le plus à gauche possible. Attention ! un arbre binaire parfait n’est pas forcément complet.

15

14 2

8 13

7 5


Arbre binaire parfait?

Tests !!


24

23

7

16

1

2210 8

5

Exemple de tas

Profondeur ou Nbr nœuds Niveau Max 0 20 = 1

1 21 = 2

2 22 = 4

h=3 au Max 23 = 8

Racine = + gd valeur

= 2h+1 - 1N <=

La structure de tas


Nœud x en i, son père est en i/2

Nœud x en i, son fils gauche en 2*i

Nœud x en i, son fils droit en 2*i+1

24

23

7

16

1

2210 8

5 Exemple de tas

Profondeur ou Nbr nœuds Niveau Max 0 20 = 1

1 21 = 2

2 22 = 4

3 au Max 23 = 8

1

2 3

2*2=4 5 6 2*3+1=7

8 9 10

Index

Index

2*Index 2*Index + 1

4


24

23

7

16

1

2210 8

5

1

2 3

2*2=4 5 6 2*3+1=7

8 9 10

Index

4

24 16 23 7 1 2210 8 5 4

i 1 2 3 4 5 6 7 8 9 10

tab[i]

int pere(i){ return (i/2);} int gauche(i){ return (2 * i);} int droit(i){ return (2 * i + 1);}

Relation entre un tas et tableau


Opérations sur les tas

Insertion d’un élément dans un tas

24

23

7

16

1

2210 8

5 4 22

24

23

7

16

1

2222 8

5 4 10

Nouveau nœud insérer le plus à gauche possible sur le niveau de profondeur le plus élevée. tjr arbre binaire complet mais pas forcement un tas.


24

23

7

16

1

2222 8

5 4 10

24

23

7

22

1

2216 8

5 4 10

Compléxité : O(h) avec h : hauteur du tas Or la hauteur d’un tas de taille n = log2n l’insertion requiert un temps O(logn)

tant que ( y racine ) et ( y > père(y) ) faire

échanger y et père(y)

1

2 3

4 5 6 7

8 9 10 11

Insertion de n éléments O(nlogn)


void ajouter (int tab[], int ntas , int val ){ // ajoute l’élément x au tas de ntas éléments

int i;ntas ++ ;i =ntas ;tab[i] = val ;while ( ( i > 1 ) && ( tab[i/2] < tab[i] ) ){

Echanger ( tab[i], tab[i / 2] );i = i/2 ;

}}

VERIFICATION


24 16 23 7 1 2210 8 5 4

i 1 2 3 4 5 6 7 8 9 10

tab[i]

Avant l’ajout

while ( tab[i /2] < tab[i ] ) {

Echanger ( tab[i], tab[i / 2] );

i = i/2 ;

}

24 16 23 7 1 2222 8 5 4 tab[i] 10

Echanger

i = i/2 i=11/2=5

Echanger i = i/2 i=5/2=2

24 22 23 7 1 2216 8 5 4 tab[i] 10

22+

11


24 22 23 7 1 2216 8 5 4 tab[i] 10

i 1 2 3 4 5 6 7 8 9 10 11

24

23

7

22

1

2216 8

5 4 10

1

2 3

4 5 6 7

8 9 10 11

CQFD


Exce : Construction d’un tas

8 15 2 3 5 1413tab[i]

i 1 2 3 4 5 6 7

8

15

15

8

tas +15

8 2

15

8 2

1315

13 2

8

+ 15

13 2

8 14

tas tas 15

14 2

8 13

+

+tas 15

14 5

8 13 2 3


8 15 2 3 5 1413tab[i]

i 1 2 3 4 5 6 7

int i;

ntas ++ ;

i =ntas ;

tab[i] = val ;

while ( ( i > 1 ) && ( tab[i/2] < tab[i] ) ){


i = i/2 ;

}

8 15 tab[2/2] < tab[2] 8 15

1315 2 3 5 14 8

1315 2 3 5 14 8

1415 2 3 5 13 8

8 15 2 3 5 1413tab[i]

i 1 2 3 4 5 6 7

8 15 2 3 5 1413tab[i]


tab[i]

i 1 2 3 4 5 6 7

1415 2 3 5 13 8

int i;

ntas ++ ;

i =ntas ;

tab[i] = val ;

while ( ( i > 1 ) && ( tab[i/2] < tab[i] ) ){


i = i/2 ;

}

1415 5 3 2 13 8

1415 5 3 2 13 8

1415 5 3 2 13 8

15

14 5

8 13 2 3


Suppression d’un élément

On remplace la valeur du nœud par celle du nœud le plus à droite possible sur le niveau de profondeur le plus élevée, nœud que l’on supprime alors, puis permutations.

Exp: racine : suppression du premier élément de la file

24

23

7

16

1

2210 8

5 4

4

23

7

16

1

2210 8

5 4


4

23

7

16

1

2210 8

5

23

4

7

16

1

2210 8

5 23

22

7

16

1

4 10 8

5


Tri par tas [Heap sort]

Principe : deux phases

- Construire un tas contenant les n éléments par adjonction successives ; en O (n log n).

- Tant que le tas n’est pas vide, répéter l'opération de prendre l'élément de la racine (max),

le retirer du tas avec réorganisation, mettre ce max à sa place définitive ; en O (n log n).

15

14 5

8 13 2 3

3

14 5

8 13 2 15

réorganisation

Suppression


3

14 5

8 13 2 15

réorganisation14

13 5

8 3 2 15

2

13 5

8 3 14 15

Suppression


trier_tas(A) { construire_tas(A)

while( …) {

echanger A[1] avec A[taille]supprimer A[taille]taille = taille – 1

reorganisation() } }


Test !!!

8 15 2 3 5 14 13tab[i]

i 1 2 3 4 5 6 7

1: construction d’un tas

2: ajout de 20


15

13 14

3 2 5 8

20

20

15 14

13 2 5 8

3

15 13 14 3 2 5 8 20+i 1 2 3 4 5 6 7

Test !!!


Test !!!

5, 1, 7, 3, 4, 6, 2

Construction d’un arbre binaire

de recherche (ABR).

i 1 2 3 4 5 6 7

r

<= r > r

Ag Ad

Prefixe, Infixe , Postfixe ??


Application : Imprimante en réseau

JbU5

Tri:Arbre

JbUn

JbU1

JbUn

JbU1

User1

User2

UserN

JbUnJbU1

FIFO


Diviser pour régner

Existe-t-il une méthode pour rechercher une récursivité et évaluer a priori sa complexité?

On peut couper un problème de taille N en A problèmes identiques

Recomposition de ces A problèmes se fait en un temps d'ordre N


Exemple : TRI par FUSION

Pour trier un tableau t de n éléments, on le scinde en deux tableaux de même taille (à un élément près). On les note t1 de taille n1 et t2 de taille n-n1.Ces deux tableaux sont ensuite triés (appel récursif) et enfin fusionnés de manière à reformer le tableau t trié.

scinder

scinder

scinder

fusionner fusionner

fusionner

T(N) = 2 * T(N/2) + ordre Nd'oùT(N) = N log2N

tableau t


Quicksort : tri rapide Principe : ‘’ diviser pour régner ‘’On prend un élément au hasard dans le tableau à trier. Soit p (pivot) sa valeur. On partitionne le reste du tableau en 2 zones: les éléments plus petits ou égaux à p, et les éléments plus grands à p. Si on arrive à mettre en tête du tableau les plus petits que p et en fin du tableau les plus grands, on peut mettre p entre les deux zones à sa place définitive. On recommence récursivement la procédure Quicksort sur chacune des partitions tant qu'elles ne sont pas réduites à un élément.

A la fin, la liste est triée par ordre croissant.

p > pivot pivot

g > pivotG pivotG d > pivotD pivotD


p > pivot pivot

void Quicksort ( int tab[] , int g , int d ) { // Quicksort ( tab , 0 , n )

int k; //position du pivot

if( g < d){ Placer (tab , g , d , &k); Quicksort (tab , g , k - 1); Quicksort (tab, k + 1 , d); }}

g d


p p p p > p p > p > p > p x

i L K j j+1

La fonction Placer : La partition et le placement du pivot ne nécessitent qu’un parcours.

On utilise deux compteurs L et K qui partent des extrémités du sous-tableau, et qui vont l’un vers l’autre :- L part de i+1 et avance tant que l’on rencontre un élément à p.- K part de j et recule tant que l’on rencontre un élément > à p.

On échange les deux éléments et on recommence la progression jusqu’à ce que les deux compteurs se croisent : la place définitive du pivot est en k, et on y place le pivot p par échange avec un élément à p.

complexité en moyenne O (n log n).


Exemple de tri rapide

55 33 22 66 44 11 33 77

33 22 66 44 11 33 77

i j

55

33 22 66 44 11 33 77

33 22 33 44 11 66 77

33 22 33 44 11 66 77 55


Arbres balancés ou B-arbres

• prendre en compte la taille des blocs disques

• regrouper les nœuds voisins dans un même bloc

Les B_arbres sont des arbres de recherche équilibrés conçus pour être efficaces sur des disques ou d'autres unités de stockage secondaire à accès direct.

Dans une application classique ayant recours aux B_arbres, la quantité de données gérées est si grande qu’elles ne tiennent pas toutes en même temps dans la mémoire principale.

Généralisation des ABR


Éclatement d'une racine


Soient - B boules blanches et N boules noires dans une urne.- B 0, N 0, B+N 1- Une réserve infinie de boules

Mode de fonctionnement Tirage aveugle de 2 boules- si les boules sont de même couleur, on remet une boule noire dans l'urne- sinon, on remet une boule blanche

Le jeu se termine lorsqu'il ne reste plus qu'une boule dans l'urne

QuestionQuelle est la couleur de la dernière boule connaissant les nombres initiaux N et B?

Jeu de l'urneÉviter de ‘’ réinventer la roue ‘’


Le jeu se terminera-t-il ou pas?

Le jeu se terminera car à chaque tirage, le nombre de boules dans l'urne diminue de 1.

Tirage aveugle de 2 boules

- si les boules sont de même couleur, on remet une boule noire dans l'urne

- sinon, on remet une boule blanche


RESOLUTION :

Le jeu se terminera car à chaque tirage, le nombre de boules dans l'urne diminue de 1.

Exemple avec 3 Boules:

GENERALISER

2Bles de même couleur N

sinon, on remet boule blanche


GENERALISER !! Impensable


AUTRE APPROCHE :

Tirages possibles et propriétés?

(B-2) + (N+1)

B + (N-1)

B + (N-1)

Conclusion La parité des blanches est inchangée. Donc, si le nombre initial B est impair, la dernière boule sera blanche, sinon, elle sera noire.

Documents

Arbres