Les arbres - LIPN
Les arbres 1 Introduction 1 1 Définition L'arbre est une structure de donnée qui généralise la liste : alors qu'une Algorithme de parcours en largeur
Arbres en algorithmique (1)
Algorithmes utilisant des arbres algorithme de Hu man {compression de donn ees sans perte (JPEG) : entr ee : un texte a coder sortie : une suite de 0 et 1 principe : consiste a construire un arbre binaire, a mettre les lettres sur les feuilles et a les rep erer par le chemin sur l’arbre; algorithme de Dijkstraa :
Cours Algorithmique avancée (WI) cours 3: Les arbres
Les arbres sont des structures de données fondamentales en informatique très utilisés dans tous les domaines parce qu’ils sont bien adaptés à la représentation naturelle d’informations homogènes organisées et d’une grande commodité et rapidité de manipulation Leur usage est multiple car ils captent l’idée de hiérarchie: 3
Algorithmique Les arbres - Laboratoire de Recherce en
Algorithme Entrée:unentierpositifounul n Sortie:unelisted’arbres res
Algorithmique: algorithmes sur les arbres binaires
travaillent sur des structures de donn ees telles que les arbres 2 Calculer la taille d’un arbre: Nous allons maintenant etudier un algorithme qui permet de calculer le nombre de noeuds pr esents dans un arbre Exercice 2: Etudiez cet algorithme: Cet algorithme ressemble beaucoup a l’algorithme etudi e dans l’exercice 1, son etude ne
Algorithmes sur les arbres et les graphes en bioinformatique
comprendre a quelle famille les panda géants appartiennent • Panda géants ressemblent les ours mais ils ont des caractéristiques assez différent et typique des ratons laveurs, il n’hibernent pas par exemple • En 1985, Steven O’Brien et al ont résolu ce problème de classification en utilisant les séquences d’ADN et algorithmes
Arbres et récursivité
Comme pour les listes chaînées, les nœuds contiennent en général une information supplémentaire, leur valeur, qui peut être de n’importe quel type Les arbres servent ainsi de structure de données, c’est-à-dire de contenant pour stocker un certain nombre d’éléments Comme les tableaux et les listes chaînées, on peut ainsi
Structures de donn ees et algorithmes Projet 2: arbres
Deux arbres binaires de recherche La seconde approche, consiste a stocker les villes dans deux arbres binaires de recherche Le premier admet comme cl e les latitudes des villes et le second leur longitude Il s’agira donc de 1 Rechercher S ˚, toutes les villes comprises entre deux latitudes; 2 Rechercher S
[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 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
[PDF] les artisans au moyen age
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 quatregrandes 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 larecherche 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 15433
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 15433
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 15433
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
15433
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
15433
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
15433
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
346 79
1112
1522
25
28
29303133
48croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.
8 de 1
Arbre binaire de recherche
346 79
1112
1522
25
28
29303133
48croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.
8 de 1
Arbre binaire de recherche
346 79
1112
1522
25
28
29303133
48croissance stricte Ici : arbre binaire de recherche (ou ordonné); parcours infixe (ou symétrique); recherche, insertion, suppression.
9 de 1
Arbre Tournoi
6521
2512
1511
483
7 9
281574
29croissance largeIci : arbre tournoi; minimum, insertion, suppression du minimum.
9 de 1
Arbre Tournoi
6521
2512
1511
483
7 9
281574
29croissance 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 res16 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 : C0=1Cn=n-1?
i=0C iCn-1-i.On en déduit
C n=(2n)!n!(n+1)!.Voici les premières valeurs : C0=1,C1=1,C2=2,C3=5,C4=14,C5=42,c6=132.
17 de 1
taille et hauteurDé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)}