Arbres binaires Chaque noeud a au plus 2 fils : le fils gauche et le fils droit (sa racine est ) fils droit sous−arbre droit noeud fils gauche sous−arbre gauche
Previous PDF | Next PDF |
[PDF] Algorithmique Les arbres
nœud = question, feuille = réponse ; branche gauche étiquetée par FAUX, branche droite par VRAI Recherche : par arbres binaires de recherche Files de priorité
[PDF] Cours 4 et 5 Les arbres 1 Introduction 11 Définition Larbre - LIPN
IUT De Villetaneuse Année 2004-2005 Dépt informatique 2éme Année F Lévy - Algorithmique avancée Page 1/17 Cours 4 et 5 Cours 4 et 5 Les arbres 1
[PDF] Arbres binaires de recherche - CNU 27 Marseille
Arbres binaires : hauteur, nombre de noeuds et nombre de feuilles Un arbre binaire est complet si toutes ses branches ont la même longueur et tous ses noeuds
[PDF] Arbres - Algorithmique 1 - 2019-2020
Arbres binaires Chaque noeud a au plus 2 fils : le fils gauche et le fils droit (sa racine est ) fils droit sous−arbre droit noeud fils gauche sous−arbre gauche
[PDF] Parcours dun arbre binaire
En-dessous : infixe 2 Algorithmes récursifs Pour chacun des parcours définis ci- dessus (postfixe, infixe, préfixe), définir récursivement le
[PDF] Arbres en algorithmique (1)
Arbres Arbres en algorithmique (1) Gilles Aldon, Jérôme Germoni, Jean-Manuel Mény IREM de Deux algorithmes o`u la structure d'arbre reste implicite : 1
[PDF] AGP: Algorithmique et programmation Les arbres - INSA Lyon
20 nov 2007 · s Un arbre binaire est un arbre dont les noeuds ont au plus deux fils s Les algorithmes travaillant sur des arbres sont généralement récursifs
[PDF] Structures de données et algorithmes
Algorithmes de recherche Les arbres généraux (étiquetés) Un arbre est une structure hiérarchique sur des nœuds `a partir d'un nœud particulier, la racine
[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
Arbres
Algorithmique 1
Stéphane Grandcolas
Aix-Marseille Université
2021-2022
Arbres
I définitions, vocabulaire, I arbres binaires, I abres binaires de recherche,Arbres
Arbre syntaxique représentant l"exp. arith.
x(x1)(78+y) xy78 x1Arbres
Un a rbrelexicographique , ou arbre en parties communestroi e l e t c n el s em a ei p i main portpispilepicmitemiemale porteArbres : définition 1
Un arbre est un ensemble organisé de noeuds :
I chaque noeud a un p ère et un seul, I excepté un noeud, la racine , qui n"a pas de père. Les fils d"un no eudpsont les noeuds dont le père estp Les feuilles d"un a rbreso nt les noeuds qui n"ont pas de filsracine feuillesArbres : définition 2 (récursive)
Un arbre (non vide) est constitué
I d"un noeudp, saracine , I d"une suite de sous-a rbres(a1;a2;:::;ak). Les racines des a rbresa1;a2;:::;aksont lesfils de p....p a 1a2akArbres : définition 3 (graphes)
Un arbre est un graphe
connexe et sans cycleArbres : définition 3 (graphes)
Un graphe avec des
cyclesArbres : définition 3 (graphes)
Un graphe
non connexeArbres : définition 3 (graphes)
Un graphe
non connexeArbres : définition 3 (graphes)
Graphe
connexe et sans cycle : nb arêtes=nb sommets1Arbres : vocabulairefrère
hauteur=5 niveaux profondeur=2racine descendant ancetre branche : chemin à la racineArbres binaires
Chaque noeud a au plus 2 fils : le
fils gauche et le fils droit (sa racine est ) fils droit sous-arbre droitnoeud fils gauchesous-arbre gaucheArbres binaires168421
racine nombre de noeudsArbre binaire complet : Ià la profondeurp: 2pnoeuds
I nombre total de noeuds :h1X i=02 i=2h1 Un arbre binaire de hauteurhcontient au plus2h1noeuds (hauteur = nombre de niveaux)Arbres binaires : représentation
Arbre vide :
Arbre non vide :p=hx;G;Di
I x:élément, information, (étiquette, label, valeur), IG=lsG(p):sous-arbre gauchede p,
ID=lsD(p):sous-arbre droitde p,
78+6xh;h78;;i;h+;hx;;i;h6;;iii
Arbres binaires : implémentation
public class NodeT element;
Node filsG;
Node filsD;
constructeurs getters sett ers }On utiliseranullpour représenter l"arbre videArbres binaires : implémentation
public class ArbreArbres binaires : implémentation
12 17 91146782
1191racine 671
14 1182
712
Arbres binaires : implémentation
12 17 91146782
1112racine.filsG racine 671
14 1182
7 91
racine.filsD.filsD
Arbres binaires : parcours en profondeur
Principe :explorer le sous-arbre gauche, puis explorer le sous-arbre droitstaticpublic void parcours(Node node) { if(node !=null) { traitement avant parcours(node.filsG); traitement entre les deux parcours parcours(node.filsD); traitement apresArbres binaires : parcours préfixe
static public void parcours(Node node) { if(node !=null) { node.printNode(); parcours(node.filsG ); parcours(node.filsD); }1 2 3 45 6 712 1 91 67 7 82 61
1 67127 82
6191
Parcoursinfixe, parcourspostfixe.
Arbres binaires : hauteur minimale
Soitaun arbre contenantnnoeuds :
hauteur(a)log2nPreuve.Par induction en utilisant la propriétéh(a) =1+max(h(a1);h(a2))Supposonsn1n2, et doncn1n=2.Hypothèse :h(a1)log2n1donch(a1)log2(n=2) =log2n1orh(a)1+h(a1),Conclusion :h(a)1+log2n1=log2nn
1noeudsa
n2noeudsa
2a1C"est aussi vrai si on considère le nombre de feuilles.
Arbres binaires : hauteur minimale
Soitaun arbre contenantnnoeuds :
hauteur(a)log2nPreuve.Par induction en utilisant la propriétéh(a) =1+max(h(a1);h(a2))Supposonsn1n2, et doncn1n=2.Hypothèse :h(a1)log2n1donch(a1)log2(n=2) =log2n1orh(a)1+h(a1),Conclusion :h(a)1+log2n1=log2nn
1noeudsa
n2noeudsa
2a1C"est aussi vrai si on considère le nombre de feuilles.
Arbres binaires : hauteur minimale
Soitaun arbre contenantnnoeuds :
hauteur(a)log2nPreuve.Par induction en utilisant la propriétéh(a) =1+max(h(a1);h(a2))Supposonsn1n2, et doncn1n=2.Hypothèse :h(a1)log2n1donch(a1)log2(n=2) =log2n1orh(a)1+h(a1),Conclusion :h(a)1+log2n1=log2nn
1noeudsa
n2noeudsa
2a1C"est aussi vrai si on considère le nombre de feuilles.
Arbres binaires : hauteur minimale
Soitaun arbre contenantnnoeuds :
hauteur(a)log2nPreuve.Par induction en utilisant la propriétéh(a) =1+max(h(a1);h(a2))Supposonsn1n2, et doncn1n=2.Hypothèse :h(a1)log2n1donch(a1)log2(n=2) =log2n1orh(a)1+h(a1),Conclusion :h(a)1+log2n1=log2nn
1noeudsa
n2noeudsa
2a1C"est aussi vrai si on considère le nombre de feuilles.
Arbres binaires de recherche
Undictionnaireest un ensemble dynamique d"objets
comparables qui supporte les opérations suivantes : insérer :ajout d"une nouvelle valeur rechercher :recherche d"une valeur supprimer :suppression d"une valeur donnée Exemples :liste, tableau, arbre binaire de recherche,... Objectif :être efficace, utiliser peu d"espace.Arbres binaires de recherche
SoitEun ensemble muni d"unerelation d"o rdre(ordre total) Un arbre binaire étiqueté avec des éléments deEest una rbre binaire de recherche s"il satisfait l"o rdreinfixe, c"est à dire : pour tout noeudp=hx;G;Di I8q2G,element(q)x,
I8q2D,xelement(q).
Les éléments figurant dans l"arbre sont tous différents (i.e. sixyetyxalorsxetysont le même élément)Arbres binaires de recherche> 66 < 66
p 8 162667 69 94
883517
2925
23 2832
302150
6670
3637
68
52
5134
557
997804471
56 8122
27ensemble(N;<)
Arbres binaires de recherche : parcours infixé
Le parcours infixe de l"arbre produit la suite ordonnée des éléments7 8 9 16 17 21 22 23 25 26 27 28 29 30 32 34 35 36 37 ... 8 162627 67 69 94
881 2 416 7 5 3 68913
15 14 12 10 11 17 35
6855 97804471
56 8122
17 92925
23 2832
302150
6670
517
52