Taille
Comparaisons

Opération En moyenne Pire cas

Plus d'informations sur les structures de données

Visualiseur de structures de données

Une structure de données est une façon de ranger des données pour que les questions posées le plus souvent reçoivent une réponse rapide. Choisissez l'une des onze structures classiques, de la pile à l'arbre rouge-noir, tapez une valeur et appuyez sur une opération. Chaque étape se déroule à l'écran : quel nœud est comparé, quel lien change, pourquoi un arbre tourne ou une valeur remonte, avec une phrase qui nomme ce qui se passe. Les tuiles comptent le travail de chaque opération, et un tableau donne son temps d'exécution. Choisissez une structure, tapez une valeur et appuyez sur une opération. Chaque opération se déroule étape par étape : les nœuds mis en évidence montrent ce qui est comparé, déplacé ou modifié, et la ligne sous l'image dit ce qui se passe et pourquoi. Retour, Étape, Lecture et Fin parcourent de nouveau les étapes. Remplissage aléatoire et Effacer repartent de zéro, et Annuler revient sur une opération. Les tuiles montrent la taille, la hauteur des arbres, le travail de la dernière opération (comparaisons, sondages ou liens parents suivis) et un chiffre qui compte pour la structure ; le tableau donne le temps d'exécution de chaque opération.

Comment ça marche

  1. Choisissez une structure, par exemple un arbre binaire de recherche, une table de hachage ou un trie. Elle démarre avec un contenu aléatoire ; Remplissage aléatoire et Effacer repartent de zéro.
  2. Tapez une valeur et appuyez sur une opération : empiler, enfiler, insérer, supprimer, rechercher, un parcours, union ou find. Les étapes défilent toutes seules ; Retour, Étape, Lecture et Fin les parcourent de nouveau.
  3. Lisez sur la ligne sous l'image ce que fait chaque étape, suivez dans les tuiles la taille, la hauteur et le travail de la dernière opération, et comparez les temps d'exécution dans le tableau.

Listes, piles et files

Les structures les plus simples rangent les éléments en ligne. Une pile ne travaille qu'à un bout : le dernier élément entré sort le premier, comme une pile d'assiettes ; une file ajoute à l'arrière et retire à l'avant, comme une file d'attente au guichet. La file d'ici vit dans un tampon circulaire : l'avant et l'arrière tournent autour d'un tableau fixe et repassent au début après la fin, et quand il est plein, les éléments sont copiés dans un tampon deux fois plus grand. Une liste chaînée relie des nœuds par des pointeurs : insérer en tête ne coûte rien, mais trouver la queue ou un indice oblige à suivre les liens un par un.

Arbres, tas, tables de hachage et ensembles

Un arbre binaire de recherche range les valeurs plus petites à gauche et les plus grandes à droite, si bien qu'une recherche divise les candidats par deux à chaque étape, tant que l'arbre reste touffu. Les arbres AVL et rouge-noir y veillent, par des rotations que l'on peut regarder et qui sont nommées selon leur cas. Un tas ne garde au sommet que la plus petite ou la plus grande valeur, ce qui suffit à une file de priorité. Une table de hachage saute directement à une alvéole calculée à partir de la clé et doit gérer les collisions ; un trie partage les préfixes des mots ; union-find dit en temps quasi constant si deux éléments appartiennent au même ensemble.

Questions fréquemment posées

Quelle structure de données dois-je utiliser ?

Cela dépend des questions que vous posez le plus souvent. Une pile ou une file quand les éléments sont traités dans l'ordre d'arrivée ou dans l'ordre inverse ; une table de hachage pour retrouver une clé ; un arbre de recherche équilibré comme un arbre AVL ou rouge-noir quand il faut aussi les clés triées ou la clé la plus proche ; un tas quand on n'a jamais besoin que du plus petit ou du plus grand élément ; un trie pour les mots et les préfixes ; union-find pour suivre des groupes qui fusionnent.

Quelle est la différence entre un arbre AVL et un arbre rouge-noir ?

Tous deux gardent un arbre binaire de recherche peu profond, si bien que chaque recherche, insertion et suppression prend un temps proportionnel à log n. Un arbre AVL est équilibré plus strictement, avec des hauteurs des deux côtés de chaque nœud distantes d'au plus un, donc les recherches sont un peu plus rapides. Un arbre rouge-noir tolère plus de jeu et demande moins de rotations lorsqu'il change, c'est pourquoi beaucoup de bibliothèques standard l'utilisent pour leurs dictionnaires et ensembles triés.

Pourquoi une table de hachage peut-elle être lente dans le pire cas ?

Si beaucoup de clés tombent dans la même alvéole, une recherche doit les vérifier une à une, exactement comme dans une liste. Une bonne fonction de hachage répartit les clés uniformément et la table grandit avant d'être trop pleine, si bien qu'une recherche prend en moyenne un temps constant. Essayez une table de taille 10 avec des nombres qui finissent par le même chiffre, ou des mots qui sont des anagrammes les uns des autres, pour voir les collisions s'accumuler.

Que signifient les nombres à côté des nœuds AVL ?

Ce sont des facteurs d'équilibre : la hauteur du sous-arbre gauche d'un nœud moins celle de son sous-arbre droit. Dans un arbre AVL, chaque facteur d'équilibre doit valoir −1, 0 ou +1. Quand une insertion ou une suppression en fait passer un à +2 ou −2, l'arbre fait une rotation en ce nœud ; le cas (LL, RR, LR ou RL) indique de quel côté penche la hauteur en trop et décide entre une et deux rotations.

Quelque chose est-il envoyé à un serveur ?

Non. Chaque opération s'exécute dans votre navigateur, et le contenu de chaque structure est enregistré dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur