Arbres binaires
Il est dès lors facile d'établir par induction qu'un arbre binaire est complet si et seulement si toutes ses feuilles sont à la même profondeur. 0. 1. 1. 4 0. 2.
INAL_4_Les arbres
Arbre binaire complet : 1 nœud à la hauteur 0. 2 nœuds à la hauteur 1. 4 nœuds à la hauteur 2 … Nombre total de nœuds : 1 + 2 + 22 + … + 2h = 2h+1 - 1.
Arbres binaires
complets et de même hauteur. Un arbre binaire est complet si et seulement si toutes ses feuilles sont à la même profondeur.
INF601 : Algorithme et Structure de données - Cours 2 : TDA Arbre
27 févr. 2010 Arbre binaire complet (uniforme) : Chaque niveau est complètement rempli. I.E. Tout sommet est soit une feuille au dernier niveau soit.
Algorithmique et Structures de données
Donner des exemples d'arbres binaires complets. 2. Ecrire une fonction qui teste si un arbre binaire est complet. Exercice 5.6 Arbre binaire parfait. On
stage graphes
Dans un arbre binaire presque complet ayant n sommets montrer que le nombre maximal de descendants d'un fils de la racine est 2n/3. On pourra commencer par le
Arbres binaires de recherche
25 août 2017 Théorème 2 Un arbre binaire est parfait si et seulement si n = 2h ?1 où h est sa hauteur et n son nombre de nœuds. 1.10 Arbre quasi-complet.
1ere Enseignement transversal
Nous allons nous restreindre aux arbres binaires pour lesquels la liste des références vers (Autrement dit un arbre binaire localement complet est un.
Arbres - Algorithmique 1
Arbres binaires. 16. 8. 4. 2. 1 racine nombre de noeuds. Arbre binaire complet : ? à la profondeur p : 2p noeuds. ? nombre total de noeuds :.
Cours 4 : Les arbres binaires
Un arbre binaire est constitué de nœuds. • Chaque nœud « pointe » vers deux nœuds de l'étage inférieur. ?Version récursive. • Un arbre binaire peut être
Cours 4 : Les arbres binaires - LRI
• Un arbre binaire est constitué de nœuds • Chaque nœud « pointe » vers deux nœuds de l’étage inférieur Version récursive • Un arbre binaire peut être vide • Un arbre binaire possède un nœud (étiqueté ou pas) • Un arbre binaire possède deux sous-arbres « fils » 2013-2014 Algorithmique 3
APP3 : Arbres phylogénétiques
Dans un arbre binaire de recherche chaque nœud a une cle ´ Acces aux nœuds :` gauche(x) etdroit(x) pour les enfants de x (nulls’il n’y en a pas) parent(x) pour le parent de x (nullpour la racine) cle(x) pour la cle de nœud´ x (en gen´ eral un entier dans nos discussions)´
Arbres binaires - AlloSchool
Un arbre binaire de recherche (en abrégé : ABR) permet l’implémentation sous forme d’arbre binaire de certaines structures de données stockant des éléments formés d’une clé et d’une valeur tels les dictionnaires 7
Cours 6 Arbres binaires - University of Paris-Est Marne-la
D e nition des arbres BINAIRES Un arbre binaire est une structure permettant de stocker une collection de donn ees de m^eme type D e nitionr ecursive: un arbre binaire est : soitvide soit un noeud contenant une donn ee et ayant2 ls(gauche et droit) qui sont eux-m^emes desarbres binaires L’espace m emoire utilis e par un arbre n’est pas
Cours - NSI Les arbres binaires
Les arbres binaires Vous écrirez tous les codes de ce chapitre dans le même ?chier 1Dé?nition Un arbre binaire est un arbre de degré 2 au plus (dont les noeuds sont de degré 2 au plus) Vocabulaires : † Les enfants d’un noeud sont lus de gauche à droite et sont appelés : ?ls gauche et ?ls droit
Searches related to arbre binaire complet PDF
Arbre binaire complet : 2h+1 1 nœuds dans un arbre de hauteur h donc hauteur h= dlg(n+ 1)e 1 pour nnœuds est possible Insertion successive de 1;2;3;4;:::;ndonne un arbre avec h= n 1
Comment faire un arbre binaire?
1. Nommer les différents termes et notions autour des arbres : nœuds, racine, feuilles, hauteur d’un arbre; 2. Représenter une information sous forme d’arbre binaire; 3. Écrire un algorithme récursif simple de parcours et de recherche dans un arbre; 4.
Quelle est la hauteur d’un arbre binaire de recherche?
Un arbre binaire de recherche est un arbre AVL si, pour n’importe lequel de ses nœuds, la di?érence de hauteur entre ses deux ?ls di?ère d’au plus un. Exemples d’arbres AVL 18 14 10 3 11 15 16 42 27 23 32 59 78 51 18 70 62 98 Hauteur d’un arbre AVL Proposition 3.Soit un arbre AVL de hauteur h et possédant n nœuds. On a : h6 3 2 log2(n + 1).
Quels sont les différents types de nœuds dans un arbre binaire ?
Mais pour un arbre binaire, comme chaque parent n'a au maximum que 2 enfants, on distingue l'enfant gauche de l'enfant droit. Alors il y a 4 sortes de nœuds : Ceux comme Dqui n'ont aucun enfant : ce sont les feuilles de l'arbre. Ceux qui n'ont qu'un enfant gauche. Ceux qui n'ont qu'un enfant droit. Ceux comme Bqui ont deux enfants.
Comment l'arbre binaire permet-il de parcourir l'arbre ABCDEFGHI?
La structure d'arbre binaire permet de parcourir l'arbre ABCDEFGHI sans utiliser les étiquettes des nœuds. On peut donc mettre des étiquettes identiques sur plusieurs nœuds et ainsi, donner un sens à l'arbre binaire. Par exemple : Les étiquettes des feuilles représentent soit des constantes 2, 3, 5 soit la variable x.
![Cours 4 : Les arbres binaires Cours 4 : Les arbres binaires](https://pdfprof.com/Listes/17/12927-17C4.pdf.pdf.jpg)
Cours 4 : Les arbres binaires
Définition
Implémentation
Manipulation
Définition
Un arbre binaire est un arbre qui
possède au maximum deux sous-arbres (d"où le binaire)2013-2014 Algorithmique2
Deux implémentations
possiblesVersion itérative•Un arbre binaire est constitué de noeuds•Chaque noeud " pointe » vers deux noeuds de l"étage inférieur
Version récursive•Un arbre binaire peut être vide•Un arbre binaire possède un noeud (étiqueté ou pas)•Un arbre binaire possède deux sous-arbres " fils »
2013-2014 Algorithmique3
Utilisation
Enormément d"applications, que ce soit
dans le domaine informatique ou pas :•Expressions mathématiques : 3 + 2*5 - 4 4 3 2 52013-2014 Algorithmique4
Autres exemples
Résultats d"un tournoi à élimination
directe (tennis par exemple)Arborescence de si-alors-sinon(voir les arbres de décision pour les tris vus à la première séance)2013-2014 Algorithmique5
Un peu de vocabulaire
Un arbre est constitué de
noeuds (ou sommetsCes sommets sont reliés par des
arcs (ou arêtes ) orientés : père ®filsIl existe dans tout arbre un noeud qui
n"est le point d"arrivée d"aucun arc : c"est la racine2013-2014 Algorithmique6
Un peu de vocabulaire (2)
Tout autre noeud est la racine d"un
sous-arbre de l"arbre principalUn noeud qui n"est le point de départ d"aucun arc est appelé feuillePour les arbres binaires, on distinguera
de façon visuelle le fils gauche du fils droit2013-2014 Algorithmique7
Un exemple
racine feuilles sommets 4 3 2 52013-2014 Algorithmique8
Un exemple
sous-arbre gauche de "-» 4 3 25sous-arbre droit de "-»
2013-2014 Algorithmique9
Un peu de vocabulaire (3)
La hauteur d"un noeud est la longueur du plus long chemin de ce noeud aux feuilles qui en dépendent plus 1 •C"est le nombre de noeuds du chemin •La hauteur d"un arbre est la hauteur de sa racine•L"arbre vide a une hauteur 0 •L"arbre réduit à une racine étiqueté a une hauteur 1
2013-2014 Algorithmique10
Un peu de vocabulaire (4)
La profondeur d"un noeud est le nombre de noeuds du chemin qui va de la racine à ce noeud•La racine d"un arbre est à une profondeur 0 •La profondeur d"un noeud est égale à la profondeur de son père plus 1 •Si un noeud est à une profondeurp, tous ses fils
sont à une profondeurp+1 Tous les noeuds d"un arbre de même profondeur sont au même niveau2013-2014 Algorithmique11
Premier traitement sur un
arbre L"affichageTrois façons d"afficher •Préfixe•Infixe•Postfixe2013-2014 Algorithmique12
Affichages
Préfixe :•On affiche la racine, puis le sous-arbre gauche, puis le sous-arbre droit Infixe :•On affiche le sous-arbre gauche, puis la racine, puis le sous-arbre droit Postfixe :•On affiche le sous-arbre gauche, puis le sous-arbre droit, puis la racine2013-2014 Algorithmique13
1 3 2 4 5 6Un exemple
2013-2014 Algorithmique14
Résultats
Préfixe :•1 2 4 3 5 6
Infixe :•4 2 1 5 6 3
Postfixe•4 2 6 5 3 1
2013-2014 Algorithmique15
Deuxième traitement
Recherche d"un élémentAu moins deux façons de faire :•DFS :Depth-First Search
ou recherche en profondeur d"abord •BFS :Breadth-First Search
ou recherche en largeur d"abord2013-2014 Algorithmique16
DFS en détail
DFS :•On cherche à la racine•S"il n"y est pas :•On cherche dans le fils gauche•Puis s"il n"était pas dans le fils gauche, on cherche
dans le fils droitIdée : explorer à fond chaque branche avant de passer à la suivanteOn s"arrête quand on a trouvé ou qu"il n"y a plus de branches à explorer
2013-2014 Algorithmique17
Réflexions
On reconnaît encore une fois un
fonctionnement récursifProblème : si l"élément est dans le sous arbre droit de la racine, on va quand même explorer tout le sous-arbre de gauche2013-2014 Algorithmique18
Exemples
1 3 2 4 5 7 62013-2014 Algorithmique19
Avec DFS : on cherche 4
Racine = 1 ®non•On explore le fils gauche•Racine = 2 ®non•On explore le fils gauche-Racine = 4 ®TROUVÉ
2013-2014 Algorithmique20
Avec DFS (2) : on cherche 3Racine = 1 ®non•On explore le fils gauche•Racine = 2 ®non•On explore le fils gauche-Racine = 4 ®non-Pas de fils
•Pas de fils droit •On explore le fils droit•Racine = 3 ®TROUVÉ2013-2014 Algorithmique21
BFS en détail
BFS :•On cherche à la racine•Si l"élément n"y est pas :•On cherche dans les noeuds de profondeur 1•S"il n"est pas dans à la profondeur 1, on cherche à la profondeur 2•Etc...
2013-2014 Algorithmique22
Réflexions
Plutôt un fonctionnement itératifOn va avoir besoin d"une file FIFO (ou autre structure équivalente) pourstocker les noeuds à explorer :•On ne peut pas " sauter » d"un noeud de profondeur pà un autre•Il faut se souvenir de la liste des noeuds à traiter
2013-2014 Algorithmique23
Fonctionnement de la file
Au début, la file contient l"arbre principalSi la valeur n"est pas à la racine du premier arbre de la file•On supprime l"arbre de la file•On ajoute ses deux sous-arbre en fin de file s"ils ne sont pas vides•Et on explore l"arbre suivant, qui est le premier de la file
On s"arrête quand on a trouvé ou que la file est vide2013-2014 Algorithmique24
Exemples
1 3 2 4 5 7 62013-2014 Algorithmique25
Avec BFS : on cherche 3
File = [arbre " 1 »]Valeur de la racine = 1 ®nonOn enlève l"arbre " 1 »et on ajoute ses deux
sous-arbres•File = [sous-arbre gauche de " 1 », sous-arbredroit de " 1 »]•On explore le premier : racine = 2 ®non•On l"enlève et on ajoute ses sous-arbres•File= [sous-arbre droit de " 1 », sous-arbre gauche de
" 2 »]•On explore le premier : racine = 3 ®TROUVÉ2013-2014 Algorithmique26
Avec BFS (2) : on cherche 4File = [arbre " 1 »]Valeur de la racine = 1 ®nonOn enlève l" arbre " 1 »et on ajoute ses deux sous-arbres•File = [s.-a. gauche de " 1 », s.-a. droit de " 1 »]•On explore le premier : racine = 2 ®non•On l"enlève et on ajoute ses deux sous-arbres•File = [s.-a. droit de " 1 », s.-a. gauche de " 2 »]•On explore le premier : racine = 3 ®non•On l"enlève et on ajoute ses deux sous-arbres-File = [s.-a. gauche de " 2 », s.-a. gauche de " 3 », s.-a. droit de " 3 »]-On explore le premier : racine = 4 ®TROUVÉ
2013-2014 Algorithmique27
Comparatif
Avec DFS, on n"a besoin d"aucun
stockage en plus mais on peut s"attarder trop longtemps dans une brancheAvec BFS, on fonctionne par profondeur incrémentale donc on évite le piège mais on a besoin d"un stockage dont la taille augmente à chaque étape2013-2014 Algorithmique28
Les ABR
On voit que la recherche dans les
arbres binaires est peu aiséeAutre problème: où ajouterun élément?Solution : les ABR ou arbres binaires de
recherche2013-2014 Algorithmique29
Définition
Un arbre binaire de recherche (ABR est un arbre binairedans lequel chaque noeud possède une clételle que •chaque noeud du sous-arbre gauche possède une clé inférieure ou égale à celle du noeud considéré•chaque noeud du sous-arbre droitpossèdeune clé supérieure ou égale à celle-ci •(on pourra interdire ou non des clés de valeur égale)
2013-2014 Algorithmique30
Pourquoi les problèmes
sont-ils réglés ?Pour la recherche : à partir de la racine,
on sait si on doit explorer le fils gauche ou le fils droit •DFS devient très efficacePour l"ajout, le nouveau noeud ajouté
devient une feuille•Ici aussi il suffit de faire une DFS en descendant systématiquement à droite ou à gauche suivant qu"on est inférieur ou supérieur à la racine
2013-2014 Algorithmique31
Et si on veut supprimer
un noeud ? Si c"est une feuille•Facile, rien à faire•On garde un ABR Sinon si c"est un noeud avec un seul s.-a.•On le remplace par son sous-arbreSinon•On lui donne la valeur minimale de son sous-arbre droit et on supprime ce noeud (récursif)
2013-2014 Algorithmique32
Exemple
3 6 2 1 4 7 5On supprime 52013-2014 Algorithmique33
On supprime 5
3 6 2 1 4 72013-2014 Algorithmique34
Exemple
3 6 2 1 4 7 5On supprime 22013-2014 Algorithmique35
On supprime 2
3 6 1 4 7 52013-2014 Algorithmique36
Exemple
3 6 2 1 4 7 5On supprime 32013-2014 Algorithmique37
On supprime 3
3 6 2 1 4 7 5 4 6 2 1 4 7 5 4 6 2 1 5 7 4 6 2 1 5 72013-2014 Algorithmique38
quotesdbs_dbs28.pdfusesText_34[PDF] arbre de probabilité pile ou face
[PDF] arbre de probabilité seconde
[PDF] arbre probabilité conditionnelle
[PDF] arbre de décision exercices corrigés
[PDF] arbre de décision data mining
[PDF] cours arbre de décision
[PDF] classification par arbre de décision
[PDF] arbre de décision exemple
[PDF] arbre de décision cart
[PDF] construire un arbre de décision
[PDF] arbre de décision définition
[PDF] dénombrement cours 1ere s
[PDF] apollon et daphné résumé
[PDF] apollon et daphné leur histoire