Arbres Binaires

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]

Arbres binaires Définition Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition par récurrence suivante : Un arbre binaire est : soit un arbre vide, noté $E$, ne contenant aucun nœud ; soit un nœud, appelé racine, relié à exactement deux arbres binaires $g$ et $d$, respectivement appelés sous-arbres gauche et sous-arbre droit. On note $T(r,g,d)$ l’arbre non vide dont la racine $r$ (on peut aussi indiquer l’étiquette de cette racine). [Lire]