Structures de données linéaires

Si un problème peut être résolu avec une séquence ordonnée d'éléments (element), l'approche la plus simple pourrait être de les stocker dans une liste. Certains problèmes exigent que les actions soient effectuées dans un ordre chronologique strict, comme le traitement des éléments dans l'ordre de leur arrivée ou dans l'ordre inverse. Dans ces situations, une structure de données linéaire (linear data structure), qui est une catégorie de structures de données où les éléments sont ordonnés en ligne, est appropriée. Il existe deux implémentations possibles pour le type abstrait de données liste. La première, une liste de tableau (array list) (Figure 3.3), est une structure de données qui stocke les éléments de la liste côte à côte en mémoire. L'autre est une liste chaînée (linked list) (Figure 3.4), qui est une structure de données de liste qui ne stocke pas nécessairement les éléments de la liste côte à côte, mais fonctionne plutôt en maintenant, pour chaque élément, un lien vers l'élément suivant dans la liste. Les listes de tableaux et les listes chaînées sont toutes deux des structures de données linéaires car leurs éléments sont organisés en ligne, l'un après l'autre. Un avantage des listes de tableaux est qu'elles permettent un accès (aléatoire) à chaque élément de la liste en une seule étape. Cela contraste fortement avec les listes chaînées, qui ne prennent en charge que l'« accès séquentiel ». D'autre part, les listes chaînées prennent en charge des opérations d'insertion et de suppression rapides, ce que les listes de tableaux ne font pas.

Figure 3.3 Une liste de tableau stocke les éléments côte à côte en mémoire dans l'ordre exact de la liste. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Figure 3.4 Une liste chaînée maintient un lien pour chaque élément vers l'élément suivant dans la liste. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Plus tôt, nous avons présenté les ensembles comme offrant moins de fonctionnalités que les listes. Les listes de tableaux et les listes chaînées peuvent également implémenter le type abstrait de données ensemble (set). Les ensembles diffèrent des listes de deux manières : les ensembles sont non ordonnés — les éléments ne se voient donc pas attribuer de positions spécifiques — et les ensembles ne sont composés que d'éléments uniques. En plus d'implémenter les ensembles, les structures de données linéaires peuvent également implémenter les types abstraits de données carte, file de priorité et graphe. Si les structures de données linéaires peuvent couvrir un si large éventail de types abstraits de données, pourquoi apprendre d'autres structures de données ? En théorie, toute donnée complexe peut être représentée avec une liste de tableau ou une liste chaînée, bien que cela puisse ne pas être optimal, comme nous l'expliquerons plus en détail.

Un inconvénient de ne s'appuyer que sur des structures de données linéaires est lié au concept d'efficacité. Même si les structures de données linéaires peuvent résoudre n'importe quel problème, nous pourrions préférer des structures de données plus spécialisées qui peuvent résoudre moins de problèmes plus efficacement et aider à représenter plus fidèlement les arrangements de données du monde réel. Cela est particulièrement utile lorsque nous avons de grandes quantités de données comme des lieux ou des routes dans une carte en ligne du monde entier. Les structures de données linéaires organisent finalement les éléments en ligne, ce qui est nécessaire pour implémenter les listes mais pas pour d'autres types abstraits de données. D'autres structures de données se spécialisent dans l'implémentation d'ensembles, de cartes et de files de priorité en organisant les éléments dans une hiérarchie plutôt qu'en ligne.

Structures de données arborescentes

Un arbre (tree) est une structure de données hiérarchique. Bien qu'il existe de nombreux types de structures de données arborescentes, toutes partagent la même structure d'organisation de base : un nœud (node) représente un élément dans un arbre ou un graphe. Un nœud peut ou non avoir un descendant. Un nœud enfant (child node) est un descendant d'un autre nœud. Souvent, le nœud principal est appelé « nœud parent (parent node) ». Les arbres maintiennent une hiérarchie par le biais de relations parent-enfant, qui se répètent du nœud racine (root node) au sommet de l'arbre jusqu'à chaque nœud feuille (leaf node), qui se trouve au bas de l'arbre et n'a pas d'enfants. La hauteur d'un arbre correspond à la profondeur de la hiérarchie des descendants. La Figure 3.5 illustre la structure et les éléments d'un arbre.

Figure 3.5 Un arbre est une structure de données hiérarchique avec des nœuds où chaque nœud peut avoir zéro ou plusieurs nœuds enfants descendants. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Arbres binaires de recherche

