Arbres Binaires Recherche

Introduction Quelle structure de données permet : d’organiser les données selon un ordre donné (numérique, lexicographique, etc.) ; d’effectuer des recherches le plus efficacement possible ; d’accéder à, d’insérer ou de supprimer les données le plus efficacement possible. Tableaux Propriétés On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en $O(n \; \log n)$ ; On peut accéder à une donnée en $O(1)$ ; On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié ! [Lire]