[PDF] [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 



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

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 x1

Arbres

Un a rbrelexicographique , ou arbre en parties communestroi e l e t c n el s em a ei p i main portpispilepicmitemiemale porte

Arbres : 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 feuilles

Arbres : 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 1a2ak

Arbres : définition 3 (graphes)

Un arbre est un graphe

connexe et sans cycle

Arbres : définition 3 (graphes)

Un graphe avec des

cycles

Arbres : définition 3 (graphes)

Un graphe

non connexe

Arbres : définition 3 (graphes)

Un graphe

non connexe

Arbres : définition 3 (graphes)

Graphe

connexe et sans cycle : nb arêtes=nb sommets1

Arbres : vocabulairefrère

hauteur=5 niveaux profondeur=2racine descendant ancetre branche : chemin à la racine

Arbres 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 gauche

Arbres 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), I

G=lsG(p):sous-arbre gauchede p,

I

D=lsD(p):sous-arbre droitde p,

78+

6xh;h78;;i;h+;hx;;i;h6;;iii

Arbres binaires : implémentation

public class Node {

T element;

Node filsG;

Node filsD;

constructeurs getters sett ers }On utiliseranullpour représenter l"arbre vide

Arbres binaires : implémentation

public class Arbre { privateNode racine; publicArbre() { this. racine =null; booleanestVide() { return(this. racine ==null); }Encapsulation :Arbreconnaît sa racine

Arbres binaires : implémentation

12 17 91

146782

1191
racine 671
14 1182
712

Arbres binaires : implémentation

12 17 91

146782

1112
racine.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 apres

Arbres 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 7

12 1 91 67 7 82 61

1 6712
7 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

n

2noeudsa

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

n

2noeudsa

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

n

2noeudsa

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

n

2noeudsa

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 I

8q2G,element(q)x,

I

8q2D,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 16

2667 69 94

883517

29
25

23 2832

302150

66
70
3637
68
52
5134
557

997804471

56 8122

27
ensemble(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 16

2627 67 69 94

88
1 2 416 7 5 3 68913
15 14 12 10 11 17 35

6855 97804471

56 8122

17 929
25

23 2832

302150

66
70
517
52

363734

ABR : Recherche d"un élément

Soiteun élément qui apparaît dans l"arbrea=hx;G;Di: I siexalorse2D.< 34quotesdbs_dbs46.pdfusesText_46