Un arbre binaire de recherche (binary search tree) est un type de structure de données arborescente souvent utilisé pour implémenter des ensembles et des cartes avec la propriété d'arbre binaire (binary tree property), qui exige que chaque nœud puisse avoir zéro, un ou deux enfants, et la propriété d'arbre de recherche (search tree property), qui exige que les éléments de l'arbre soient organisés du plus petit au plus grand de gauche à droite. En d'autres termes, les valeurs de tous les éléments du sous-arbre gauche d'un nœud ont une valeur inférieure à celle du nœud. De même, les valeurs de tous les éléments du sous-arbre droit d'un nœud ont une valeur supérieure à celle du nœud. La propriété d'arbre de recherche suggère que lorsque les éléments sont lus de gauche à droite dans un arbre de recherche, nous obtiendrons les éléments dans l'ordre trié. Pour les nombres, nous pouvons comparer et trier les nombres par leurs valeurs numériques. Pour des données plus complexes comme des mots ou des phrases, nous pouvons les comparer et les trier par ordre alphabétique. Les arbres binaires de recherche utilisent ces propriétés intrinsèques des données pour organiser les éléments dans une hiérarchie consultable (Figure 3.6).

Figure 3.6 Un arbre binaire de recherche organise les éléments du plus petit au plus grand de gauche à droite. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

L'arbre illustré satisfait la propriété d'arbre binaire basée sur l'ordre alphabétique naturel entre les lettres puisque les éléments de l'arbre sont organisés du plus petit au plus grand de gauche à droite. En d'autres termes, pour une liste de lettres donnée, commencez au milieu de la liste de lettres avec D (le nœud racine), puis choisissez B comme sous-nœud gauche de D qui se trouve au milieu de la liste de lettres qui est à droite de D, et choisissez F comme sous-nœud droit de D, qui se trouve au milieu de la liste de lettres qui est à gauche de D. Enfin, organisez les lettres restantes sous les sous-nœuds B et F pour vous assurer qu'elles sont du plus petit au plus grand de gauche à droite.

La propriété d'arbre de recherche est responsable des améliorations d'efficacité par rapport aux structures de données linéaires. En stockant les éléments dans un ordre trié dans l'arbre de recherche plutôt que dans un ordre indexé dans une liste, les arbres binaires de recherche peuvent trouver un élément donné plus efficacement. Considérez comment nous pourrions rechercher des mots dans un dictionnaire. Un dictionnaire d'arbre binaire de recherche stockant tous les termes et leurs définitions associées peut permettre une recherche efficace en commençant au milieu du dictionnaire (le nœud racine) avant de déterminer s'il faut aller à gauche ou à droite en fonction de si nous nous attendons à ce que notre mot apparaisse plus tôt ou plus tard dans l'ordre alphabétique. Si nous répétons ce processus, nous pouvons éliminer à plusieurs reprises la moitié des éléments restants à chaque fois. La recherche d'un terme dans un dictionnaire basé sur une liste qui n'est pas trié, en revanche, nous obligerait à commencer au début de la liste et à considérer chaque mot jusqu'à la fin de la liste puisqu'il n'y a pas de structure d'ordonnancement sous-jacente aux éléments.

Arbres binaires de recherche équilibrés

Les arbres binaires de recherche ne sont pas aussi efficaces que nous l'avons décrit. L'exemple du dictionnaire représente un scénario du meilleur cas pour les arbres binaires de recherche. Nous ne pouvons éliminer la moitié des éléments restants à chaque fois que si l'arbre binaire de recherche est parfaitement équilibré (perfectly balanced), ce qui signifie que pour chaque nœud de l'arbre binaire de recherche, ses sous-arbres gauche et droit contiennent le même nombre d'éléments. C'est une exigence forte, car l'ordre dans lequel les éléments sont ajoutés à un arbre binaire de recherche détermine la forme de l'arbre. En d'autres termes, les arbres binaires de recherche peuvent facilement devenir déséquilibrés. Il est possible qu'un arbre binaire de recherche ressemble exactement à une liste chaînée, dans laquelle chaque nœud contient soit zéro enfant, soit un enfant, ce qui n'est pas plus efficace qu'une structure de données linéaire.

