TP 8 : Arbres binaires de recherche
noeud_t et arbre_t (ces types devraient permettre de représenter une feuille c'est à dire un arbre vide). ? Correction typedef struct noeud_s {.
Parcours dun arbre binaire
ordre infixe : ch
Algorithmes dans les arbres binaires [tn03] - Exercices
Écrivez une classe TNoeudBinaire<T> qui représente un noeud d'un arbre binaire d'éléments de type T. Validez votre classe avec la solution. Solution C++.
ARBRES BINAIRES DE RECHERCHE
Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...
Chapitre 1 - Arbres binaires de recherche
arbre de le représenter avec la tête en bas
INF601 : Algorithme et Structure de données - Cours 2 : TDA Arbre
27 févr. 2010 INF601 : Algorithme et Structure de données. Introduction. Organisation d'un arbre binaire a b c d e g f racine sous arbre Gauche.
Arbres et récursivité
1 juil. 2020 un arbre binaire c'est beaucoup plus compliqué
Conception de structures de données Pourquoi les arbres
Un arbre binaire est une structure permettant de stocker une collection de données de même type. Définition d'un arbre binaire en C arbre vide:.
ARBRES BINAIRES DE RECHERCHE
Dans un arbre binaire de recherche chaque nœud a une clé. soit null. Notez que c'est une recursion terminale ? transformation en forme itérative ...
[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam
Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d'un arbre binaire contenant une valeur entière Ajouter des typedef pour
[PDF] 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
[PDF] Algorithmique Les arbres
Tout arbre binaire de n nœuds possède 2n branches Plus précisément lorsque n ? 1 il possède n ? 1 branches internes et n + 1 branches externes
[PDF] Les arbres - Ecole Mohammadia dIngénieurs-Cours
Dans ce qui suit on traitera les arbres binaires (degré=2) C'est le type le plus basique dont toutes les opérations sont valables pour un arbre n-aire
[PDF] Les arbres binaires de recherche - Zeste de Savoir
12 août 2019 · à créer une structure de données révolutionnaire : les arbres binaires de recherche Qu'est-ce que c'est à quoi ça sert comment ça marche
[PDF] Parcours dun arbre binaire
ordre infixe : chaidl jrkeb f 1 2 Seconde définition des trois parcours Dans la balade schématisée plus haut on ajoute les fils fantômes
[PDF] Structures de données et algorithmes
conventionnel et il est basé sur un arbre de recherche binaire sont liés par cette relation par exemple les nœuds B et C ne sont pas reliés
Les structures de données arbres en langage C - Academiaedu
Les structures de données arbres en langage C Download Free PDF Un arbre binaire est un cas basique: les algorithmes de manipulation d'un tel arbre
[PDF] CH2 ARBRES - IGM
9 IMAC ch 2 17 Propriétés : - un arbre binaire de hauteur n a au plus 2n+1 – 1 noeuds dont 2n noeuds externes - le nombre de feuilles est égal à un de
[PDF] Cours 4 et 5 Les arbres 1 Introduction 11 Définition Larbre est une
C:\ Program Files Send To Norton Word Excel Eudora Word nav exe Word98 exe Définition : un arbre binaire est un arbre dont les nœuds ont au plus
Comment creer un arbre binaire en C ?
Pour faire des arbres en C, tu peux utiliser les structures et les pointeurs. Un peu comme les listes chaînées. Une branche représenté par un pointeur et donc chaque nœud de ton arbre peut être représenter par deux pointeurs.Comment coder un arbre binaire ?
La taille d'un arbre binaire non vide vaut : 1 + taille(sous-arbre gauche) + taille(sous-arbre droit). La hauteur d'un arbre binaire non vide vaut : 1 + max(hauteur(sous-arbre gauche), hauteur(sous-arbre droit)).Quelle est la complexité dans le pire cas de la recherche d'un élément dans un arbre binaire de recherche de hauteur H contenant n nœuds ?
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une clé dans un arbre binaire de recherche équilibré est donc O(log2(n)).- Un arbre binaire de recherche (ABR) est un arbre binaire qui a la propriété suivante : quelque soit le nœud p = <x, G, D>, les nœuds appartenant `a son sous-arbre gauche G ont des valeurs strictement inférieures `a x, et les nœuds appartenant son sous-arbre droit D ont des valeurs supérieures ou égales x.
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
recherchequotesdbs_dbs4.pdfusesText_7[PDF] arbre binaire java
[PDF] retour ? l'unité proportionnalité
[PDF] le timbre d'un son
[PDF] psychologie criminelle cours pdf
[PDF] passage ? l'acte psychologie
[PDF] cours de criminologie générale pdf
[PDF] livre criminologie pdf
[PDF] tétraèdre régulier propriétés
[PDF] passage ? l'acte
[PDF] tétraèdre propriétés
[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération
[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques
[PDF] grille estimation dangerosité suicidaire
[PDF] grille d'évaluation de l'urgence suicidaire
