Fiche de révision : Arbres binaires en algorithmique

Plan du Cours

  1. Arbres et hiérarchie des données
  2. Vocabulaire des arbres binaires
  3. Clés et interface du type arbre
  4. Hauteur et taille récursives
  5. Parcours infixe en profondeur
  6. Parcours en largeur d’un arbre binaire
  7. Propriétés des arbres de recherche
  8. Recherche dans un arbre de recherche
  9. Insertion dans un arbre de recherche

1. Arbres et hiérarchie des données

Notions clés & Définitions

  • Arbre : Structure composée de nœuds qui peuvent avoir des enfants, eux-mêmes des nœuds.

Points essentiels

📌 Les tableaux, listes, piles et files sont des structures linéaires, tandis qu’un arbre organise les données de façon hiérarchique.

Astuce mémo

Une liste aligne les éléments, un arbre les organise en niveaux.

2. Vocabulaire des arbres binaires

Notions clés & Définitions

  • Arbre binaire : Structure hiérarchique dans laquelle chaque nœud possède au plus deux fils, appelés gauche et droit.
  • Profondeur : Nombre de nœuds du chemin entre la racine et ce nœud, la racine étant à la profondeur 1.
  • Hauteur : Profondeur maximale de ses nœuds.
  • Racine : Nœud initial d’un arbre.
  • Feuille : Nœud qui n’a aucun fils.

3. Clés et interface du type arbre

Notions clés & Définitions

  • Arbre vide : Arbre ou sous-arbre vide, noté NIL.

★ À maîtriser

  • Le TAD arbre binaire comporte trois attributs récursifs : racine de type E, gauche de type arbre_binaire et droit de type arbre_binaire.

Compléments

  • Chaque nœud d’un arbre binaire peut recevoir une clé qui sert d’étiquette.
  • Un sous-arbre gauche ou droit est lui-même un arbre, même s’il contient un seul nœud ou est vide.

  • L’interface du TAD arbre binaire prévoit les opérations suivantes : le constructeur créerArbre, les sélecteurs get_cle, get_gauche et get_droite, les mutateurs insert_gauche et insert_droite, le prédicat estVide

4. Hauteur et taille récursives

★ À maîtriser

  • La hauteur se calcule récursivement : un arbre vide a une hauteur de 0 et un arbre non vide a une hauteur égale à 1 plus le maximum des hauteurs de ses deux sous-arbres.

  • La taille, c’est-à-dire le nombre de nœuds, se calcule récursivement : un arbre vide a une taille de 0 et un arbre non vide a une taille égale à 1 plus les tailles de ses deux sous-arbres.

Compléments

  • Dans les algorithmes, T.racine désigne la racine de T, T.gauche son sous-arbre gauche et T.droit son sous-arbre droit.

5. Parcours infixe en profondeur

Notions clés & Définitions

  • Parcours infixe : Visite chaque nœud après son enfant gauche et avant son enfant droit, selon l’ordre gauche, racine, droite (GRD).

★ À maîtriser

📌 Le parcours infixe visite les nœuds dans l’ordre gauche, racine, droite (GRD), le parcours préfixe dans l’ordre racine, gauche, droite (RGD), et le parcours suffixe ou postfixe dans l’ordre gauche, droite, racine (GDR).

Compléments

  • Le parcours suffixe ou postfixe récursif traite le sous-arbre gauche, le sous-arbre droit, puis affiche la racine.

Astuce mémo

GRD : gauche, racine, droite.

6. Parcours en largeur d’un arbre binaire

Notions clés & Définitions

  • Parcours en largeur : Le parcours en largeur, ou BFS (Breadth First Search), explore d’abord un nœud source, puis ses successeurs et les successeurs non encore explorés de ceux-ci.

★ À maîtriser

  • Le parcours en largeur place la source dans une file, retire et traite le nœud en tête, ajoute en fin de file ses voisins non explorés, puis recommence tant que la file n’est pas vide.

Compléments

  • Le parcours en largeur utilise une file FIFO et ne fait pas appel à une fonction récursive.

Astuce mémo

Une file d’attente où chaque niveau attend son tour avant le suivant.

7. Propriétés des arbres de recherche

Notions clés & Définitions

  • Arbre binaire de recherche : Un arbre binaire de recherche est un arbre dont les valeurs du sous-arbre gauche sont inférieures ou égales à celles de chaque nœud et celles du sous-arbre droit strictement supérieures.

★ À maîtriser

  • La plupart des opérations dans un arbre binaire de recherche ont une complexité temporelle logarithmique O(log⁡n)O(\log n) dans le cas moyen, grâce à la navigation fondée sur l’ordre des valeurs.

Compléments

  • Les éléments d’un arbre binaire de recherche doivent posséder une relation d’ordre totale permettant de comparer deux éléments.

  • Le premier élément inséré dans un arbre binaire de recherche devient sa racine ; les éléments plus petits sont placés à gauche et les éléments plus grands à droite.

Astuce mémo

À gauche, les valeurs sont inférieures ou égales ; à droite, elles sont strictement supérieures.

8. Recherche dans un arbre de recherche

★ À maîtriser

  • La recherche d’une clé dans un arbre binaire de recherche compare la clé à la racine, renvoie vrai si elles sont égales, poursuit à gauche si la clé est inférieure et à droite si elle est supérieure, et renvoie faux si elle atteint un arbre vide.

Compléments

📌 La recherche dans un arbre binaire de recherche suit les liens de l’arbre en comparant les clés, tandis que la recherche dichotomique accède directement aux éléments d’un tableau.

  • La recherche d’une clé dans un arbre binaire de recherche est récursive.

9. Insertion dans un arbre de recherche

Points essentiels

  • Pour insérer une clé dans un arbre binaire de recherche non vide, on la compare aux nœuds en descendant jusqu’à une feuille, puis on l’ajoute comme fils gauche si elle est inférieure à la clé de cette feuille et comme fils droit sinon.

Tableaux de synthèse

Ordres des parcours en profondeur

ParcoursOrdre
InfixeGauche, racine, droite (GRD)
PréfixeRacine, gauche, droite (RGD)
Suffixe ou postfixeGauche, droite, racine (GDR)

Teste tes connaissances

Teste tes connaissances sur Arbres binaires en algorithmique avec 18 questions à choix multiples et corrections détaillées.

1. Un système de fichiers doit représenter les dossiers et sous-dossiers à plusieurs niveaux de profondeur. Quelle propriété distingue le mieux une structure adaptée à cette organisation d’une liste simple ?

2. Dans un modèle de données, des éléments sont reliés de sorte que certains peuvent en contenir ou en désigner d’autres comme enfants. Quelle structure correspond à cette description ?

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de Arbres binaires en algorithmique avec 55 flashcards interactives.

Quelle organisation des données caractérise les tableaux, listes, piles et files ?

Une organisation linéaire.

Quelle organisation des données caractérise un arbre ?

Une organisation hiérarchique.

De quels éléments un arbre est-il composé ?

De nœuds pouvant avoir des enfants qui sont eux-mêmes des nœuds.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches