Arbres binaires de recherche (ABR) en Terminale
Arbres binaires de recherche (ABR), c'est une notion de nsi du chapitre « Structures de données (listes, piles, files, arbres, graphes) », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Arbres binaires de recherche (ABR) : le cours
Un ABR est un arbre binaire où chaque nœud satisfait : tous les nœuds du sous-arbre gauche sont plus petits, tous ceux du droit sont plus grands. Cela permet une recherche rapide.
Exemple
Un dictionnaire organisé en arbre : le mot au milieu est la racine, les mots avant alphabétiquement vont à gauche, les mots après vont à droite.
À retenir
Un ABR bien équilibré permet une recherche en O(log n), mais un ABR dégénéré (comme une liste) en O(n).
S'entraîner sur arbres binaires de recherche (abr)
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
On considère un ABR contenant les valeurs 50, 30, 70, 20, 40, 60, 80. Dessinez l'arbre puis donnez le parcours infixe. Quel est l'intérêt du parcours infixe sur un ABR ?
Corrige cet exercice avec le tuteur →Exercice 2
Représentez le graphe suivant par (1) une matrice d'adjacence, (2) une liste d'adjacence. Sommets : A, B, C, D Arêtes : A-B, A-C, B-C, B-D, C-D Le graphe est-il orienté ou non orienté ? Quel mode de représentation est le plus efficace ici ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Structures de données (listes, piles, files, arbres, graphes) (NSI Terminale).