[PDF] Algorithmique Les arbres Algorithme. Entrée : un entier

View - Download Algorithmique Les arbres

Previous PDF

Next PDF

1 de 1

Algorithmique

Les arbres

Florent Hivert

Mél :Florent.Hivert@lri.fr

Page personnelle :http://www.lri.fr/˜hivert

2 de 1

Algorithmes et structures de données

La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Nous allons étudier quatre

grandes classes de structures de données :Les structures de données séquentielles (tableaux);

Les structures de données linéaires (liste chaînées);

Les arbres;Les graphes.

3 de 1

Problème de la recherche

On aimerai avoir une structure de donnée où l"insertion et la

recherche sont efficace.Pour les tableaux : insertion enO(n), recherche enO(log(n))Pour les listes : insertion enO(1), recherche enO(n)

4 de 1

Représentations graphiques d"arbres binaires et vocabulaire 154
33
39
1128
721
25
12

291576

5noeuds

branches une branche gaucheune branche droitevaleurs Ici : arbre, noeuds, branches; arbre binaire, branches gauches, branches droites; valeurs (ou étiquettes) des noeuds.

4 de 1

Représentations graphiques d"arbres binaires et vocabulaire 154
33
39
1128
721
25
12

291576

5noeuds

branches une branche gaucheune branche droitevaleurs Ici : arbre, noeuds, branches; arbre binaire, branches gauches, branches droites; valeurs (ou étiquettes) des noeuds.

4 de 1

Représentations graphiques d"arbres binaires et vocabulaire 154
33
39
1128
721
25
12

291576

5noeuds

branches une branche gaucheune branche droitevaleurs Ici : arbre, noeuds, branches; arbre binaire, branches gauches, branches droites; valeurs (ou étiquettes) des noeuds.

5 de 1

Définition récursive

154
33
39
1128
721
25
12

291576

5noeud-racine

arbre videsous-arbre gauche sous-arbre droit Ici : (noeud-)racine, sous-arbre gauche, sous-arbre droit; l"arbre vide, notion récursive d"arbre binaire valué (ou étiqueté);notion récursive de sous-arbre.

5 de 1

Définition récursive

154
33
39
1128
721
25
12

291576

5noeud-racine

arbre videsous-arbre gauche sous-arbre droit Ici : (noeud-)racine, sous-arbre gauche, sous-arbre droit; l"arbre vide, notion récursive d"arbre binaire valué (ou étiqueté);notion récursive de sous-arbre.

5 de 1

Définition récursive

154
33
39
1128
721
25
12

291576

5noeud-racine

arbre videsous-arbre gauche sous-arbre droit Ici : (noeud-)racine, sous-arbre gauche, sous-arbre droit; l"arbre vide, notion récursive d"arbre binaire valué (ou étiqueté);notion récursive de sous-arbre.

6 de 1

Arbres binaires étendus

a15 v4 e33 c3 -9 d11 e28 s7 -21 f25 e12 u29 i15 l7 l6 e5 s feuilles Ici : feuilles; notion récursive d"arbre binaire étendu.

6 de 1

Arbres binaires étendus

a15 v4 e33 c3 -9 d11 e28 s7 -21 f25 e12 u29 i15 l7 l6 e5 s feuilles Ici : feuilles; notion récursive d"arbre binaire étendu.

7 de 1

Vocabulaire

h auteurtaille Ici : structure d"arbre binaire; dimensions : taille, hauteur;

équilibre;

chemin issu de la racine, longueur d"un chemin.

7 de 1

Vocabulaire

h auteurtaille Ici : structure d"arbre binaire; dimensions : taille, hauteur;

équilibre;

chemin issu de la racine, longueur d"un chemin.

7 de 1

Vocabulaire

h auteurtaille Ici : structure d"arbre binaire; dimensions : taille, hauteur;

équilibre;

chemin issu de la racine, longueur d"un chemin.

7 de 1

Vocabulaire

h auteurtaille Ici : structure d"arbre binaire; dimensions : taille, hauteur;

équilibre;

chemin issu de la racine, longueur d"un chemin.

8 de 1

Arbre binaire de recherche

34
6 79
1112
1522
25
28

29303133

48
croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.

8 de 1

Arbre binaire de recherche

34
6 79
1112
1522
25
28

29303133

48
croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.

8 de 1

Arbre binaire de recherche

34
6 79
1112
1522
25
28

29303133

48
croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.

9 de 1

Arbre Tournoi

65
21
2512
1511
483
7 9

281574

29c
roissance largeIci : arbre tournoi; minimum, insertion, suppression du minimum.

9 de 1

Arbre Tournoi

65
21
2512
1511
483
7 9

281574

29c
roissance largeIci : arbre tournoi; minimum, insertion, suppression du minimum.

10 de 1

Termes anglo-saxons

binary tree;node,branch,value,label,root,subtree,leaf;size,height,distance;balanced tree;path from the root,length of a path;infix traversal;valued binary tree,label(l)ed binary tree,extended binary tree,

binary search tree,ordered binary tree,tournament tree.

11 de 1

Applications des arbres

Classifications :par questionnaire binaire :noeud = question, feuille = réponse; branche gauche étiquetée par FAUX, branche droite par VRAI.

Recherche :par arbres binaires de recherche.Files de priorité :par arbres-tournoi : gestion des tampons

avec priorité.

12 de 1

Spécification formelle

Définition (Type abstraitABin)Opérations :