Un arbre AVL (AVL tree) (nommé d'après ses inventeurs, Adelson-Velsky et Landis) est une structure de données d'arbre binaire de recherche équilibré souvent utilisée pour implémenter des ensembles ou des cartes avec une propriété d'arbre supplémentaire : la propriété d'arbre AVL (AVL tree property), qui exige que les sous-arbres gauche et droit soient équilibrés à chaque nœud de l'arbre. Les arbres AVL ne sont qu'un parmi de nombreux arbres binaires de recherche « auto-équilibrants ». Un arbre binaire de recherche équilibré (balanced binary search tree) introduit des propriétés supplémentaires qui garantissent que l'arbre réorganise les éléments pour maintenir l'équilibre (Figure 3.7).

Figure 3.7 Un arbre AVL fait pivoter les nœuds dans un arbre binaire de recherche pour maintenir l'équilibre. Cette séquence d'étapes illustre l'insertion des nombres 1, 2, 3, 4, 5, 6 dans un arbre AVL initialement vide. (Les étapes où la rotation se produit sont représentées par les flèches noires pleines.) (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Les arbres binaires de recherche équilibrés tels que les arbres AVL représentent une seule approche pour garantir que l'arbre n'entre jamais dans une situation du pire cas. Il existe de nombreuses autres structures de données d'arbres binaires de recherche équilibrés en plus des arbres AVL. Les arbres binaires de recherche équilibrés peuvent également être utilisés pour implémenter le type abstrait de données file de priorité (priority queue) si les éléments sont ordonnés selon leur valeur de priorité. Mais les arbres de recherche équilibrés ne sont pas la seule façon d'implémenter les files de priorité.

Tas binaires

Les files de priorité se concentrent sur la récupération et la suppression des éléments de plus haute priorité en premier, l'ajout d'un élément (element) à une file de priorité implique également la spécification d'une valeur de priorité associée qui est utilisée pour déterminer quels éléments sont servis ensuite. Par exemple, les patients dans un service d'urgence pourraient être servis en fonction de la gravité de leurs problèmes de santé plutôt qu'en fonction de l'heure d'arrivée. Un tas binaire (binary heap) est un type de structure de données d'arbre binaire qui est également l'implémentation la plus courante pour le type abstrait de données file de priorité (Figure 3.8). Un tas binaire n'est pas un arbre de recherche, mais plutôt une structure de données hybride entre un arbre binaire et une liste de tableau. Les données sont stockées sous forme de liste de tableau en mémoire, mais le tas binaire aide à visualiser les données de la même manière qu'un arbre binaire, ce qui facilite la compréhension de la manière dont les données sont stockées et manipulées. Les tas binaires organisent les éléments selon la propriété de tas (heap property), qui exige que la valeur de priorité de chaque nœud dans le tas soit supérieure ou égale aux valeurs de priorité de ses enfants. La propriété de tas suggère que l'élément de plus haute priorité sera toujours le nœud racine où il est efficace d'accéder.

Figure 3.8 Un tas binaire est l'implémentation la plus courante du type abstrait de données file de priorité. La valeur de priorité de chaque nœud dans le tas binaire est supérieure ou égale aux valeurs de priorité des enfants. Notez que la valeur stockée dans le nœud racine du sous-arbre droit peut être inférieure à la valeur stockée dans n'importe quel nœud du sous-arbre gauche, sans violer la propriété de tas. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Concepts en pratique

Suivi des tremblements de terre

Les tremblements de terre, les ouragans, les tsunamis et autres catastrophes naturelles se produisent régulièrement et exigent souvent une réponse internationale. Comment suivre les catastrophes naturelles et identifier les zones les plus touchées afin de coordonner les efforts de secours et de soutien ? Aux États-Unis, l'U.S. Geological Survey (USGS) est responsable de la déclaration des tremblements de terre à l'aide de milliers de capteurs sismiques. Cependant, de nombreux endroits restent sans capteurs sismiques. En dehors des États-Unis, la technologie des capteurs peut être moins robuste ou inaccessible.

Les données des réseaux sociaux peuvent être utilisées pour améliorer ces informations et alerter plus rapidement les gouvernements sur les catastrophes naturelles en temps réel. En surveillant les plateformes de réseaux sociaux publiques pour les occurrences de messages courts tels que « tremblement de terre ? », nous pouvons rapidement localiser les tremblements de terre en fonction des données de géolocalisation de l'utilisateur. Cependant, l'agrégation et la compréhension de ces données — souvent des milliers de points de données arrivant en quelques minutes — nécessitent des structures de données et des algorithmes efficaces. Nous pouvons utiliser un tas binaire qui implémente le type abstrait de données file de priorité pour un programme de suivi des tremblements de terre. Pour chaque message « tremblement de terre ? » reçu pour une géolocalisation donnée, nous pouvons augmenter la priorité des emplacements de tremblement de terre, ce qui aide à identifier l'emplacement probable du tremblement de terre le plus proche de l'emplacement réel de l'utilisateur. À tout moment, nous pouvons récupérer efficacement l'élément de plus haute priorité de la file de priorité. En choisissant d'utiliser un tas binaire plutôt qu'une structure de données linéaire pour implémenter la file de priorité, nous pouvons nous assurer que le programme de suivi des tremblements de terre est capable de suivre les milliers de messages envoyés chaque minute lors d'un tremblement de terre.

Structures de données de graphe

Les structures de données d'arbres binaires de recherche et de tas binaires représentent des moyens plus efficaces d'implémenter des ensembles, des cartes et des files de priorité en organisant les données selon leurs propriétés intrinsèques. Dans les deux cas, les propriétés des données permettent l'ajout, la récupération et la suppression efficaces d'éléments.

Les graphes sont un type différent de type abstrait de données. Plutôt que de se concentrer sur l'ajout, la récupération et la suppression, les graphes (graph) se concentrent sur la modélisation explicite des relations entre les éléments. Les graphes permettent d'accéder non seulement aux éléments, mais aussi aux relations entre les éléments.

• Un sommet (vertex) représente un élément dans un graphe ou un type spécial de celui-ci, tel qu'un arbre.
• Une arête (edge) est la relation entre les sommets ou les nœuds. En option, les arêtes peuvent avoir des poids associés. Dans un type abstrait de données graphe, les relations entre deux sommets connectés par une arête sont considérées comme adjacents (adjacent).

Dans les réseaux informatiques tels que l'Internet, les graphes peuvent représenter des routeurs (router) de réseau individuels comme des nœuds (node) avec des paquets de données (data packet) circulant entre des routeurs directement connectés le long des arêtes. Même si tous les routeurs ne sont pas directement connectés à tous les autres routeurs, le routeur au nœud actuel peut analyser un paquet de données entrant pour déterminer par quelle arête il doit voyager ensuite. En répétant ce processus, un paquet de données peut voyager d'un routeur sur l'Internet à un autre routeur sur l'Internet même si les deux routeurs ne sont pas directement adjacents l'un à l'autre.

Les graphes sont uniques en ce qu'ils peuvent représenter directement une grande variété de problèmes du monde réel, tels que les suivants :

• Un réseau social (social network), où chaque sommet est une personne et chaque arête est une amitié.
• Le Web, où chaque sommet est une page web et chaque arête est un lien.
• Une carte (map) de campus, où chaque sommet est un bâtiment et chaque arête est un sentier piétonnier.
• Un diagramme de prérequis de cours, où chaque sommet est un cours et chaque arête est un prérequis.

Contrairement aux types abstraits de données liste, ensemble, carte et file de priorité, qui ont des fonctionnalités relativement standardisées axées sur l'ajout, la récupération et la suppression d'éléments, le type abstrait de données graphe est beaucoup moins standardisé. Généralement, les concepteurs d'algorithmes de graphe créeront leur propre type de données graphe pour représenter un problème. Le problème de graphe correspondant peut alors être représenté en utilisant ou en adaptant un algorithme de graphe standard. Contrairement à la programmation avec d'autres types abstraits de données, une grande partie du travail difficile de résolution d'un problème avec un graphe se produit lorsque les programmeurs décident ce que les sommets et les arêtes représentent, et quel algorithme de graphe serait approprié pour résoudre le problème. Ils doivent également considérer les conséquences de la manière dont ils représentent le problème.

Données complexes

Maintenant que nous avons vu plusieurs implémentations de structures de données pour les données abstraites, examinons comment ces structures de données sont utilisées en pratique. Rappelons que nous avons comparé les calculatrices dont les algorithmes opéraient sur des nombres avec l'idée d'un ordinateur dont les algorithmes opéraient sur des données complexes. Les structures de données peuvent être utilisées pour représenter des données complexes en modélisant la hiérarchie et les relations.

Nous pourrions représenter un magasin de détail en ligne comme une carte associant chaque article à des détails tels qu'une image, une brève description, le prix et le nombre d'articles en stock. Cette carte facilite l'implémentation de certaines fonctionnalités de vitrine en ligne par rapport à d'autres. Étant donné un article, cette carte facilite la récupération des détails associés à cet article. D'un autre côté, il n'est pas si facile de trier les articles par prix, de trier les articles par popularité ou de rechercher un article par mots-clés dans sa description. Toutes ces fonctionnalités pourraient être implémentées avec des structures de données supplémentaires. Nous pouvons combiner plusieurs structures de données pour implémenter ces fonctionnalités. En informatique, nous utilisons des systèmes de bases de données (voir Chapitre 8 Gestion des données) qui fonctionnent en coulisses dans de nombreuses applications pour gérer ces structures de données et faciliter le stockage à long terme et l'accès à de grandes quantités de données.

Tout comme les calculatrices ont des algorithmes pour calculer des nombres, les ordinateurs ont des algorithmes pour calculer des données complexes. Les structures de données représentent ces données complexes, et les algorithmes agissent sur ces structures de données.