AcademyGilbak LogoAcademyGilbak
Fiches Bristol, Définitions & Cartes Mentales · Bac NSI

Fiches de Révision Haute Fidélité

8 synthèses complètes avec résumés exécutifs, définitions officielles, cartes mentales schématisées et fiches Bristol recto-verso prêtes à imprimer en PDF.

Choisir un chapitre à réviser (8 fiches) :
Fiche de Révision Officielle #1 · Structures de Données

Arbres Binaires & Arbres Binaires de Recherche (ABR)

Programme Terminale NSI
Résumé Synthétique du Chapitre :Un arbre binaire est une structure de données hiérarchique où chaque nœud possède au plus deux sous-arbres (gauche et droit). Dans un ABR, toutes les clés du sous-arbre gauche sont strictement inférieures à la racine, et celles de droite strictement supérieures, permettant des recherches rapides en O(log N).

Recto : Vocabulaire Fondamental, Encadrements & Parcours

RECTO

1. Vocabulaire & Relations Métriques

  • Taille N : Nombre total de nœuds. Hauteur h : Nombre de nœuds sur le plus long chemin.
  • Arbre équilibré : h = ⌊log₂(N)⌋ + 1 (hauteur minimale).
  • Arbre dégénéré / peigne : h = N (comportement d'une liste chaînée).
  • Encadrement fondamental : log₂(N + 1) ≤ h ≤ N.

2. Les 4 Parcours d'Arbres

  • Infixe : Gauche ➔ Racine ➔ Droite (Fournit les éléments triés dans l'ordre croissant pour un ABR).
  • Préfixe : Racine ➔ Gauche ➔ Droite.
  • Postfixe : Gauche ➔ Droite ➔ Racine.
  • En Largeur (BFS) : Niveau par niveau de gauche à droite à l'aide d'une File FIFO.

Verso : Algorithmes Python & Propriétés Clés des ABR

VERSO

3. Implémentation de la Recherche dans un ABR

  • Recherche dichotomique récursive basée sur la comparaison avec la clé courante :
def rechercher_abr(arbre, cle):
    if arbre is None:
        return False
    if cle == arbre.cle:
        return True
    elif cle < arbre.cle:
        return rechercher_abr(arbre.gauche, cle)
    else:
        return rechercher_abr(arbre.droite, cle)

4. Calcul de la Taille et de la Hauteur

  • Taille = 1 + taille(gauche) + taille(droite).
  • Hauteur = 1 + max(hauteur(gauche), hauteur(droite)).
def taille(arbre):
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droite)

def hauteur(arbre):
    if arbre is None:
        return 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))
Formules & Complexités Clés
  • ➔log₂(N + 1) ≤ h ≤ N
  • ➔N_max = 2ʰ - 1 (arbre parfait)
  • ➔Recherche ABR équilibré : O(log N)
  • ➔Recherche ABR peigne : O(N)
Pièges Fréquents & Réflexes Bac
  • •Toujours mentionner l'état de l'arbre (équilibré ou dégénéré) pour justifier la complexité O(log N) ou O(N).
  • •Pour vérifier qu'un arbre est un ABR, faire un parcours infixe : la liste obtenue doit être strictement croissante.