Vide:{} →ABinNoeud:ABin×ABin→ABinEstVide:ABin→BooleenSAG,SAD:ABin→ABin Préconditions :SAD(t),SAG(t)défini seulement si nonEstVide(t)

Axiomes :EstVide(Vide()) =VRAIEstVide(Noeud(g,d)) =FAUXSAG(Noeud(g,d)) =gSAD(Noeud(g,d)) =dNoeud(SAG(t),SAD(t)) =t si nonEstVide(t).

13 de 1

Voici la liste de tous les arbres jusqu"à la taille 3 :

13 de 1

Voici la liste de tous les arbres jusqu"à la taille 3 :

14 de 1

Voici la liste de tous les arbres de taille 4 :

15 de 1

Liste de tous les arbres ànNoeudsAlgorithme

Entrée :un entier positif ou nuln

Sortie :une liste d"arbres

res <- listeVide() si n = 0 alors ajoute(res, arbreVide()) retourner res pour i de 0 à n-1 faire lg <- ALGO(i); ld <- ALGO(n-1-i) pour g dans lg faire pour d dans ld faire ajoute(res, Noeud(g,d)) retourner res

16 de 1

Nombre de Catalan

Proposition

Le nombre d"arbres binaires à n noeuds est appelé n-ième nombre de Catalan noté C n. Les nombre de Catalan vérifient la récurrence : C

0=1Cn=n-1?

i=0C iCn-1-i.

On en déduit

C n=(2n)!n!(n+1)!.Voici les premières valeurs : C

0=1,C1=1,C2=2,C3=5,C4=14,C5=42,c6=132.

17 de 1

taille et hauteur

Définition

On définit deux fonctions sur les arbres binaires : Le nombre de noeuds appeléTaille:Taille(Vide) =0Taille(Noeud(a0,a1)) =1+Taille(a0) +Taille(a1)

Le nombre de noeuds du plus long chemin appeléHauteur:Hauteur(Vide) =0Hauteur(Noeud(a0,a1)) =1+max{Hauteur(a0),Hauteur(a1)}

18 de 1

Comparaison taille/hauteur

Proposition

Pour tout arbre binaire de taille n et de hauteur h : h6n62h-1.

19 de 1

Noeuds

Retenir

Un noeud est ditinternes"il a deux fils non vide. Sinon il est dit externe.internes externes

20 de 1

Retenir

Unebrancherelie un noeuds à l"un des deux sous-arbres. Une brancheest soit la branche gauche soit la branche droite d"un noeud. Une branche estinternelorsqu"elle relie deux noeuds; elle est externedans le cas contraire.internes externes

En conséquence de quoi :

un noeud interne possède deux branches internes; un noeud externe possède au moins une branche externe.

21 de 1

Nombre de branches

Proposition

Tout arbre binaire de n noeuds possède2n branches. Plus précisément, lorsque n>1, il possède n-1branches internes et n+1branches externes.

22 de 1

Retenir

Uncheminde longueur k issu de a est un couple de la forme : (a,?b1,b2,...,bk?) pour lequel il existe t

1,t2,...,tktels que :

en posant t

0=a, tjest le sous-arbre gauche ou droit de a?j-1selon

que lebit de directionbjvaut0ou1.

On dit d"un tel chemin qu"il mène de a à t

k.Le chemin de longueur nulle(a,??)mène deaà lui-même.0101010101 chemin(a,?0,1,0,0?)a=t0t 1t 2t 3t

4Un chemin estinternelorsqu"il mène à un noeud; il estexternesinon.

22 de 1

Retenir

Uncheminde longueur k issu de a est un couple de la forme : (a,?b1,b2,...,bk?) pour lequel il existe t

1,t2,...,tktels que :

en posant t

0=a, tjest le sous-arbre gauche ou droit de a?j-1selon

que lebit de directionbjvaut0ou1.

On dit d"un tel chemin qu"il mène de a à t

k.Le chemin de longueur nulle(a,??)mène deaà lui-même.0101010101 chemin(a,?0,1,0,0?)a=t0t 1t 2t 3t

4Un chemin estinternelorsqu"il mène à un noeud; il estexternesinon.

22 de 1

Retenir

Uncheminde longueur k issu de a est un couple de la forme : (a,?b1,b2,...,bk?) pour lequel il existe t

1,t2,...,tktels que :

en posant t

0=a, tjest le sous-arbre gauche ou droit de a?j-1selon

que lebit de directionbjvaut0ou1.

On dit d"un tel chemin qu"il mène de a à t

k.Le chemin de longueur nulle(a,??)mène deaà lui-même.0101010101 chemin(a,?0,1,0,0?)a=t0tquotesdbs_dbs10.pdfusesText_16

[PDF] Les arbres et la neige

[PDF] les arbres rouges de maurice vlaminck

[PDF] les arenes de nimes

[PDF] les arguments de créon pour convaincre antigone

[PDF] les arguments de la dérive des continents

[PDF] lES ARGUMENTS DE WEGENER

[PDF] Les arguments envers les Incas-Espagnols

[PDF] les arguments et les exemples

[PDF] Les arméniens pendant la 1ere Guerre Mondiale

[PDF] Les Armes sont-elles nécessaire

[PDF] Les arrondis au centième et millimètre près

[PDF] les articles en espagnol pdf

[PDF] Les articles indefinis

[PDF] Les artificiers DM

[PDF] les artificiers sont cachés du public par un mur de hauteur 2m