[PDF] Algorithmique Les arbres Idée : on remplace la

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).

quotesdbs_dbs45.pdfusesText_45

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] ALGORITHME DE PILE OU FACE svp essayer de me faire comprendre cette algorithme 2nde Mathématiques

[PDF] Algorithme de Pythagore 2nde Mathématiques

[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques

[PDF] algorithme de recherche dextremum 2nde Mathématiques

[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche intelligence artificielle PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche python PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche séquentielle PDF Cours,Exercices ,Examens

[PDF] Algorithme de resolution dequation de degré 1 ou 2 1ère Mathématiques

[PDF] Algorithme de seconde 2nde Mathématiques

[PDF] Algorithme de suite pour un devoir maison Terminale Mathématiques

[PDF] Algorithme de suites 1ère Mathématiques

[PDF] algorithme de tracé de cercle PDF Cours,Exercices ,Examens