Numérique et sciences informatiques (NSI) · Terminale

Fiche de révision : arbres binaires et arbres binaires de recherche

L’essentiel à connaître, sur une seule page. Imprime-la ou enregistre-la en PDF.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Arbres binaires et arbres binaires de recherche

Un arbre binaire est vide ou formé d’une racine et de deux sous-arbres ; ordonné, c’est un arbre binaire de recherche.

Mesures

  • Taille n : nombre de nœuds. Hauteur h : plus grande profondeur (vide = 0, racine seule = 1 dans ce cours).
  • h ≤ n ≤ 2h − 1.
  • taille(a) = 1 + taille(gauche) + taille(droit) ; hauteur(a) = 1 + max(…).

Parcours

  • Préfixe : nœud, gauche, droite.
  • Infixe : gauche, nœud, droite.
  • Suffixe : gauche, droite, nœud.
  • Largeur : niveau par niveau, avec une file.

ABR

  • Pour chaque nœud : clés à gauche < clé < clés à droite.
  • Recherche et insertion : un seul chemin depuis la racine, coût ≤ h.
  • Équilibré : h ≈ log₂(n) ; filiforme : h = n.

Pièges à éviter

  • Ne pas vérifier la convention de hauteur de l’énoncé.
  • Vérifier la propriété d’ABR seulement entre un nœud et ses enfants directs.
  • Confondre préfixe (nœud en premier) et suffixe (nœud en dernier).
  • Oublier le cas de l’arbre vide dans une fonction récursive.

À découvrir aussi