Arbres

À lire absolument pour en découvrir plus ! Introduction Dans ce document, on s'intéresse à une classe de problèmes d'optimisation connus sous le nom général de « problème du sac à dos ». On peut définir ce problème de la manière suivante : *« durant un cambriolage un voleur possède un sac dont la capacité (en poids par exemple) est limitée. Il se trouve face à un ensemble d'objets qu'il veut dérober. [Lire]

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]

La notion de listes chaînées est parfaite pour structurer un ensemble d’élements destinés à être énumérés séquentiellement. Elle permet aussi d’implémenter les structures de piles et de files. Elle n’est cependant pas adaptée aux accès spécifiques à des positions données dans la séquence, puisqu’il faut alors parcourir toutes les cellules depuis le début de la liste jusqu’à la position souhaitée (complexité en $O(N)$). Document de référence pour ce cours Structures arborescentes Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement : [Lire]