- Si l'arbre est vide, on créer un nœud avec la valeur à insérer.
- Si l'élément à insérer est plus petit que la valeur de la racine, on l'insère dans le sous-arbre gauche.
- S'il est plus grand que la valeur de la racine, on l'insère dans dans le sous-arbre droit.
[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 d
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)}